Combinatorics

**veronicak5678** · January 22nd 2011, 02:46 PM

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.

**Soroban** · January 22nd 2011, 05:36 PM

Hello, veronicak5678!

I hope I understand the problem . . .

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

**veronicak5678** · January 22nd 2011, 05:41 PM

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!

**awkward** · January 23rd 2011, 08:35 AM

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

Thread: Combinatorics

LinkBack

Thread Tools

Display

Combinatorics

Similar Math Help Forum Discussions

[SOLVED] Combinatorics.

Combinatorics

Combinatorics

combinatorics

Combinatorics

Search Tags