# Combinatorics

• Jan 22nd 2011, 02: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.
• Jan 22nd 2011, 05:36 PM
Soroban
Hello, veronicak5678!

I hope I understand the problem . . .

Quote:

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

You do this by choosing first the middle element,
then $\displaystyle \,k$ elements from its left,
then $\displaystyle \,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 $\displaystyle \,n$ is odd.

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

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

We select the middle element: 1 way.

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

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

$\displaystyle \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.}$

• Jan 22nd 2011, 05: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!
• Jan 23rd 2011, 08: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 $\displaystyle x$. In order to have at least k elements of {1,2,...,n} on each side of $\displaystyle x$, we must have $\displaystyle k+1 \leq x \leq n-k$. If we have chosen $\displaystyle x$, there are then $\displaystyle \binom{x-1}{k}$ ways to choose the k elements to the left of $\displaystyle x$ and $\displaystyle \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 \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 \displaystyle \sum_{x=k+1}^{n-k} \binom{x-1}{k} \binom{n-x}{k} = \binom{n}{2k+1}$.