CommeUnJeu · L1 PCSI
Counting
Counting is what we do when we ask « how many »? In primary school we counted on fingers ; at lycée we learned the formulas \(n^p\), \(\frac{n!}{(n-p)!}\), \(\binom{n}{p}\) and applied them to bag-of-balls problems. This chapter does two things. First, it makes the language rigorous : « how many » becomes « cardinal », defined as the integer \(n\) for which there is a bijection \(\llbracket 1, n \rrbracket \to E\). Second, it organizes the formulas around the three physical models of a draw --- with replacement, without replacement, simultaneous --- and proves them by direct counting.
The chapter is the technical bridge to probabilities. On a finite equiprobable sample space, \(\mathbb{P}(A) = |A| / |\Omega|\), so every probability calculation is a counting calculation. The reflex you should leave with is short : read the problem statement, ask « does order matter? is there replacement? », and pick the formula. The whole chapter is built to install that reflex.
A piece of advice : counting is listing, not arithmetic. When a formula does not apply, list what you want to count in a thoughtful order --- the formula will almost always come out of the listing.
The chapter is the technical bridge to probabilities. On a finite equiprobable sample space, \(\mathbb{P}(A) = |A| / |\Omega|\), so every probability calculation is a counting calculation. The reflex you should leave with is short : read the problem statement, ask « does order matter? is there replacement? », and pick the formula. The whole chapter is built to install that reflex.
A piece of advice : counting is listing, not arithmetic. When a formula does not apply, list what you want to count in a thoughtful order --- the formula will almost always come out of the listing.
I
Cardinal of a finite set
This section sets up the language of finite cardinals. The cardinal \(|E|\) is the integer that answers « how many elements does \(E\) have? ». We pin it down via bijection with \(\llbracket 1, n \rrbracket\), then study how cardinal behaves under the three operations that show up everywhere downstream : taking subsets, applying a function, combining sets by union, difference, or product. The section closes with two derived formulas --- the cardinal of an application set \(F^E\) and of a power set \(\mathcal{P}(E)\) --- that turn out to be the core bricks for the rest of the chapter.
I.1
Finite set\(\virgule\) cardinal
At lycée, the cardinal of a finite set was « the number of elements » --- counted by hand or by listing. Here we want a definition that does not assume we already know how to count. The rigorous way is to compare \(E\) to a reference set that we agree is « obviously of cardinal \(n\) » : the integer interval \(\llbracket 1, n \rrbracket = \{1, 2, \ldots, n\}\). If we can match the elements of \(E\) one-to-one with those of \(\llbracket 1, n \rrbracket\), then \(E\) « has \(n\) elements ».
Definition — Finite set\(\virgule\) cardinal
A set \(E\) is finite if it is empty, or if there exist an integer \(n \in \mathbb{N}^*\) and a bijection \(\llbracket 1, n \rrbracket \to E\). In the latter case, the integer \(n\) is unique (admitted --- the axiomatic theory of \(\mathbb{N}\) is out of program) and is called the cardinal of \(E\), denoted \(|E|\), \(\mathrm{Card}(E)\), or \(\#E\). By convention, \(|\emptyset| = 0\).A set that is not finite is said to be infinite.
Proposition — Equipotence and cardinal
Let \(E\) be a finite set of cardinal \(n\), and let \(F\) be a set in bijection with \(E\). Then \(F\) is finite and \(|F| = n\).
If \(n = 0\), then \(E = \emptyset\), and any bijection \(E \to F\) forces \(F = \emptyset\), so \(|F| = 0 = n\). If \(n \ge 1\), fix a bijection \(\varphi : \llbracket 1, n \rrbracket \to E\) and let \(\psi : E \to F\) be the given bijection. Then \(\psi \circ \varphi : \llbracket 1, n \rrbracket \to F\) is a composition of bijections, hence a bijection. So \(F\) is finite of cardinal \(n\).
Method — Showing a set is finite of cardinal n
To prove that a set \(E\) is finite of cardinal \(n\), exhibit a bijection \(\llbracket 1, n \rrbracket \to E\) --- or, equivalently, a bijection between \(E\) and a known set of cardinal \(n\). Example
For integers \(m \le n\), the set \(\llbracket m, n \rrbracket\) is finite of cardinal \(n - m + 1\). Indeed, $$ \llbracket 1, n - m + 1 \rrbracket \to \llbracket m, n \rrbracket, \quad k \mapsto k + m - 1 $$ is a bijection. Skills to practice
- Determining the cardinal of a finite set
I.2
Cardinal of a subset\(\virgule\) equality case
Two facts about subsets are useful at every step of the chapter and beyond. The first is intuitive : a subset of a finite set is finite, with smaller-or-equal cardinal. We admit it. The second is the workhorse : if a subset has the same cardinal as its host, the inclusion is in fact an equality. This second fact lets us prove \(A = B\) by checking only one inclusion plus a cardinal count --- which is often much easier than checking both inclusions.
Proposition — Cardinal of a subset and equality case
Let \(E\) be a finite set and \(A \subset E\). Then \(A\) is finite and \(|A| \le |E|\). Moreover, if \(|A| = |E|\), then \(A = E\).
Admitted
This intuitive property of the finite cardinal is admitted at this level (the most intuitive properties are admitted).
Method — Proving set equality at finite cardinal
To prove \(A = B\) where \(A\) and \(B\) are finite, it suffices to show $$ A \subset B \quad \text{and} \quad |A| = |B|. $$ This trick is used everywhere downstream : in linear algebra to show that a sub-space of full dimension is the whole space, in the symmetric group to identify finite groups, in determinant theory to identify a basis. Example
Show that if \(A \subset \llbracket 1, n \rrbracket\) has cardinal \(n\), then \(A = \llbracket 1, n \rrbracket\).
We have \(A \subset \llbracket 1, n \rrbracket\) and \(|A| = n = |\llbracket 1, n \rrbracket|\). By the Equality case, \(A = \llbracket 1, n \rrbracket\).
Skills to practice
- Computing cardinals of subsets and applying the equality case
I.3
Cardinal under an application\(\virgule\) pigeonhole
An injection \(f : E \to F\) « copies \(E\) inside \(F\) » : the image \(f(E)\) is a subset of \(F\) in bijection with \(E\), so \(E\) « fits inside » \(F\) in cardinality. A surjection \(f : E \to F\) « covers \(F\) from \(E\) » : every element of \(F\) is reached, so \(E\) « is at least as big as » \(F\). We admit these two intuitive facts. What is not obvious --- and what is the central theorem of the Cardinal of a finite set section --- is the equality case : when \(|E| = |F|\) are finite and equal, the three notions injective, surjective, bijective collapse into one. This collapse is a workhorse used in every finite-dimension argument downstream.
Method — Injection cannot increase cardinal (admitted)
Let \(f : E \to F\) be an injection between finite sets. Then \(|E| \le |F|\), with equality if and only if \(f\) is bijective. Method — Surjection cannot decrease cardinal (admitted)
Let \(f : E \to F\) be a surjection between finite sets. Then \(|F| \le |E|\), with equality if and only if \(f\) is bijective. Theorem — Bijection characterization at equal finite cardinal
Let \(E\) and \(F\) be finite sets with \(|E| = |F|\), and let \(f : E \to F\) be an application. The three following statements are equivalent : - \(f\) is bijective ;
- \(f\) is injective ;
- \(f\) is surjective.
\(f\) bijective implies trivially \(f\) injective and \(f\) surjective. Conversely :
- If \(f\) is injective, the first Method gives \(|E| \le |F|\), with equality iff \(f\) is bijective. As \(|E| = |F|\) by hypothesis, the equality case forces \(f\) bijective.
- If \(f\) is surjective, the second Method gives \(|F| \le |E|\), with equality iff \(f\) is bijective. As \(|E| = |F|\), the equality case again forces \(f\) bijective.
Method — At equal finite cardinal\(\virgule\) injectivity suffices
When \(E\) and \(F\) have the same finite cardinal, proving that an application \(f : E \to F\) is bijective reduces to proving that \(f\) is injective : surjectivity is automatic. This shortcut is used everywhere downstream (modular arithmetic, finite groups, finite-dimensional linear algebra). Proposition — Pigeonhole
There is no injective application \(\llbracket 1, n+1 \rrbracket \to \llbracket 1, n \rrbracket\). Equivalently : if \(n+1\) socks are distributed among \(n\) drawers, at least two socks share a drawer.
An injection \(\llbracket 1, n+1 \rrbracket \to \llbracket 1, n \rrbracket\) would, by the Method « Injection cannot increase cardinal », give \(n+1 \le n\), which is absurd.
Example
Show that, given any 5 points in a square of side \(2\), two of them are at distance at most \(\sqrt{2}\).
Cut the square of side \(2\) into four sub-squares of side \(1\) by the two median lines. 
The four sub-squares are the « drawers ». Distributing \(5\) points among \(4\) drawers, the pigeonhole principle gives at least two points in the same sub-square. Inside a square of side \(1\), the maximum distance between two points is the diagonal, equal to \(\sqrt{2}\). So two of the five points are at distance at most \(\sqrt{2}\).
Skills to practice
- Applying the same-cardinal characterization and pigeonhole
I.4
Operations on cardinals\(\virgule\) shepherd's principle
The arithmetic of cardinals follows two practical rules. Disjoint union adds : when we have « either the first or the second » non-overlapping case, we sum the cardinals. Cartesian product multiplies : when we have « the first then the second » independent choice, we multiply. The unifying principle is the principe des bergers : when each « shepherd » has the same number of « sheep », the total is the number of shepherds times the number of sheep per shepherd. We state it in its most powerful form, using fibres of an application.
Proposition — Disjoint union
Let \(A_1, \ldots, A_n\) be finite sets, pairwise disjoint. Then \(A_1 \sqcup \cdots \sqcup A_n\) is finite and $$ \left| \bigsqcup_{k=1}^n A_k \right| = \sum_{k=1}^n |A_k|. $$
Induction on \(n\).
- Base case \(n = 1\). Trivial : a single set \(A_1\) has cardinal \(|A_1|\).
- Case \(n = 2\). Let \(a = |A_1|\), \(b = |A_2|\), and pick bijections \(\varphi_1 : \llbracket 1, a \rrbracket \to A_1\) and \(\varphi_2 : \llbracket 1, b \rrbracket \to A_2\). Define \(\varphi : \llbracket 1, a + b \rrbracket \to A_1 \sqcup A_2\) by \(\varphi(k) = \varphi_1(k)\) for \(k \le a\) and \(\varphi(k) = \varphi_2(k - a)\) for \(a < k \le a + b\). Disjointness ensures \(\varphi\) is a bijection, hence \(|A_1 \sqcup A_2| = a + b\).
- Inductive step \(n \to n + 1\). Group \(A_1 \sqcup \cdots \sqcup A_{n+1} = (A_1 \sqcup \cdots \sqcup A_n) \sqcup A_{n+1}\) and apply the case \(n = 2\) (the two parenthesized blocks are disjoint by hypothesis). Then apply the induction hypothesis to the first block.
Proposition — Union of two sets
For \(A\) and \(B\) finite, $$ |A \cup B| = |A| + |B| - |A \cap B|. $$
Decompose \(A \cup B\) into a disjoint union : $$ A \cup B = A \sqcup (B \setminus A). $$ By disjoint union, \(|A \cup B| = |A| + |B \setminus A|\). Now \(B = (B \cap A) \sqcup (B \setminus A)\) is also a disjoint decomposition, giving \(|B| = |A \cap B| + |B \setminus A|\), hence \(|B \setminus A| = |B| - |A \cap B|\). Substituting : $$ |A \cup B| = |A| + |B| - |A \cap B|. $$
Method — Difference and complement
For \(B \subset A\) finite, \(|A \setminus B| = |A| - |B|\). In particular, for \(A \subset E\) finite, \(|A^c| = |E| - |A|\) where \(A^c = E \setminus A\). Proposition — Shepherd's principle (fibre form)
Let \(f : E \to F\) be an application between finite sets. If every fibre \(f^{-1}(\{y\})\), for \(y \in F\), has the same cardinal \(p\), then $$ |E| = p \cdot |F|. $$
The fibres of \(f\) form a partition of \(E\) : $$ E = \bigsqcup_{y \in F} f^{-1}(\{y\}), $$ in \(|F|\) disjoint blocks, each of cardinal \(p\). By disjoint union, $$ |E| = \sum_{y \in F} |f^{-1}(\{y\})| = \sum_{y \in F} p = p \cdot |F|. $$
Method — Shepherd's image
The pedagogical name says it all : think of \(F\) as the set of shepherds (\(y \in F\)), and of each fibre \(f^{-1}(\{y\})\) as the flock of sheep of that shepherd. If every shepherd has the same number \(p\) of sheep, the total number of sheep is \(p\) times the number of shepherds. This is the multiplicative reading of « choose the shepherd then choose a sheep » --- the prototype of every « then » computation in the Lists, arrangements, combinations section. Proposition — Disjoint union of equal-size blocks (corollary)
If \(A_1, \ldots, A_n\) are pairwise disjoint and all of cardinal \(p\), then $$ \left| \bigsqcup_{k=1}^n A_k \right| = n \cdot p. $$
Direct case of the disjoint union Proposition. Equivalently : the projection \(\bigsqcup A_k \to \llbracket 1, n \rrbracket\) sending \(x \in A_k\) to \(k\) is an application all of whose fibres have cardinal \(p\), and the shepherd's principle gives \(n \cdot p\).
Proposition — Cartesian product
Let \(E_1, \ldots, E_p\) be finite sets. Then $$ |E_1 \times E_2 \times \cdots \times E_p| = |E_1| \cdot |E_2| \cdots |E_p|. $$ In particular, for any finite set \(E\) and \(p \ge 1\), $$ |E^p| = |E|^p. $$
Induction on \(p\).
- Base case \(p = 1\). Trivial : \(|E_1| = |E_1|\).
- Case \(p = 2\). Consider the projection $$ \pi : E_1 \times E_2 \to E_1, \quad (x_1, x_2) \mapsto x_1. $$ For each \(x_1 \in E_1\), the fibre \(\pi^{-1}(\{x_1\}) = \{x_1\} \times E_2\) has cardinal \(|E_2|\). By the shepherd's principle, \(|E_1 \times E_2| = |E_2| \cdot |E_1|\).
- Inductive step \(p \to p + 1\). Write \(E_1 \times \cdots \times E_p \times E_{p+1}\) as \((E_1 \times \cdots \times E_p) \times E_{p+1}\) and apply the case \(p = 2\) to these two factors. Then apply the induction hypothesis to the first factor.
Method — The chapter's slogan
« this, THEN that » \(\longrightarrow\) MULTIPLICATION.
Example
How many couples \((x, y) \in \llbracket 1, n \rrbracket^2\) satisfy \(x \ne y\)?
Construct the couple in two steps : choose \(x\) (\(n\) choices) THEN choose \(y \ne x\) (\(n - 1\) choices). By the multiplication slogan, $$ \#\{(x, y) \in \llbracket 1, n \rrbracket^2 \mid x \ne y\} = n (n - 1). $$ Equivalently : the total number of couples is \(n^2\) (cartesian product), and the number of couples with \(x = y\) is \(n\) (the diagonal), so by complementation \(n^2 - n = n(n-1)\).
Skills to practice
- Computing cardinals of unions and products
I.5
Cardinal of \(F^E\) and \(\mathcal{P}(E)\)
Two formulas drop out of cardinal multiplicativity. The set \(F^E\) of all applications \(E \to F\) has cardinal \(|F|^{|E|}\) : it is just \(F^p\) in disguise, where \(p = |E|\). The power set \(\mathcal{P}(E)\), of all subsets of \(E\), has cardinal \(2^{|E|}\) : a subset is described by saying « in / out » for each element, which is an application \(E \to \{0, 1\}\). These are the bricks every subsequent counting argument rests on.
Method — Cardinal of \(F^E\)
Let \(E\) and \(F\) be finite sets with \(E\) non-empty, and write \(E = \{x_1, x_2, \ldots, x_p\}\) where \(p = |E|\). An application \(f : E \to F\) is entirely determined by the list of its values $$ (f(x_1), f(x_2), \ldots, f(x_p)) \in F^p. $$ Conversely, every list in \(F^p\) defines a unique application. Hence the map \(f \mapsto (f(x_1), \ldots, f(x_p))\) is a bijection \(F^E \to F^p\), and $$ |F^E| = |F^p| = |F|^p = |F|^{|E|}. $$ If \(E = \emptyset\), there is exactly one application \(\emptyset \to F\) (the empty application), so \(|F^\emptyset| = 1 = |F|^0\), in agreement with the formula. Proposition — Cardinal of the power set
For \(E\) a finite set, $$ |\mathcal{P}(E)| = 2^{|E|}. $$
The map $$ \Phi : \mathcal{P}(E) \to \{0, 1\}^E, \quad A \mapsto \indicatrice_A $$ is a bijection : every subset is determined by its indicator, and every \(\{0, 1\}\)-valued function on \(E\) is the indicator of a unique subset. By the previous Method, $$ |\mathcal{P}(E)| = |\{0, 1\}^E| = 2^{|E|}. $$
Method — Bricks\(\virgule\) counting all applications\(\virgule\) all subsets
- To count « all applications \(E \to F\) » : use \(|F|^{|E|}\).
- To count « all subsets of \(E\) » : use \(2^{|E|}\).
Example
Take \(E = \{a, b, c\}\). Compute the number of applications \(E \to \{0, 1\}\) and the number of subsets of \(E\). Verify that these two counts agree.
By the Method, \(|\{0, 1\}^E| = 2^{|E|} = 2^3 = 8\) applications, and \(|\mathcal{P}(E)| = 2^{|E|} = 8\) subsets. The two counts agree --- and they should, because the bijection \(A \mapsto \indicatrice_A\) identifies subsets with \(\{0, 1\}\)-valued applications. Listing makes it concrete : the \(8\) subsets are $$ \emptyset, \quad \{a\}, \{b\}, \{c\}, \quad \{a, b\}, \{a, c\}, \{b, c\}, \quad \{a, b, c\}, $$ and each one corresponds to one application \(E \to \{0, 1\}\) via its indicator.
Skills to practice
- Counting functions and subsets
II
Lists\(\virgule\) arrangements\(\virgule\) combinations
This second section is where the chapter's central reflex is built. Every counting question of the form « how many ways can I draw \(p\) items from a set of \(n\)? » falls under one of three models, and which model applies is decided by two binary questions :
- Does the order of the draw matter?
- Is each item put back after being drawn?
II.1
Listing to count
Before any formula, a piece of method. Counting is, ultimately, listing : you decide on a thoughtful order, you walk through the objects you want to count one at a time, and you read off the total. The formulas in subsections p-lists (with replacement) through p-combinations and binomial coefficients are shortcuts that bypass the listing in well-recognized cases --- but when no formula applies, the listing is your fallback, and listing in a thoughtful order often produces the formula on the fly.
Method — Three-step recipe
- Identify : what is the set of objects we want to count? Name it.
- Represent : encode each object by a concrete data structure (a word, a list, a subset, a path, a tuple).
- Decompose : split the construction into successive choices --- ADDITION for EITHER/OR, MULTIPLICATION for THEN.
Example
List the parties of \(\llbracket 1, 3 \rrbracket\) in lexicographic order, by increasing cardinal. Verify that there are \(2^3 = 8\) of them.
By increasing cardinal, then by alphabetic order on the listed elements : $$ \emptyset, \quad \{1\}, \quad \{2\}, \quad \{3\}, \quad \{1, 2\}, \quad \{1, 3\}, \quad \{2, 3\}, \quad \{1, 2, 3\}. $$ That is \(1 + 3 + 3 + 1 = 8 = 2^3\) parties, in agreement with \(|\mathcal{P}(E)| = 2^{|E|}\).
Skills to practice
- Counting small sets by listing
II.2
\(p\)-lists (with replacement)
A \(p\)-list is the simplest combinatorial object : an ordered tuple of \(p\) elements drawn from \(E\), where repetitions are allowed. The physical model is the lycée bag-draw with order and with replacement : draw a ball, write its number down, put it back, redraw, etc. The formula is the cleanest of the chapter --- \(n^p\) --- and it is just \(|E^p|\) from the Operations on cardinals, shepherd's principle subsection in a different language.
Definition — \(p\)-list
For \(p \ge 1\), a \(p\)-list (or \(p\)-uplet) of \(E\) is an element of \(E^p\), that is, an ordered tuple \((y_1, \ldots, y_p)\) with each \(y_i \in E\). Repetitions are allowed : we may have \(y_i = y_j\) for \(i \ne j\).By convention, there is exactly one \(0\)-list of \(E\) : the empty tuple. The formulas below extend to \(p = 0\) with \(n^0 = 1\).
Method — Number of \(p\)-lists
For \(|E| = n\) and \(p \ge 0\), there are $$ n^p $$ \(p\)-lists of \(E\). This is the cartesian product formula \(|E^p| = |E|^p\) from the Operations on cardinals, shepherd's principle subsection, renamed (with \(E^0\) a singleton, the empty tuple). Practical model : tirages successifs avec remise. Method — Bridge to applications
A \(p\)-list \((y_1, \ldots, y_p)\) of \(F\) is the same data as an application \(\llbracket 1, p \rrbracket \to F\) defined by \(i \mapsto y_i\). Hence the formula \(|F|^p\) for \(p\)-lists is the same as the formula \(|F|^{|E|}\) for applications \(E \to F\) when \(|E| = p\). Example
How many words of \(5\) letters can be formed on the Latin alphabet (\(26\) letters)?
A word of \(5\) letters on a \(26\)-letter alphabet is a \(5\)-list of the alphabet (with replacement, since letters may repeat). The count is $$ 26^5 = 11\,881\,376. $$
Example
How many \(4\)-digit PIN codes can be formed on the digits \(0\) to \(9\)?
A \(4\)-digit PIN code is a \(4\)-list on the digit set \(\llbracket 0, 9 \rrbracket\) (with replacement : a digit may be reused). The count is $$ 10^4 = 10\,000. $$
Skills to practice
- Counting words and PIN codes (with replacement)
II.3
\(p\)-arrangements\(\virgule\) permutations\(\virgule\) injections
A \(p\)-arrangement is a \(p\)-list with the additional constraint that all elements are distinct. The physical model is the lycée bag-draw with order and without replacement : draw a ball, set it aside, redraw a different one, etc. The formula --- the descending product \(n(n-1) \cdots (n-p+1)\) --- comes from the multiplicative slogan with the number of available choices decreasing by \(1\) at each step. The factorial form \(\frac{n!}{(n-p)!}\) is the same number, regrouped. The special case \(p = n\) gives the number of permutations of \(E\), which is \(n!\). And, because forbidding repetitions in the sequence is the same as forbidding \(f(i) = f(j)\) in the corresponding application, the same formula counts the number of injective applications \(\llbracket 1, p \rrbracket \to E\).
Definition — \(p\)-arrangement
For \(p \ge 1\), a \(p\)-arrangement of \(E\) is a \(p\)-list of \(E\) all of whose elements are distinct.By convention, the empty tuple is the unique \(0\)-arrangement ; the formula below extends to \(p = 0\) with \(\frac{n!}{n!} = 1\).
Proposition — Number of \(p\)-arrangements
Let \(|E| = n\) and \(1 \le p \le n\). The number of \(p\)-arrangements of \(E\) is $$ n (n-1) (n-2) \cdots (n-p+1) = \frac{n!}{(n-p)!}. $$ For \(p > n\), there is no \(p\)-arrangement of \(E\) ( the count is \(0\)).
Construct a \(p\)-arrangement step by step.
- Step \(1\) : choose \(y_1 \in E\) --- \(n\) possible choices.
- Step \(2\) : choose \(y_2 \in E\) with \(y_2 \ne y_1\) --- \(n - 1\) choices.
- Step \(k\) (\(1 \le k \le p\)) : choose \(y_k \in E\) distinct from \(y_1, \ldots, y_{k-1}\) --- \(n - (k-1) = n - k + 1\) choices.
Definition — Permutation
A permutation of a finite set \(E\) is a bijection \(E \to E\). The set of permutations of \(E\) is denoted \(\mathfrak{S}_E\) (or \(\mathfrak{S}_n\) when \(E = \llbracket 1, n \rrbracket\)). Proposition — Number of permutations
For \(|E| = n\), $$ |\mathfrak{S}_E| = n\,! $$
A permutation of \(E\) is in particular an injection \(E \to E\) ; by the central Theorem of the Cardinal under an application, pigeonhole subsection, in equal finite cardinal \(|E| = |E|\), an injection is automatically a bijection. So permutations are exactly the \(n\)-arrangements of \(E\). The previous Proposition gives \(\frac{n!}{(n-n)!} = \frac{n!}{0!} = n!\).
Proposition — Number of injective applications
Let \(E\) and \(F\) be finite sets with \(|E| = p\) and \(|F| = n\). The number of injective applications \(E \to F\) is $$ \frac{n!}{(n-p)!} \quad \text{if } p \le n, \qquad 0 \quad \text{if } p > n. $$
Write \(E = \{x_1, \ldots, x_p\}\). As in the Method of the Cardinal of \(F^E\) and \(\mathcal{P}(E)\) subsection, an application \(E \to F\) is identified with the list \((f(x_1), \ldots, f(x_p)) \in F^p\). The application is injective if and only if all the values \(f(x_i)\) are distinct, that is, if and only if the corresponding list is a \(p\)-arrangement of \(F\). By the previous Proposition, the count is \(\frac{n!}{(n-p)!}\) for \(p \le n\), \(0\) otherwise.
Method — Sans-remise \(\Leftrightarrow\) injection \(\Leftrightarrow\) permutation
The same number \(\frac{n!}{(n-p)!}\) counts three things : the \(p\)-arrangements of an \(n\)-set, the injective applications from a \(p\)-set to an \(n\)-set, and (when \(p = n\)) the permutations of an \(n\)-set. Recognizing one of these three forms in a problem statement immediately gives the formula. Example
How many ways are there to draw \(5\) cards successively without replacement from a \(52\)-card deck?
This is the number of \(5\)-arrangements of a \(52\)-set : $$ \frac{52\,!}{(52 - 5)\,!} = \frac{52\,!}{47\,!} = 52 \cdot 51 \cdot 50 \cdot 49 \cdot 48. $$
Example
In how many ways can \(n\) persons be seated on a straight bench? Around a round table? - Straight bench. Number the \(n\) seats from left to right. Seating \(n\) persons amounts to giving an \(n\)-arrangement of \(\{1, \ldots, n\}\) for the seats, that is, a permutation. Total : \(n!\) seatings.
- Round table. The convention must be stated explicitly :
- If the seats are numbered (each chair has its own identity), the round table behaves exactly like the straight bench : \(n!\) seatings.
- If two seatings that differ only by a rotation are considered the same (the unmarked round table), then we fix the position of one given person --- say person \(n\) --- and seat the remaining \(n - 1\) on the \(n - 1\) remaining seats around them. Total : \((n - 1)!\) seatings.
Skills to practice
- Counting anagrams\(\virgule\) seatings\(\virgule\) and constrained permutations
II.4
\(p\)-combinations and binomial coefficients
A \(p\)-combination is a subset of \(E\) of cardinal \(p\) : the elements are pulled together as a set, with no notion of order. The physical model is the simultaneous draw : grab a handful of \(p\) balls from the bag at once. The number of \(p\)-combinations of an \(n\)-set is the binomial coefficient \(\binom{n}{p}\). We have already met \(\binom{n}{p}\) in \(\mathrm{CalculAlgebrique}\) as the algebraic expression \(\frac{n!}{p!(n-p)!}\) ; here we redefine it combinatorially, then prove the equivalence with the factorial expression by double counting. The classical identities --- symmetry, Pascal, captain's formula --- are all proved by double counting, the chapter's signature technique.
Definition — Binomial coefficient (combinatorial)
For \(n \in \mathbb{N}\) and \(p \in \mathbb{Z}\), the binomial coefficient \(\binom{n}{p}\) is the cardinal of the set of \(p\)-element subsets of \(\llbracket 1, n \rrbracket\) : $$ \binom{n}{p} = \big| \mathcal{P}_p(\llbracket 1, n \rrbracket) \big| \quad \text{where} \quad \mathcal{P}_p(F) = \{ A \subset F \mid |A| = p \}. $$ We use the usual convention \(\llbracket 1, 0 \rrbracket = \emptyset\). Direct consequences : - \(\binom{n}{p} = 0\) for \(p < 0\) or \(p > n\) (no subset of cardinal outside \([0, n]\)).
- \(\binom{n}{0} = 1\) for all \(n \ge 0\) (the only subset of cardinal \(0\) is \(\emptyset\)).
- \(\binom{n}{n} = 1\) for all \(n \ge 0\) (the only subset of cardinal \(n\) is \(\llbracket 1, n \rrbracket\) itself).
- \(\binom{0}{0} = 1\) : the only subset of \(\emptyset\) of cardinal \(0\) is \(\emptyset\) itself.
Definition — \(p\)-combination
For \(p \ge 0\), a \(p\)-combination of \(E\) is a subset of \(E\) of cardinal \(p\). The set of \(p\)-combinations of \(E\) is denoted \(\mathcal{P}_p(E)\). Proposition — Cardinal of \(\mathcal{P}_p(E)\)
For \(|E| = n\), $$ |\mathcal{P}_p(E)| = \binom{n}{p}. $$
Pick a bijection \(\varphi : \llbracket 1, n \rrbracket \to E\). The induced map $$ \Phi : \mathcal{P}_p(\llbracket 1, n \rrbracket) \to \mathcal{P}_p(E), \quad X \mapsto \varphi(X) $$ is a bijection : it sends a subset of cardinal \(p\) to a subset of cardinal \(p\) (because \(\varphi\) is a bijection, \(|\varphi(X)| = |X|\)), and its inverse is \(Y \mapsto \varphi^{-1}(Y)\). Hence \(|\mathcal{P}_p(E)| = |\mathcal{P}_p(\llbracket 1, n \rrbracket)| = \binom{n}{p}\).
Theorem — Factorial expression of \(\binom{n}{p}\)
For integers \(0 \le p \le n\), $$ \binom{n}{p} = \frac{n\,!}{p\,! \, (n - p)\,!}. $$
We count the \(p\)-arrangements of \(\llbracket 1, n \rrbracket\) in two different ways.
- First count. By the formula of the p-arrangements, permutations, injections subsection, $$ \#\{p\text{-arrangements of } \llbracket 1, n \rrbracket\} = \frac{n!}{(n-p)!}. $$
- Second count. A \(p\)-arrangement is built in two steps :
- Choose the underlying \(p\)-combination (the set of values that appear) --- \(\binom{n}{p}\) choices.
- Order this set in a sequence --- \(p\,!\) choices (a permutation of a \(p\)-element set).
Proposition — Symmetry
For \(0 \le p \le n\), $$ \binom{n}{p} = \binom{n}{n - p}. $$
Combinatorial proof by complementation. The map $$ \mathcal{P}_p(\llbracket 1, n \rrbracket) \to \mathcal{P}_{n-p}(\llbracket 1, n \rrbracket), \quad A \mapsto A^c = \llbracket 1, n \rrbracket \setminus A $$ is a bijection (its inverse is itself, since \((A^c)^c = A\)). Hence the two sets have the same cardinal, that is, \(\binom{n}{p} = \binom{n}{n - p}\).
Proposition — Pascal's formula
For \(1 \le p \le n + 1\), with the convention \(\binom{n}{p} = 0\) for \(p > n\), $$ \binom{n}{p - 1} + \binom{n}{p} = \binom{n + 1}{p}. $$
Combinatorial proof. Count the subsets of cardinal \(p\) in \(\llbracket 1, n + 1 \rrbracket\) --- there are \(\binom{n+1}{p}\) of them. Split them into two disjoint families according to whether they contain the special element \(n + 1\) or not :
Equivalent form. A re-indexing \(p \to p+1\) gives the equivalent shape often seen in textbooks : $$ \binom{n}{p} + \binom{n}{p+1} = \binom{n+1}{p+1}. $$
- Subsets of cardinal \(p\) containing \(n + 1\) : remove \(n + 1\) to get a subset of cardinal \(p - 1\) in \(\llbracket 1, n \rrbracket\). This sets up a bijection with \(\mathcal{P}_{p-1}(\llbracket 1, n \rrbracket)\), so there are \(\binom{n}{p-1}\) such subsets.
- Subsets of cardinal \(p\) not containing \(n + 1\) : these are exactly the subsets of cardinal \(p\) of \(\llbracket 1, n \rrbracket\), hence \(\binom{n}{p}\) of them.
Equivalent form. A re-indexing \(p \to p+1\) gives the equivalent shape often seen in textbooks : $$ \binom{n}{p} + \binom{n}{p+1} = \binom{n+1}{p+1}. $$
Proposition — Captain's formula
For \(1 \le p \le n\), $$ p \cdot \binom{n}{p} = n \cdot \binom{n - 1}{p - 1}. $$
Combinatorial proof. We count the couples (team of \(p\) players among \(n\), captain designated within the team) in two ways.
- First count. Choose the team first (\(\binom{n}{p}\) choices), then designate the captain inside the team (\(p\) choices). Total : \(p \cdot \binom{n}{p}\).
- Second count. Choose the captain first (\(n\) choices), then complete the team with \(p - 1\) remaining players among the \(n - 1\) non-captains (\(\binom{n-1}{p-1}\) choices). Total : \(n \cdot \binom{n-1}{p-1}\).
Method — Combinations \(\Leftrightarrow\) simultaneous draws
When the problem statement says « tirage simultané » or « subset of size \(p\) », the model is the \(p\)-combination ; the formula is \(\binom{n}{p}\). The hallmark : order does not matter. Example
How many ways are there to draw \(5\) cards simultaneously from a \(52\)-card deck?
The order does not matter ; the model is a \(5\)-combination of a \(52\)-set. Total : \(\binom{52}{5}\).
Example
Compute the number of anagrams of the word BOROROS.
The word \(\mathrm{BOROROS}\) has \(7\) letters with multiplicities : \(\mathrm{O}\) appears \(3\) times, \(\mathrm{R}\) appears \(2\) times, \(\mathrm{B}\) once, \(\mathrm{S}\) once. We give two methods.
Method 1 : place each letter in its positions.
Method 1 : place each letter in its positions.
- Choose the \(3\) positions for the \(\mathrm{O}\)'s among \(7\) : \(\binom{7}{3}\) ways.
- Choose the \(2\) positions for the \(\mathrm{R}\)'s among the \(4\) remaining : \(\binom{4}{2}\) ways.
- Choose the \(1\) position for the \(\mathrm{B}\) among the \(2\) remaining : \(\binom{2}{1}\) ways.
- The last position is forced for the \(\mathrm{S}\) : \(\binom{1}{1} = 1\).
Skills to practice
- Counting subsets\(\virgule\) committees and grid paths
II.5
Combinatorial proof of the binomial formula
The chapter \(\mathrm{CalculAlgebrique}\) proved the binomial formula \((a+b)^n = \sum_{k} \binom{n}{k} a^k b^{n-k}\) by induction on \(n\), using Pascal's identity. Here we give a combinatorial proof : count where the term \(a^k b^{n-k}\) comes from in the expansion. This is exactly the kind of double-counting argument the previous subsection worked through.
Theorem — Binomial formula\(\virgule\) combinatorial proof
For \(a, b\) in a commutative ring (in particular for \(a, b \in \mathbb{R}\) or \(\mathbb{C}\)) and \(n \in \mathbb{N}\), $$ (a + b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n - k}. $$
Write $$ (a + b)^n = \underbrace{(a + b)(a + b) \cdots (a + b)}_{n \text{ factors}}. $$ Distribute the product entirely. Each term of the expansion corresponds to a choice « take \(a\) or take \(b\) » in each of the \(n\) factors. The term obtained by taking \(a\) in exactly \(k\) of the factors (and \(b\) in the other \(n - k\)) is $$ a^k b^{n - k}. $$ The number of such choices is the number of ways to select which \(k\) factors contribute the \(a\), that is, the number of \(k\)-combinations of the set of \(n\) factors : $$ \binom{n}{k}. $$ Summing over \(k = 0, 1, \ldots, n\) collects all the terms of the expansion : $$ (a + b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n - k}. $$ Equivalent form. By symmetry \(\binom{n}{k} = \binom{n}{n-k}\), the substitution \(k \to n - k\) in the sum yields the equivalent expression \(\sum_k \binom{n}{k} a^{n - k} b^k\), often seen in textbooks. The two are the same identity.
Method — Double counting for binomial identities
To prove an identity between binomial coefficients, look for a single set that the two sides count in two different ways. This single technique covers : symmetry \(\binom{n}{p} = \binom{n}{n-p}\) (counting subsets vs counting their complements), Pascal \(\binom{n+1}{p} = \binom{n}{p-1} + \binom{n}{p}\) (subsets containing or not a specified element), captain \(p\binom{n}{p} = n\binom{n-1}{p-1}\) (team-then-captain vs captain-then-team), and the binomial formula itself (which factors give the \(a\)).
Loop back to \(|\mathcal{P}(E)| \equal 2^n\)
A second proof of the formula \(|\mathcal{P}(E)| = 2^n\) falls out of the binomial formula. Apply the binomial formula at \(a = b = 1\) : $$ 2^n = (1 + 1)^n = \sum_{k=0}^n \binom{n}{k} 1^k 1^{n-k} = \sum_{k=0}^n \binom{n}{k}. $$ On the other hand, \(\mathcal{P}(E) = \bigsqcup_{k=0}^n \mathcal{P}_k(E)\) is a disjoint union by cardinal, so $$ |\mathcal{P}(E)| = \sum_{k=0}^n |\mathcal{P}_k(E)| = \sum_{k=0}^n \binom{n}{k} = 2^n. $$ This recovers --- by a completely different route --- the result of the Cardinal of \(F^E\) and \(\mathcal{P}(E)\) subsection proved there via indicators.
Example
Compute the alternating sum \(\displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k}\) for \(n \ge 1\).
Apply the binomial formula at \(a = -1\), \(b = 1\) : $$ \begin{aligned} 0 = 0^n = (-1 + 1)^n &= \sum_{k=0}^n \binom{n}{k} (-1)^k 1^{n-k} \\
&= \sum_{k=0}^n (-1)^k \binom{n}{k}. \end{aligned} $$ Hence \(\displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k} = 0\) for \(n \ge 1\). For \(n = 0\), the sum reduces to its sole term \(k = 0\), so it equals \(\binom{0}{0} = 1\) : this is the usual empty-product convention in the binomial formula.
Skills to practice
- Proving identities by double counting and binomial substitution
II.6
Synthesis --- the three fundamental models
The whole chapter --- once you erase the proofs --- can be summarized in one table. The three fundamental models classify by two binary criteria : does the order matter, and is there replacement? The corresponding cardinals are \(n^p\), \(\frac{n!}{(n-p)!}\), and \(\binom{n}{p}\). Reading a problem statement and matching it to one of the three rows is the central reflex of the chapter.
Method — The three models --- summary table
For drawing \(p\) items from a set of cardinal \(n\), the three standard models are : | Type of draw | Order | Replacement | Model | Count |
| Successive, with replacement | yes | yes | \(p\)-list of \(E\) | \(n^p\) |
| Successive, without replacement | yes | no | \(p\)-arrangement of \(E\) | \(\dfrac{n\,!}{(n-p)\,!}\) |
| Simultaneous | no | no | \(p\)-combination of \(E\) | \(\dbinom{n}{p}\) |
Method — Reading the problem statement
Faced with a counting problem, ask the two binary questions : - Does the order matter?
- Is there replacement?
- Order matters and replacement is allowed : \(p\)-list, count \(n^p\).
- Order matters and replacement is not allowed : \(p\)-arrangement, count \(\dfrac{n!}{(n-p)!}\) if \(p \le n\), \(0\) otherwise.
- Order does not matter and replacement is not allowed : \(p\)-combination, count \(\binom{n}{p}\).
- Order does not matter and replacement is allowed : multisets / stars and bars --- out of program.
Skills to practice
- Choosing list\(\virgule\) arrangement\(\virgule\) or combination from the wording
Jump to section