Dénombrement : cours de maths sup en PDF.

Un ensemble \(E\) est fini s’il est vide ou s’il existe un entier \(n \geq\, 1\) et une bijection de \([\![1, n]\!]\) sur \(E\). Cet entier \(n\) est alors unique : c’est le cardinal de \(E\), noté \(\operatorname{card}(E)\), \(|E|\) ou \(\# E\). Par convention, \(\operatorname{card}(\varnothing) = 0\).

Soit \(E\) un ensemble fini et \(A\) une partie de \(E\). Alors \(A\) est finie et \(\operatorname{card}(A) \leq\, \operatorname{card}(E)\). De plus, l’égalité \(\operatorname{card}(A) = \operatorname{card}(E)\) a lieu si et seulement si \(A = E\).

Soient \(E\) et \(F\) deux ensembles finis de même cardinal et \(f : E \to F\). Les trois assertions suivantes sont équivalentes :

• \(f\) est injective ;
• \(f\) est surjective ;
• \(f\) est bijective.

Notons \(n = \operatorname{card}(E) = \operatorname{card}(F)\). Si \(f\) est injective, alors \(f(E)\) est en bijection avec \(E\), donc \(\operatorname{card}(f(E)) = n\). Or \(f(E) \subset F\) et \(\operatorname{card}(F) = n\). D’après la propriété précédente, \(f(E) = F\) : \(f\) est surjective, donc bijective.

Réciproquement, supposons \(f\) surjective. Pour chaque \(y \in F\), choisissons un antécédent \(g(y)\). On obtient ainsi \(g : F \to E\) telle que \(f \circ g = \mathrm{id}_F\). Alors \(g\) est injective, donc bijective d’après le premier point. Finalement, \(f = f \circ g \circ g^{-1} = g^{-1}\) est bijective.

L’hypothèse de finitude est indispensable. Par exemple, l’application \(n \mapsto n + 1\) de \(\mathbb{N}\) dans \(\mathbb{N}\) est injective, mais \(0\) n’a pas d’antécédent. De même, l’égalité des cardinaux est nécessaire : une injection de \([\![1, 2]\!]\) dans \([\![1, 3]\!]\) n’est jamais surjective.

Soit \(n \geq\, 2\) et \(a\) un entier premier avec \(n\). L’application qui envoie \(x \in [\![0, n-1]\!]\) sur le reste de \(ax\) modulo \(n\) est injective, d’après le lemme de Gauss. Comme elle va d’un ensemble à \(n\) éléments dans lui-même, elle est bijective. En particulier, \(1\) possède un antécédent : \(a\) est inversible modulo \(n\).

Si \(A\) et \(B\) sont deux ensembles finis disjoints, alors \(\operatorname{card}(A \cup B) = \operatorname{card}(A) + \operatorname{card}(B)\). Plus généralement, si \(A_1, \ldots, A_p\) sont finis et deux à deux disjoints, alors

\[\operatorname{card}\Big(\bigcup_{i=1}^{p} A_i\Big) = \sum_{i=1}^{p} \operatorname{card}(A_i).\]

Soient \(E\) un ensemble fini et \(A, B\) deux parties de \(E\).

• \(\operatorname{card}(E \setminus A) = \operatorname{card}(E) – \operatorname{card}(A)\) ;
• \(\operatorname{card}(B \setminus A) = \operatorname{card}(B) – \operatorname{card}(A \cap B)\).

D’abord, \(E\) est la réunion disjointe de \(A\) et de \(E \setminus A\), d’où la première formule. Ensuite, \(B\) est la réunion disjointe de \(A \cap B\) et de \(B \setminus A\), d’où la seconde.

Pour compter les objets qui vérifient « au moins un » critère, il est souvent plus simple de passer au complémentaire. On compte alors ceux qui ne vérifient aucun critère, puis on soustrait du total. Les mots « au moins », « pas tous » ou « au plus » signalent en général cette méthode.

Combien de codes à trois chiffres (de \(000\) à \(999\)) contiennent au moins un \(7\) ? Il y a \(1000\) codes en tout. Or les codes sans \(7\) sont formés de trois chiffres pris parmi neuf : il y en a \(9^3 = 729\). Par conséquent, \(1000 – 729 = 271\) codes contiennent au moins un \(7\).

Pour deux ensembles finis \(A\) et \(B\), on a

\[\operatorname{card}(A \cup B) = \operatorname{card}(A) + \operatorname{card}(B) – \operatorname{card}(A \cap B).\]

Il existe une généralisation à \(p\) ensembles, appelée formule du crible. Elle est hors programme en première année. Pour trois ensembles ou plus, on se ramène donc à des réunions disjointes ou à un passage au complémentaire.

Si \(E\) et \(F\) sont finis, alors \(E \times F\) est fini et \(\operatorname{card}(E \times F) = \operatorname{card}(E) \times \operatorname{card}(F)\). Plus généralement,

\[\operatorname{card}(E_1 \times \cdots \times E_p) = \prod_{i=1}^{p} \operatorname{card}(E_i), \qquad \operatorname{card}(E^p) = \operatorname{card}(E)^p.\]

Notons \(F = \{y_1, \ldots, y_m\}\). Alors \(E \times F\) est la réunion disjointe des ensembles \(E \times \{y_j\}\), pour \(j\) allant de \(1\) à \(m\). Or chacun est en bijection avec \(E\). Le principe additif donne donc \(\operatorname{card}(E \times F) = m \operatorname{card}(E)\). Le cas général s’obtient ensuite par récurrence sur \(p\).

Le principe multiplicatif exige que chaque objet soit obtenu par une seule suite de choix. Si deux suites de choix différentes produisent le même objet, on compte cet objet plusieurs fois. C’est l’erreur la plus fréquente en dénombrement : elle survient dès que l’on choisit des éléments « un par un » alors que l’ordre n’importe pas.

Si \(\operatorname{card}(E) = p\) et \(\operatorname{card}(F) = n\), l’ensemble \(F^E\) des applications de \(E\) dans \(F\) est fini et \(\operatorname{card}(F^E) = n^p\).

Écrivons \(E = \{x_1, \ldots, x_p\}\). L’application \(f \mapsto (f(x_1), \ldots, f(x_p))\) est une bijection de \(F^E\) sur \(F^p\). En effet, une application est entièrement déterminée par ses valeurs, qui sont arbitraires. Donc \(\operatorname{card}(F^E) = \operatorname{card}(F)^p = n^p\).

Si \(\operatorname{card}(E) = n\), alors \(\mathcal{P}(E)\) est fini et \(\operatorname{card}(\mathcal{P}(E)) = 2^n\).

À toute partie \(A\) de \(E\), associons sa fonction indicatrice \(\mathbf{1}_A : E \to \{0, 1\}\). Cette correspondance est une bijection de \(\mathcal{P}(E)\) sur \(\{0, 1\}^E\). En effet, la réciproque associe à \(g\) la partie \(g^{-1}(\{1\})\). Par le théorème précédent, \(\operatorname{card}(\mathcal{P}(E)) = 2^n\).

Soit \(E\) un ensemble fini à \(n\) éléments. Une \(p\)-liste d’éléments de \(E\) est un élément \((x_1, \ldots, x_p)\) de \(E^p\). L’ordre compte et les répétitions sont permises. Il y a donc \(n^p\) \(p\)-listes.

Si \(0 \leq\, p \leq\, n\), le nombre de \(p\)-listes d’éléments distincts d’un ensemble à \(n\) éléments vaut

\[n(n-1)\cdots(n-p+1) = \frac{n!}{(n-p)!}.\]

Si \(p > n\), il n’y en a aucune.

On choisit \(x_1\) parmi \(n\) éléments. Ensuite, \(x_2\) se choisit parmi les \(n – 1\) éléments restants, et ainsi de suite. Enfin, \(x_p\) se choisit parmi \(n – p + 1\) éléments. Le nombre de choix à chaque étape ne dépend pas des choix précédents. Le principe multiplicatif donne donc le produit annoncé. Une récurrence sur \(p\) rend ce raisonnement rigoureux.

Si \(\operatorname{card}(E) = p\) et \(\operatorname{card}(F) = n\), le nombre d’injections de \(E\) dans \(F\) vaut \(\dfrac{n!}{(n-p)!}\) si \(p \leq\, n\), et \(0\) sinon.

Le cas \(p > n\) est le principe des tiroirs. Si l’on range \(p\) objets dans \(n\) tiroirs avec \(p > n\), un tiroir contient au moins deux objets. En effet, aucune application de l’ensemble des objets vers celui des tiroirs n’est injective.

Une permutation d’un ensemble fini \(E\) est une bijection de \(E\) sur lui-même. Si \(\operatorname{card}(E) = n\), il y a exactement \(n!\) permutations de \(E\).

Combien d’anagrammes a le mot \(\text{RADAR}\) ? Si les cinq lettres étaient distinctes, on en trouverait \(5! = 120\). Or échanger les deux R, ou les deux A, ne change pas le mot. Chaque anagramme est donc comptée \(2! \times 2! = 4\) fois. Finalement, il y a \(120 / 4 = 30\) anagrammes.

Soit \(E\) un ensemble à \(n\) éléments. Une combinaison de \(p\) éléments de \(E\) est une partie de \(E\) à \(p\) éléments. Leur nombre est noté \(\binom\,{n}{p}\) et se lit « \(p\) parmi \(n\) ». Il ne dépend que de \(n\) et \(p\).

Pour \(0 \leq\, p \leq\, n\), on a

\[\binom\,{n}{p} = \frac{n!}{p!\,(n-p)!}.\]

Pour \(p > n\), on pose \(\binom\,{n}{p} = 0\), ce qui est cohérent avec la définition.

Comptons de deux façons les \(p\)-listes d’éléments distincts de \(E\). D’une part, il y en a \(\frac{n!}{(n-p)!}\). D’autre part, on obtient chacune d’elles en choisissant d’abord la partie \(\{x_1, \ldots, x_p\}\), puis un ordre sur ses éléments. Il y a \(\binom\,{n}{p}\) choix de la partie, puis \(p!\) ordres. Ainsi, \(\binom\,{n}{p}\, p! = \frac{n!}{(n-p)!}\).

Pour \(0 \leq\, p \leq\, n\), on a la symétrie \(\binom\,{n}{p} = \binom\,{n}{n-p}\). De plus, \(\displaystyle\sum_{p=0}^{n} \binom\,{n}{p} = 2^n\).

Pour modéliser une situation, posez-vous deux questions.

• L’ordre compte-t-il ? Si oui, on travaille avec des listes ; sinon, avec des parties.
• Les répétitions sont-elles possibles ? Si oui, on prend des \(p\)-listes quelconques (\(n^p\)) ; sinon, des listes d’éléments distincts (\(\frac{n!}{(n-p)!}\)) ou des combinaisons (\(\binom\,{n}{p}\)).

Ensuite, découpez la construction en étapes : on multiplie les choix successifs et on additionne les cas disjoints.

Une urne contient \(6\) boules blanches et \(4\) noires. On tire simultanément \(3\) boules. Un tirage est une partie à \(3\) éléments parmi \(10\) : il y en a \(\binom\,{10}{3} = 120\). Pour obtenir exactement \(2\) blanches, on choisit \(2\) blanches parmi \(6\), puis \(1\) noire parmi \(4\). Il y a donc \(\binom\,{6}{2}\binom\,{4}{1} = 15 \times 4 = 60\) tels tirages.

Pour démontrer une identité par double dénombrement :

• interprétez chaque membre comme le cardinal d’un ensemble concret (comités, chemins, mots, parties) ;
• choisissez un ensemble unique que les deux membres comptent ;
• pour le membre qui est une somme, trouvez le critère qui découpe l’ensemble en cas disjoints ;
• concluez par l’égalité des deux décomptes.

Pour \(n \geq\, 1\) et \(1 \leq\, p \leq\, n\), on a

\[\binom\,{n}{p} = \binom\,{n-1}{p-1} + \binom\,{n-1}{p}.\]

Soit \(E\) un ensemble à \(n\) éléments et \(a\) un élément fixé de \(E\). Les parties de \(E\) à \(p\) éléments se répartissent en deux classes disjointes. D’abord, celles qui contiennent \(a\) : il reste à choisir \(p – 1\) éléments parmi les \(n – 1\) autres, d’où \(\binom\,{n-1}{p-1}\) parties. Ensuite, celles qui ne contiennent pas \(a\) : on choisit alors \(p\) éléments parmi \(n – 1\), d’où \(\binom\,{n-1}{p}\) parties. Le principe additif conclut.

Pour \(a\) et \(b\) deux nombres complexes et \(n \in \mathbb{N}\),

\[(a + b)^n = \sum_{k=0}^{n} \binom\,{n}{k} a^k b^{n-k}.\]

Écrivons \((a+b)^n = (a+b)(a+b)\cdots(a+b)\) avec \(n\) facteurs numérotés. En développant, on obtient une somme de \(2^n\) produits. Chacun résulte du choix, dans chaque facteur, soit de \(a\), soit de \(b\). Un tel choix est déterminé par l’ensemble \(K\) des numéros des facteurs où l’on prend \(a\). Le produit correspondant vaut \(a^k b^{n-k}\), avec \(k = \operatorname{card}(K)\). Or il y a \(\binom\,{n}{k}\) parties \(K\) à \(k\) éléments. Par conséquent, le terme \(a^k b^{n-k}\) apparaît exactement \(\binom\,{n}{k}\) fois.

Démontrons que \(k\binom\,{n}{k} = n\binom\,{n-1}{k-1}\) pour \(1 \leq\, k \leq\, n\). Comptons les comités de \(k\) personnes, parmi \(n\), munis d’un président choisi dans le comité. D’une part, on choisit le comité (\(\binom\,{n}{k}\) façons), puis son président (\(k\) façons). D’autre part, on choisit d’abord le président (\(n\) façons), puis les \(k – 1\) autres membres parmi les \(n – 1\) personnes restantes. Les deux décomptes donnent l’identité.