Results 1 to 4 of 4

Math Help - 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
    11,738
    Thanks
    644
    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.}

    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 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}.
    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: July 20th 2010, 02:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 08:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 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: October 10th 2009, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum