## Permutations and Combinations

For a positive integer n, n factorial (written: n!) is defined to be

This is equal to the number of ways of arranging n distinct objects in a row. There are n choices for the first object, n – 1 choices for the second object, n – 2 choices for the third object, and so on, and multiplying them together gives the number of ways of choosing the arrangement.

0! is defined to be equal to 1.

For a positive integer m < n, the number of ways of arranging m of the n distinct objects in a row is

nPm is read “n permute m”.

There are m! ways of rearranging the m objects within the row. So if I want to just choose m objects from the n distinct objects, without regard for order, there are

ways to choose them. nCm is read “n choose m”. It can also be written as

(2010 SMO Junior)     Your national football coach brought a squad of 18 players to the 2010 World Cup, consisting of 3 goalkeepers, 5 defenders, 5 midfielders and 5 strikers. Midfielders are versatile enough to play as both defenders and midfielders, while the other players can only play in their designated positions. How many possible teams of 1 goalkeeper, 4 defenders, 4 midfielders and 2 strikers can the coach field?

There are ways of choosing the goalkeepers, midfielders and strikers. The four defenders can be chosen from the five defenders and the remaining midfielder in ways. Hence there are 150 x 15 = 2250 ways of forming the team.

Combinatorial Identities

Algebraically, the above identity can be proven by applying the Binomial Theorem to (1 + 1)ⁿ

Combinatorially, the RHS is the total number of subsets of a set of n elements. Each term on the LHS is the number of subsets of size i.

There are usually two approaches to proving a combinatorial identity, an algebraic one involving algebraic expansion and a combinatorial one involving counting sets of objects in two different ways. See if you can prove the identities below using both approaches:

Pascal’s Identity

Hockey Stick Identity

Vandermonde’s Identity