combinatorics

Permutations and combinations

Binomial coefficients

An ordered Set a1, a2,…, ar of r distinct objects selected from a set of n objects is called a permutation of n things taken r at a time. The number of permutations is given by nPn = n(n − 1)(n − 2)⋯ (n − r + 1). When r = n, the number nPr = n(n − 1)(n − 2)⋯ is simply the number of ways of arranging n distinct things in a row. This expression is called the factorial  n and is denoted by n!. It follows that nPr = n!/(n − r)!. By convention 0! = 1.

Combinatorics and Pascal’s Triangle

Let’s calculate some values of nCr. We start with 0C0. Then we find 1C0 and 1C1. Next, 2C0, 2C1 and 2C2. Then 3C0, 3C1, 3C2 and 3C3. We can write down all these results in a table:

					0C0 = 1
				1C0 = 1		1C1 = 1
			2C0 = 1		2C1 = 2		2C2 = 1
		3C0 = 1		3C1 = 3		3C2 = 3		3C3 = 1
	4C0 = 1		4C1 = 4		4C2 = 6		4C3 = 4		4C4 = 1
5C0 = 1		5C1 = 5		5C2 = 10		5C3 = 10		5C4 = 5		5C5 = 1