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.

———-

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: