Discrete Math 101 : Fun with Combinatorics -1
April 17, 2011 Leave a comment
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 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 possible teams and pick one from among them.)
We can easily derive some interesting results using the above meaning of .
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.
Look at it this way. We have n players, say , 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 ways.
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 ways.
Therefore, we have: .
Note that given a list of k items, we can have k! permutations of those items. (This can be easily derived recursively.)