Results 1 to 4 of 4

Math Help - Combinations in a set

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    79

    Combinations in a set

    I'm really confused about the last question in this problem:

    Let S = {1, 2, . . . , n}.
    a) Suppose that k and i are integers such that 1 <= k <= i <= n. How many subsets of S of size k have i as their largest element?
    b) How many total subsets of S are of size k?
    c) Combining your answers to (a) and (b), explain how this proves the following formula for any positive integers k <= n (there are some binomial coefficients that I will right as "(x)C(y)" here, as well as a sigma-notation series):

    n
    Sigma ( (i-1)C(k-1) ) = (n)C(k)
    i=k

    For (a), I am limited to i elements, and must choose k of them, so the answer would be (i)C(k), or so I think.
    For (b), there are n total elements, and I must choose k of them, so the answer would be (n)C(k).
    I'm really not sure where to even begin with (c).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by uberbandgeek6 View Post
    I'm really confused about the last question in this problem:

    Let S = {1, 2, . . . , n}.
    a) Suppose that k and i are integers such that 1 <= k <= i <= n. How many subsets of S of size k have i as their largest element?
    b) How many total subsets of S are of size k?
    c) Combining your answers to (a) and (b), explain how this proves the following formula for any positive integers k <= n (there are some binomial coefficients that I will right as "(x)C(y)" here, as well as a sigma-notation series):

    n
    Sigma ( (i-1)C(k-1) ) = (n)C(k)
    i=k

    For (a), I am limited to i elements, and must choose k of them, so the answer would be (i)C(k), or so I think.
    For (b), there are n total elements, and I must choose k of them, so the answer would be (n)C(k).
    I'm really not sure where to even begin with (c).
    For part (a) you're close but forgot to enforce that the greatest element of the subset is fixed. So really you're choosing k-1 elements out of a set of i-1 elements.

    Part (b) correct.

    Part (c) should make more sense now.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2008
    Posts
    79
    I understand what you said about (a), but I'm still not sure about part (c). Having n elements and choosing k of them is the same as adding together all of the subsets of n-1, n-2, ..., k-1 elements, choosing k-1 elements from each. Does this make any sense? I feel like I'm just restating the question.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by uberbandgeek6 View Post
    I understand what you said about (a), but I'm still not sure about part (c). Having n elements and choosing k of them is the same as adding together all of the subsets of n-1, n-2, ..., k-1 elements, choosing k-1 elements from each. Does this make any sense? I feel like I'm just restating the question.
    We are doing a combinatorial proof by counting something in two different ways thereby proving an identity.

    Here, consider the k-subsets of S by cases:

    Case 1: the greatest element is 1.
    Case 2: the greatest element is 2.
    ...
    Case n: the greatest element is n.

    Sum them.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. combinations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 31st 2009, 09:32 PM
  2. How many combinations are possible?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: July 23rd 2009, 08:53 PM
  3. Combinations
    Posted in the Statistics Forum
    Replies: 2
    Last Post: May 5th 2008, 09:28 AM
  4. How many combinations..?
    Posted in the Algebra Forum
    Replies: 9
    Last Post: May 2nd 2008, 11:34 AM
  5. combinations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 27th 2008, 10:00 AM

Search Tags


/mathhelpforum @mathhelpforum