Discrete Math 101: Fun with Combinatorics – 2

3. ${n \choose k} = {{n-1} \choose {k-1}) + {{n-1} \choose k}}$

Our task is to select a team of k players from among n players. Now, we have 2 options – Either select player 1 to be part of the team, or leave him out of the team.

If we select player 1 to be part of the team, our task is reduced to selecting $k-1$ players from among $n-1$ players.

And if player 1 is not part of the team, our task is reduced to selecting $k$ players from among $n$ players.

Hence we have the above result.

———

4. ${n \choose k} = {{n-1} \choose {k-1}} + {{n-2} \choose {k-1}} + { {n-3} \choose {k-1}} + \ldots.$

Again our task is to select a team of k players from among n players – $P_1, \ldots, P_n$.

If $P_1$ is part of the team: We can select such a team in ${{n-1} \choose {k-1}}$ ways.

If $P_1$ is not part of the team, and $P_2$ is part of the team: The problem is reduced to selecting k-1 players from among n-2 players.

If $P_1$ and $P_2$ are not in the team, and $P_3$ is in the team: The problem is reduced to that of selecting k-1 players from among n-3 players.

Proceeding in this manner, we get the above result.

———–

5. ${n \choose k} = \frac {n}{k} {{n-1} \choose {k-1}}$

Again, we have n players at our disposal from among whom we wish to select a team of k players.

Say we select $P_1$ to be the 1st player in our team. (Note that the term “first” actually means nothing since we wish to select a “set” of objects and not an “ordered list”. However the usage of such terminology is useful for the purposes of exposition.)

Now, all we need to do is to select $k-1$ players from among $n-1$ players.

Now, let’s go back a step. What if we select $P_2$ to be the 1st player of the team, and select the remaining players for the team in ${{n-1} \choose {k-1}}$ ways.

We can see that we have n choices for the 1st player of a team.

Hence, we can select a team of k players in $n \times {{n-1} \choose {k-1}}$.

But again some teams are being repeated.

Given a fixed team, say T, we select that team k times (with each of the k players in the team being selected as the 1st player of the team). Hence we need to divide the previous result by k.

Hence we get the above result.

———-