Elementary combinatorics and the binomial theorem

Summary

This lesson studies the elementary techniques for counting the elements of a finite set without listing them one by one. It defines the number of elements of a finite set by means of bijections, proves from that definition the addition and multiplication principles, derives from them the number of permutations, of arrangements and of combinations, and defines the binomial coefficients, whose symmetry and whose Pascal’s rule are proved both by counting and by calculation. It then arranges those coefficients in Pascal’s triangle, proves by induction the binomial theorem, which generalizes the special products, and applies it to the expansion of powers, to finding a coefficient and to numerical approximation. It is the last content lesson of the unit devoted to the natural numbers, which closes with the synthesis and challenges lesson.

Learning objectives

Apply the addition and multiplication principles to count without listing, splitting into cases when the conditions of a choice interfere with each other.
Distinguish permutations, arrangements and combinations, and calculate their number by means of the factorial.
Prove the properties of the binomial coefficients by counting and by calculation, and build Pascal’s triangle with them.
Prove the binomial theorem and apply it to the expansion of powers, to the calculation of coefficients and to the approximation of powers.

The counting principles

Counting the elements of a finite set is the most elementary operation of arithmetic as long as the set can be gone through element by element. Now, when the elements are the ways of making a compound choice, such as arranging ten books on a shelf or choosing three representatives among thirty people, listing becomes impracticable, and the number is obtained by breaking the choice down into parts or into stages. All of elementary combinatorics rests on two principles, which are proved from a precise definition of what counting means.

Counting the elements of a set means numbering them: assigning an element to each number from $1$ to $n$ , without repeating any and without leaving any out. A set $A$ is said to have $n$ elements, with $n$ natural, when there is a bijection from the set $\{1, 2, \ldots, n\}$ onto $A$ , that is, a function that takes distinct numbers to distinct elements and reaches all the elements of $A$ ; the empty set has $0$ elements, and a set is finite if it is empty or has $n$ elements for some natural number $n$ . Bijections, their composition and their inverse are studied in the lesson on sets, relations and functions.

Admitted fact (number of elements). It is admitted without proof that the number of elements of a finite set is well defined: a set cannot have $m$ elements and $n$ elements at the same time if $m \neq n$ . It is also admitted that every subset of a finite set is finite.

Both facts are proved by induction on $n$ ; the first is, at bottom, the pigeonhole principle, according to which there is no function that takes the $n + 1$ numbers of $\{1, \ldots, n + 1\}$ to distinct numbers of $\{1, \ldots, n\}$ . Their proofs are long and contribute no ideas used later, and that is why they are admitted. Without the first, the expression “the number of elements” would make no sense, and a combinatorial proof, which counts one and the same set in two ways, could not conclude that the two results are equal.

PropositionAddition principle

If $A$ has $m$ elements, $B$ has $n$ elements and $A$ and $B$ have no elements in common, then $A \cup B$ has $m + n$ elements. The figure follows the proof with $m = 3$ and $n = 2$ .

Proof

$A = \{f(1), \ldots, f(m)\}, \quad B = \{g(1), \ldots, g(n)\}$
By hypothesis, there is a bijection $f$ from $\{1, \ldots, m\}$ onto $A$ and another, $g$ , from $\{1, \ldots, n\}$ onto $B$ : the elements of each set are numbered without repetitions.
$\dato{p}{i \leq m \ \vee \ i = m + j, \quad 1 \leq j \leq n}$
By trichotomy, every number $i$ from $1$ to $m + n$ satisfies $i \leq m$ or $i > m$ ; in the second case, by the definition of the order, $i = m + j$ for a natural number $j$ , unique by the cancellation law for addition, and $j \leq n$ by the monotonicity of addition.
$\dato{h}{h(i) = f(i), \quad h(m + j) = g(j)}$
We define $h$ on $\{1, \ldots, m + n\}$ : the first $m$ numbers are numbered as with $f$ , and the next $n$ , as with $g$ .
$A \cap B = \emptyset \rightarrow \resaltar{f(i) \neq g(j)}$
The function $h$ takes distinct numbers to distinct elements: two numbers from the same part, because $f$ and $g$ do so; one from each part, because they go to an element of $A$ and to one of $B$ , which have no elements in common.
$A \cup B = \{h(1), \ldots, h(m), h(m + 1), \ldots, h(m + n)\}$
The function $h$ reaches all the elements of the union: those of $A$ are values of $f$ , and those of $B$ , values of $g$ .
$h : \{1, \ldots, \resaltar{m + n}\} \to A \cup B$
Therefore, $h$ is a bijection from $\{1, \ldots, m + n\}$ onto $A \cup B$ , and the union has $m + n$ elements. If one of the sets is empty, the statement is immediate.

By induction on the number of parts, the principle extends to any finite number of pairwise disjoint sets: the union of $A_1, \ldots, A_r$ , with $n_1, \ldots, n_r$ elements, has $n_1 + \cdots + n_r$ elements, because the union of the first $r + 1$ is the union of the first $r$ with the last one, which has no elements in common with them. From it follows the second principle, which counts the choices made in stages.

PropositionMultiplication principle

If a choice is made in two stages, the first in $m$ ways and the second, whatever the first has been, in $n$ ways, the complete choice can be made in $m \cdot n$ ways. The figure draws each complete choice as a point, in the row of its first stage, with $n = 4$ .

Proof

$E = E_1 \cup E_2 \cup \cdots \cup E_m$
We group the complete choices according to the first stage: there are $m$ classes $E_1, \ldots, E_m$ with no elements in common, and each has $n$ elements, the $n$ ways of completing that first choice.
$1 \cdot n = n$
We proceed by induction on the number $m$ of classes. Base step: if $m = 1$ , all the choices are in $E_1$ , which has $n$ elements.
$\dato{h}{E_1 \cup \cdots \cup E_k}, \quad k \cdot n$
Inductive step: we assume that the union of $k$ classes with no elements in common, of $n$ elements each, has $k \cdot n$ elements.
$(E_1 \cup \cdots \cup E_k) \cup \resaltar{E_{k + 1}}, \quad k \cdot n + \resaltar{n}$
The union of $k + 1$ classes is the union of the first $k$ with the last one, which has no elements in common with them; by the addition principle, it has $k \cdot n + n$ elements.
$k \cdot n + n = \resaltar{(k + 1) \cdot n}$
By the lemma $S(k) \cdot n = k \cdot n + n$ , proved when establishing the commutativity of multiplication in the lesson on the operations, that number is $(k + 1) \cdot n$ .
$E_1 \cup \cdots \cup E_m, \quad \resaltar{m \cdot n}$
By the principle of induction, the union of $m$ classes has $m \cdot n$ elements: the complete choice can be made in $m \cdot n$ ways. In the figure, $3 \cdot 4 = 12$ .

In the same way, by induction on the number of stages, the multiplication principle extends to any finite number of them: a choice in $r$ stages, which can be made in $n_1, n_2, \ldots, n_r$ ways respectively, can be made in $n_1 n_2 \cdots n_r$ ways. For example, in the decimal system studied in the lesson on positional numeral systems there are $9 \cdot 10 \cdot 10 = 900$ three-digit numbers, because the first digit cannot be $0$ and the other two are free. It should be noted that the multiplication principle requires the number of options at each stage not to depend on what was chosen before, even though the options themselves may depend on it; if that condition fails, one splits into cases in which it holds and adds their results with the addition principle.

The successive stages of a choice are represented with a tree diagram: from an initial point, the root, there come out as many branches as the first stage has options; from the end of each branch, as many as the second has, and so on. Each route from the root to a final end, or leaf, is a complete choice, and the multiplication principle counts the leaves without drawing them.

ExampleThree-digit numbers with the digits

1

2

and

3

Count the three-digit numbers that can be written with the digits $1$ , $2$ and $3$ without repeating any, and compare them with those obtained if repetition is allowed.

Proof

$\resaltar{3}$
The first digit can be any of the three: three branches come out of the root.
$3 \cdot \resaltar{2} = \resaltar{6}$
Once the first digit is chosen, two remain for the second, whatever the first has been: each branch splits into two, and by the multiplication principle there are six possible beginnings.
$\dato{p}{3 \cdot 2 \cdot \resaltar{1} = \resaltar{6}}$
For the third digit a single possibility remains, so that each beginning is completed in exactly one way.
$123, \ 132, \ 213, \ 231, \ 312, \ 321$
The leaves of the tree, read from the root, are the six numbers sought, in increasing order.
$\resaltar{3 \cdot 3 \cdot 3} = \resaltar{27}$
If repeating digits is allowed, each stage has three options, and the tree has many more leaves than in the case without repetition.

In the rest of this lesson

Permutations, arrangements and combinations
Permutations and factorial
Arrangements
Combinations
The properties of the binomial coefficients
Symmetry
Pascal’s rule
Paths in a grid
Pascal’s triangle
The binomial theorem
Consequences and applications
Solved problems
Even numbers with four distinct digits
Paths that avoid a node
The constant term of an expansion
Committees with a chair
The sum of the squares of a row
Proposed problems
The rectangles of a grid
Passwords with letters and digits
Subsets with an even number of elements
The crossing points of the diagonals
A bound for a power