Prove that $\ k {n \choose k } = n {n - 1 \choose k -1}$ by counting the set $\{(i, S) ∈ [n] × P([n]) : i ∈ S, \#S = k\}$ in two ways.

Question

Need help constructing the proof for $\displaystyle k {n \choose k} = n {n - 1 \choose k -1}$ by counting the set $\{(i, S) ∈ [n] × P([n]) : i ∈ S, \#S = k\}$ in two ways.

I understand how to algebraically prove the equality, as well as combinatorially by providing examples of counting the LHS and RHS; however, I am confused as to how to count the equality using the set-builder notation.

Any help would be much appreciated, thank you!

Answer 1

Call the set in question $\mathscr{P}$; it is just the set of all pairs $\langle i,S\rangle$ such that $S$ is a $k$-element subset of $[n]$, and $i\in S$. We can count this set either by

• looking at each $i\in[n]$ and asking how many $k$-element subsets of $[n]$ contain that $i$,

or by

• looking at each $k$-element subset $S$ of $[n]$ and asking how many elements of $[n]$ are in that set $S$.

The second approach is easy: if $S$ is a $k$-element subset of $[n]$, there are obviously $k$ elements of $[n]$ that belong to $S$. There are $\binom{n}k$ $k$-element subsets of $[n]$, so $|\mathscr{P}|=k\binom{n}k$.

Can you finish the argument by explaining why the first approach yields the result $|\mathscr{P}|=n\binom{n-1}{k-1}$?