# Thread: Combinations in a set

1. ## 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).

2. Originally Posted by uberbandgeek6
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.

3. 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.

4. Originally Posted by uberbandgeek6
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.