Rational Mathematics

Combinations

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 = S(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.