Dénombrement — Cours en classe — Terminale spécialité

Démonstration 1.1 — Ni oubli ni double compte

Chaque élément de \(E\) appartient à un cas, car les cas couvrent \(E\), et à un seul, car ils sont disjoints. L’addition compte donc chaque élément exactement une fois. Les deux conditions sont nécessaires : sans couverture on omettrait des éléments, sans disjonction on en compterait plusieurs fois.

Démonstration 1.2 — Retirer les cas non retenus

Les ensembles \(A\) et \(E\setminus A\) sont disjoints et leur réunion est \(E\). Ainsi \(\operatorname{Card}\left(E\right)=\operatorname{Card}\left(A\right)+\operatorname{Card}\left(E\setminus A\right)\), d’où la formule par soustraction.

Démonstration 1.3 — Les trois régions de la réunion

Notons \(x=\operatorname{Card}\left(A\setminus B\right)\), \(y=\operatorname{Card}\left(A\cap B\right)\) et \(z=\operatorname{Card}\left(B\setminus A\right)\). Ces régions sont disjointes ; la réunion contient \(x+y+z\) éléments. Or \(\operatorname{Card}\left(A\right)+\operatorname{Card}\left(B\right)-\operatorname{Card}\left(A\cap B\right)=(x+y)+(y+z)-y=x+y+z\). On retire donc l’intersection une seule fois.

Démonstration 2.1 — Compter les lignes, puis prolonger

Pour chaque \(a\in A\), il y a exactement \(\operatorname{Card}\left(B\right)\) couples commençant par \(a\). Deux valeurs différentes de \(a\) donnent des groupes disjoints. On additionne donc \(\operatorname{Card}\left(A\right)\) fois \(\operatorname{Card}\left(B\right)\). Pour une troisième composante, chacun des couples se prolonge de \(\operatorname{Card}\left(C\right)\) façons ; le raisonnement se répète pour les facteurs suivants. Si un facteur est vide, aucun résultat ne peut être construit et les deux membres valent zéro.

Démonstration 2.2 — Prolonger chaque début

Après la première étape, il existe \(m_1\) débuts. Chacun en fournit \(m_2\) à l’étape suivante, soit \(m_1m_2\). À chaque étape, le nombre de constructions est multiplié par le nombre commun de prolongements. Les constructions complètes sont donc au nombre de \(m_1\cdots m_r\) ; l’unicité de la construction d’un résultat permet de compter les résultats par ce même produit.

Démonstration 2.3 — Une place, un facteur

Chacune des \(k\) places peut recevoir n’importe lequel des \(n\) éléments, même s’il a déjà été utilisé. Les choix d’une place ne retirent donc aucun élément pour les suivantes. Chaque remplissage correspond à une liste unique ; le principe multiplicatif donne \(k\) facteurs égaux à \(n\), soit \(n^k\).

Démonstration 3.1 — Remplacer les objets par leurs partenaires

Énumérons le premier ensemble sans oubli ni répétition, puis remplaçons chaque objet par son partenaire. Tous les objets du second apparaissent exactement une fois : la longueur de la liste ne change pas. Si le premier ensemble est vide, le second l’est aussi, puisqu’aucun élément ne pourrait y avoir de partenaire.

Démonstration 3.2 — Coder, puis décoder

Pour chacun des \(n\) éléments, on décide s’il est présent ou absent : deux choix. Si \(n\geq1\), le principe multiplicatif donne \(2^n\) codes.

Une partie donne un code unique ; inversement, un code redonne la partie en retenant exactement les éléments marqués 1. Ces deux opérations sont inverses : c’est une correspondance bijective. Il y a donc autant de parties que de codes.

Pour \(n=0\), l’ensemble vide possède une seule partie, lui-même, et \(2^0=1\). Ce cas est bien inclus dans le résultat.

Démonstration 4.1 — Remplir successivement les positions

La première position offre \(n\) choix. Quelle que soit la valeur choisie, la deuxième en offre \(n-1\). Avant la \(k\)-ième position, \(k-1\) objets différents ont été utilisés ; il reste donc \(n-(k-1)=n-k+1\) choix. Le principe multiplicatif donne le produit annoncé. Chaque liste est obtenue une seule fois, car ses positions déterminent les choix successifs.

Pour \(k=0\), aucune place n’est à remplir : il n’y a qu’une liste sans composante. Pour \(k>n\), après l’utilisation des \(n\) objets, aucune nouvelle position ne peut recevoir un objet différent : le nombre de listes est nul.

Démonstration 4.2 — Isoler un facteur

Pour \(n\geq2\), \(n!=n\underbrace{(n-1)\cdots2\times1}_{(n-1)!}\). Pour \(n=1\), \(1\times0!=1=1!\). Remplacer \(n\) par \(n+1\) donne la seconde écriture.

Démonstration 4.3 — Retirer les facteurs communs

Pour \(1\leq k\leq n\), on a \(n!=n(n-1)\cdots(n-k+1)(n-k)!\). Diviser par \((n-k)!\), strictement positif, laisse exactement les \(k\) facteurs voulus. Pour \(k=0\), le quotient vaut \(n!/n!=1\) ; pour \(k=n\), il vaut \(n!/0!=n!\).

Démonstration 4.4 — Prendre \(k=n\)

Dans la propriété précédente, on utilise tous les objets : le nombre vaut \(n!/(n-n)!=n!/0!=n!\). Pour \(n=0\), on retrouve bien une seule permutation.

Démonstration 5.1 — Justifier une division

Si \(q\) est le nombre de paquets, leur réunion contient \(q\times m=N\) représentations. Comme \(m\ne0\), on obtient \(q=N/m\). La même taille pour tous les paquets est indispensable.

Démonstration 5.2 — Passer des listes aux parties

Pour \(1\leq k\leq n\), il existe \(n!/(n-k)!\) listes de \(k\) éléments distincts. Un groupe fixé de \(k\) éléments fournit exactement \(k!\) listes, en permutant ses éléments. Deux groupes différents ne produisent aucune liste commune : oublier l’ordre d’une liste donne un unique groupe.

Les listes sont donc réparties en paquets disjoints de taille constante \(k!\). Le lemme donne \[\binom{n}{k}=\frac{\dfrac{n!}{(n-k)!}}{k!} =\frac{n!}{k!(n-k)!}.\] Pour \(k=0\), l’unique partie vide donne \(\binom{n}{0}=1\), et la formule donne aussi \(n!/(0!n!)=1\). Pour \(k\geq1\), simplifier \((n-k)!\) après avoir développé les \(k\) premiers facteurs de \(n!\) donne la seconde écriture.

Démonstration 5.3 — Compter directement les cas simples

Choisir aucun élément donne la seule partie vide ; choisir tous les éléments donne l’ensemble entier. Choisir un élément offre \(n\) possibilités. Pour deux éléments, les \(n(n-1)\) couples distincts représentent chaque paire exactement deux fois, d’où \(n(n-1)/2\). Pour \(n=0\), les deux coefficients de bord désignent le même nombre : \(\binom{0}{0}=1\).

Démonstration 5.4 — Associer une partie à son complémentaire

Dans un ensemble \(E\) à \(n\) éléments, à chaque partie \(A\) de taille \(k\), on associe \(E\setminus A\), de taille \(n-k\). Prendre une seconde fois le complémentaire redonne \(A\) : deux parties différentes ont donc des complémentaires différents. De plus, toute partie \(B\) de taille \(n-k\) est obtenue à partir de \(E\setminus B\), de taille \(k\). La correspondance est une bijection ; les deux collections ont le même cardinal.

Démonstration 6.1 — Par dénombrement

Dans un ensemble de \(n+1\) éléments, distinguons un élément \(z\). Classons les parties de taille \(k\) en deux catégories.

• Celles qui contiennent \(z\) sont déterminées par le choix de \(k-1\) autres éléments parmi les \(n\) éléments différents de \(z\) : il y en a \(\binom{n}{k-1}\).

• Celles qui ne contiennent pas \(z\) sont des parties de taille \(k\) parmi ces \(n\) autres éléments : il y en a \(\binom{n}{k}\).

Ces catégories sont disjointes et couvrent toutes les parties de taille \(k\). Le principe additif donne \(\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}\). Aucune place n’est à choisir pour \(z\) : une partie n’est pas ordonnée.

Démonstration 6.2 — Par calcul

Les hypothèses \(1\leq k\leq n\) garantissent que toutes les factorielles suivantes sont définies et non nulles. En mettant au même dénominateur, \[\begin{align*} \binom{n}{k-1}+\binom{n}{k} &=\frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!}\\ &=\frac{k\,n!}{k!(n-k+1)!} +\frac{(n-k+1)n!}{k!(n-k+1)!}\\ &=\frac{[k+(n-k+1)]n!}{k!(n-k+1)!}\\ &=\frac{(n+1)n!}{k!(n+1-k)!} =\frac{(n+1)!}{k!(n+1-k)!} =\binom{n+1}{k}. \end{align*}\] Le premier quotient a été multiplié en haut et en bas par \(k\), le second par \(n-k+1\). On a ensuite utilisé \(k+(n-k+1)=n+1\) et \((n+1)n!=(n+1)!\).

Démonstration 6.3 — Pourquoi la construction est correcte

Les coefficients de bord valent 1. Pour chaque position intérieure, Pascal donne le coefficient de la ligne \(n+1\) à partir de deux coefficients de la ligne \(n\). La ligne initiale étant correcte, toutes les lignes suivantes le sont aussi. À la ligne \(n\), les indices vont de 0 à \(n\), soit \(n+1\) termes.

Démonstration 6.4 — Compter les parties de deux façons

Un ensemble à \(n\) éléments possède \(2^n\) parties. Classons-les selon leur taille : 0, 1, …, \(n\). Chaque partie a une seule taille ; ces catégories sont donc disjointes et couvrent toutes les parties. La catégorie de taille \(k\) contient \(\binom{n}{k}\) parties.

Par le principe additif, le nombre total vaut aussi \(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}\). Les deux expressions comptent les mêmes parties, d’où l’égalité. Le terme \(\binom{n}{0}=1\) compte la partie vide ; pour \(n=0\), on retrouve \(\binom{0}{0}=1=2^0\).

Démonstration 7.1 — Choisir les positions des pas H

Chaque chemin est codé par un mot de \(a+b\) lettres D et H. Choisir les \(b\) positions des H détermine le mot entier, donc le chemin ; inversement, lire le chemin restitue un seul choix de ces positions. Il y a donc \(\binom{a+b}{b}\) chemins. Choisir les positions des D donne de même \(\binom{a+b}{a}\).

Démonstration 7.2 — Additionner les probabilités des issues

Posons \(N=\operatorname{Card}\left(\Omega\right)\geq1\) et notons \(q\) la probabilité commune. Les \(N\) issues sont disjointes et couvrent l’univers, donc \(Nq=1\) et \(q=1/N\). Si A contient \(m\) issues, leurs probabilités s’ajoutent : \(P(A)=m/N\). Le complémentaire contient \(N-m\) issues, d’où \(P(\overline A)=(N-m)/N=1-P(A)\). Cette dernière égalité reste vraie sans équiprobabilité, par additivité des probabilités de A et de son contraire.

Démonstration 8.1 — La ligne correcte à chaque passage

Au départ, ligne contient bien la ligne \(0\). Supposons qu’avant un passage elle contienne la ligne \(r\), de longueur \(r+1\). La nouvelle liste commence par \(1=\binom{r+1}{0}\) ; pour \(1\leqslant k\leqslant r\), la boucle intérieure ajoute \[\binom{r}{k-1}+\binom{r}{k}=\binom{r+1}{k}.\] Le dernier \(1=\binom{r+1}{r+1}\) complète la ligne \(r+1\). Après \(n\) passages, on obtient donc la ligne \(n\). Les deux boucles sont finies. Si \(n=0\), aucun passage n’a lieu et la sortie est [1].

Démonstration 8.2 — Justifier les bornes des boucles

Une sortie utilise des indices distincts compris entre \(0\) et \(n-1\) : elle représente donc une partie valide. Toute partie possède un unique rangement croissant de ses indices ; les boucles visitent ce rangement, donc aucune partie n’est oubliée. Deux sorties représentant la même partie auraient exactement ces mêmes indices croissants : elles proviendraient du même passage, donc il n’y a pas de doublon. Les boucles sont finies. Si \(n<2\) ou \(n<3\), selon le programme, aucune chaîne d’indices de la longueur requise n’existe.

Démonstration 8.3 — Retirer puis ajouter le même objet

Après \(j\) passages, resultat contient \(j\) objets et restants les \(n-j\) autres : les deux listes sont disjointes et leur réunion est l’ensemble initial. C’est vrai au départ. À chaque passage, le retrait d’un objet disponible et son ajout au résultat conservent cette affirmation. La longueur restante diminue de \(1\) ; après \(n\) passages, elle est nulle, et le résultat contient tous les objets exactement une fois. Seule la copie de E a été modifiée.