# Combinatorics

Printable View

• January 22nd 2011, 03:46 PM
veronicak5678
Combinatorics
Suppose you want to choose a (2k+1)-element subset of the n-element set {1,2,...,n}. you decide to do this by choosing first the middle element, then the elements to its left, then the k elements to its right. Formulate the combinatorial identity you get from doing this.
• January 22nd 2011, 06:36 PM
Soroban
Hello, veronicak5678!

I hope I understand the problem . . .

Quote:

Suppose you want to choose a $(2k+1)$-element subset
from the $\,n$-element set: . $\{1,2, \hdots,n\}$

You do this by choosing first the middle element,
then $\,k$ elements from its left,
then $\,k$ elements from its right.

Formulate the combinatorial identity you get from doing this.
The question could have been stated more clearly.

Since there is a "middle element", I assume that $\,n$ is odd.

Then the middle element is $\frac{n+1}{2}$

There are: $\frac{n-1}{2}$ elements to the left, and $\frac{n-1}{2}$ elements to the right.

We select the middle element: 1 way.

We select $\,k$ elements from the $\frac{n-1}{2}$ elements on the left.
. . There are: . $\displaystyle{\frac{n-1}{2} \choose k}$ ways.

We select $\,k$ elements from the $\frac{n-1}{2}$ elements on the right.
. . There are: . $\displaystyle {\frac{n-1}{2} \choose k}$ ways.

$\displaystyle\text{Therefore, there are: }\;1\cdot{\frac{n-1}{2}\choose k}\cdot{\frac{n-1}{2}\choose k} \;=\;{\frac{n-1}{2}\choose k}^2\:\text{ such subsets.}$

• January 22nd 2011, 06:41 PM
veronicak5678
Thanks for answering. I had the same answer, but I wasn't sure it was what they were asking. I don't think English is the author's first language!
• January 23rd 2011, 09:35 AM
awkward
Quote:

Originally Posted by veronicak5678
Suppose you want to choose a (2k+1)-element subset of the n-element set {1,2,...,n}. you decide to do this by choosing first the middle element, then the elements to its left, then the k elements to its right. Formulate the combinatorial identity you get from doing this.

It seems to me the problem is poorly stated, but I have a different interpretation of it than previously given, with the advantage that it leads to an interesting identity.

I think the problem is asking us to first select the middle element of the 2k+1 element subset. Notice that we know there is a middle element because 2k+1 is odd. Let's say the middle element is $x$. In order to have at least k elements of {1,2,...,n} on each side of $x$, we must have $k+1 \leq x \leq n-k$. If we have chosen $x$, there are then $\binom{x-1}{k}$ ways to choose the k elements to the left of $x$ and $\binom{n-x}{k}$ ways to choose the k elements to the right. So the total number of ways to select the 2k+1 element subset is

$\displaystyle \sum_{x=k+1}^{n-k} \binom{x-1}{k} \binom{n-x}{k}$.

But in the end we have chosen an arbitrary 2k+1 element subset of {1,2,...,n}, so

$\displaystyle \sum_{x=k+1}^{n-k} \binom{x-1}{k} \binom{n-x}{k} = \binom{n}{2k+1}$.