Results 1 to 4 of 4

Thread: Combinatorics

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    225

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, veronicak5678!

    I hope I understand the problem . . .


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

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    225
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by veronicak5678 View Post
    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}$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: Jul 20th 2010, 02:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jun 18th 2010, 08:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jun 3rd 2010, 05:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 10:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 10th 2009, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum