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.