Discrete Math 101 : Fun with Combinatorics -1

n \choose k is the number of ways we can select k items from a group of n items. Say the number of players in India’s world cup squad is 14. Only 11 players can play in any particular match. Hence, on match-day, the coach has 14 \choose 11 possibilities for selecting a team of 11 players from his squad. (Of course, such a situation is simply a theoretical conjecture, and no sane coach would actually list down each of 14 \choose 11 possible teams and pick one from among them.)

We can easily derive some interesting results using the above meaning of n \choose k.

1. {n \choose k} = { n \choose {n-k}}

Our task is to select a team of k players from among n players. We can do this by directly selecting which players are to be part of the team, or by selecting which players are to be left out, giving the above result.

2. n \choose k = \frac { n! } {k! (n-k)! }

Look at it this way. We have n players, say P_1, \ldots, P_n, and we want to select a team of k players from among them.

Let us select the players one by one.

For selecting the first player, we have n possible options.

Now having selected one player, we have n-1 possible options for selecting the 2nd player.

Similarly, given that we have selected i players, we have n-i options for selecting the i+1 th player.

Thus, we get that we can select k players from among n players in n \times (n-1) \times (n-2) \times \ldots \times (n-k) ways.

But wait!

There are many repetitions in the teams of 11 players that we selected. Consider any particular fixed team of k players. That team is selected by us in k! ways.

Therefore, we have: {n \choose k} = \frac {n \times \ldots \times (n-k)} {k!} = \frac {n!} {k! (n-k)!}.


Note that given a list of k items, we can have k! permutations of those items. (This can be easily derived recursively.)



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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: