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

——-