Theorem (The Combination Principle): The number of ways of choosing m elements from a set of n elements is n!|((n−m)!.m!). Proof: The number of ways of choosing a sequence of m elements is n!|(n–m)! and the number of ways of arranging m elements in a sequence is m! So the n!|(n–m)! sequences fall into sets of m! containing the same elements. Thus if we denote the number of these sets by c then n!|(n–m)! = c.(m!). Thus c = n!|((n–m)!.m!).
It is often convenient to use the notation: nCm = n!|((n–m)!.m!) where C can be called the combinatorial operation. For n<m we define nCm = 0. The operation table for the combinatorial operation C is a version of Pascal's Triangle.
Combination table (base ten)
| C | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 1 | 3 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 1 | 4 | 6 | 4 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | 0 | 0 | 0 | 0 |
| 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | 0 | 0 | 0 |
| 8 | 1 | 8 | 28 | 56 | 70 | 56 | 28 | 8 | 1 | 0 | 0 |
| 9 | 1 | 9 | 36 | 84 | 126 | 126 | 84 | 36 | 9 | 1 | 0 |
| 10 | 1 | 10 | 45 | 120 | 210 | 252 | 210 | 120 | 45 | 10 | 1 |
Example: How many dominoes are there in a double (n–1) set? The set contains every distinct pair of numbers from {0, 0} to {n–1, n–1}. Thus the total is nC2 = n.(n+1)|2, the nth triangular number. The triangular numbers are the numbers that appear in column 2 of the combinatorial table (and in the diagonal from 1 in the left column). The numbers that appear in the third column are the sums of the triangular number series. Thus nC3 = 2C2 + 3C2 + ... + (n–1)C2. The numbers in the fourth column are sums of those in the third column,and so on.
Example: What is the maximum number of pieces that can result from n straight vertical cuts? We have f(1) = 2 and the nth cut increases the number of regions by n at most. Thus f(n) = f(n–1) + n, whence f(n) = n.(n+1)|2 + 1 = nC0 + nC1 + nC2. Sequence: 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, ... The augmented triangular numbers. [Jacob Steiner 1826]
Example: What is the maximum number s(n) of regions bounded by n planes in space? We have s(1) = 2. The number of 3D regions defined by the nth plane is the number of 2D regions defined in it by its n–1 straight-line intersections with the previous planes. Hence s(n) = s(n–1) + r(n–1) = nC0 + nC1 + nC2 + nC3. [This problem goes back to Jacob Steiner, Journal für die reine und angewandte Mathematic, vol.1, pp.349-364, 1826.]
Example. The number of different Bridge hands of 13 cards that can be dealt, from a pack of 52 cards, is 52C13 = 52!|(39!.13!)
Theorem (Complementarity): The number of ways of choosing m elements from a set of n is the same as the number of ways of choosing n−m elements. In symbols this theorem is: nCm = nC(n−m). Proof: (a) This statement is equivalent to the commutative property n!|((n−m)!.m!) = n!|(m!.(n−m)!) since n−(n−m) = m. (b) Alternatively we can note that choosing to include m of n is the same as choosing to exclude n−m of n.
Observation (The Bell Curve): The values of n!|((n−m)!.m!) as m runs from 0 to n form a symmetric bell-shaped pattern, rising to a maximum at the middle value n|2 when n is even, or the two middle values (n±1)|2 when n is odd.
Theorem (Binomial Theorem): The nth power of the sum of two terms is: (a+b)^n =
∑(r = 0 to n)[nCr.a^(n-r).b^r]. Proof: by induction.
Written out more fully it becomes: (a+b)^n = a^n + n.a^(n–1).b + (n.(n–1)|2).a^(n–2).b^2 + ...
+ [n!|((n–m)!.m!)].a^(n–m).b^m + ... + b^n.
Examples:
(a+b)^2 = a^2 + 2.a.b + b^2
(a+b)^3 = a^3 + 3.(a^2).b + 3.a.(b^2) + b^3
(a+b)^4 = a^4 + 4.(a^3).b + 6.(a^2).(b^2) + 4.a.(b^3) + b^4.
Note: Because of this result the numbers nCm for a given value of n are sometimes called binomial coefficients since they are the numerical factors that appear in the multiplied-out expression for (a+b)^n.
Theorem (Partitions): The number ways of expressing n (> m−1) as a sum of m numbers is (n−1)C(m−1). Proof: If we represent the numbers in linear tally form then expressing n as a sum of m numbers is equivalent to separating a row of n tallies into m sets, by introducing m−1 gaps, and there are n−1 places where gaps can be introduced.
Examples:
When m = 2, the formula reduces to n–1:
2 = 1+1, 3 = 1+2 = 2+1, 4 = 1+3 = 2+2 = 3+1, 5 = 1+4 = 2+3 = 3+2 = 4+1.
When m = 3 the formula reduces to (n–1).(n–2)|2:
3 = 1+1+1, 4 = 1+1+2 = 1+2+1 = 2+1+1, 5 = 1+1+3 = 1+2+2 = 1+3+1 = 2+1+2
= 2+2+1 = 3+1+1.