Rational Mathematics

by G. P. Jelliss

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!|(nm)! and the number of ways of arranging m elements in a sequence is m! So the n!|(nm)! sequences fall into sets of m! containing the same elements. Thus if we denote the number of these sets by c then n!|(nm)! = c.(m!). Thus c = n!|((nm)!.m!).

It is often convenient to use the notation: nCm = n!|((nm)!.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)
C012345678910
010000000000
111000000000
212100000000
313310000000
414641000000
51510105100000
616152015610000
7172135352171000
81828567056288100
91936841261268436910
101104512021025221012045101

Example: How many dominoes are there in a double (n1) set? The set contains every distinct pair of numbers from {0, 0} to {n1, n1}. 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 + ... + (n1)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(n1) + 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 n1 straight-line intersections with the previous planes. Hence s(n) = s(n1) + r(n1) = 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^(n1).b + (n.(n1)|2).a^(n2).b^2 + ... + [n!|((nm)!.m!)].a^(nm).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.