MPSI · Dénombrement

Triangle de Pascal et formule du binôme de Newton

Palier 0Palier 1Palier 1+Palier 2

L'objet de cette partie est de donner une interprétation combinatoire aux formules portant sur les coefficients binomiaux.

Question

Les identités sur les coefficients binomiaux se vérifient toutes en manipulant des factorielles — c'est exact, mais aveugle : on constate l'égalité sans jamais comprendre pourquoi elle a lieu. Or (np)\binom{n}{p} n'est pas seulement un quotient de factorielles : c'est le nombre de parties à pp éléments. Chaque identité devient alors l'affirmation que deux façons de compter le même ensemble donnent le même résultat. Peut-on démontrer ainsi, sans un seul calcul ?

Proposition 1 : Symétrie

Soient n∈Nn\in\mathbb{N} et 0⩽p⩽n0\leqslant p\leqslant n. Alors (np)=(nn−p)\dbinom{n}{p}=\dbinom{n}{n-p}.

Démonstration :

Choisir pp éléments parmi nn revient à décider lesquels (n−pn-p) on ne choisit pas.

Exemple :

(107)=(103)=120\dbinom{10}{7}=\dbinom{10}{3}=120 : désigner les 77 élèves d'une classe de 1010 qui partiront en sortie, c'est désigner les 33 qui resteront. On calcule évidemment le second, bien plus court. Comment ce passage de l'un à l'autre s'écrit-il proprement, sans invoquer les factorielles ?

Exercice 1 : La symétrie, par les factorielles

Redémontrer la relation (np)=(nn−p)\dbinom{n}{p}=\dbinom{n}{n-p} à partir de la seule expression (np)=n!p! (n−p)!\dbinom{n}{p}=\dfrac{n!}{p!\,(n-p)!}.

Solution :(cliquer pour afficher)

Soit 0⩽p⩽n0\leqslant p\leqslant n. Alors 0⩽n−p⩽n0\leqslant n-p\leqslant n, de sorte que (nn−p)\dbinom{n}{n-p} est bien défini, et la formule donne

(nn−p)=n!(n−p)! (n−(n−p))!=n!(n−p)! p!.\binom{n}{n-p}=\frac{n!}{(n-p)!\,\bigl(n-(n-p)\bigr)!}=\frac{n!}{(n-p)!\,p!}.

Le produit p! (n−p)!p!\,(n-p)! étant commutatif, ce dernier quotient est exactement n!p! (n−p)!=(np)\dfrac{n!}{p!\,(n-p)!}=\dbinom{n}{p}.

On mesure au passage la différence de nature entre les deux preuves : celle-ci vérifie l'égalité, la preuve combinatoire l'explique.

Question

Le triangle de Pascal se construit de proche en proche : chaque coefficient est la somme des deux qui le surplombent. Pourquoi cette règle d'addition ? Qu'est-ce qui, dans le fait de choisir p+1p+1 éléments parmi n+1n+1, se décompose naturellement en deux cas incompatibles ?

Théorème 1 : Formule du triangle de Pascal

Soient n∈Nn\in\mathbb{N} et 0⩽p⩽n0\leqslant p\leqslant n. Alors

(np)+(np+1)=(n+1p+1).\binom{n}{p}+\binom{n}{p+1}=\binom{n+1}{p+1}.

Démonstration :

On note x1,x2,…,xn+1x_1,x_2,\dots,x_{n+1} les n+1n+1 éléments d'un ensemble EE et l'on met à part l'élément xn+1x_{n+1}.

Pour choisir p+1p+1 éléments dans EE, deux cas s'excluent :

  • Si l'on prend l'élément xn+1x_{n+1}, il reste (np)\dbinom{n}{p} choix pour les autres.
  • Si on ne le prend pas, il reste (np+1)\dbinom{n}{p+1} choix possibles.

Ces deux possibilités étant exclusives, le nombre total de choix est leur somme, d'où la formule annoncée.

Test 1 : Pascal de mémoire

Pour 0⩽p⩽n0\leqslant p\leqslant n, on a (np)+(np+1)=(n+1p)\dbinom{n}{p}+\dbinom{n}{p+1}=\dbinom{n+1}{p}.

Exercice 2 : Une colonne du triangle

Soient n∈N∗n\in\mathbb{N}^* et p∈Np\in\mathbb{N} avec p⩽np\leqslant n. Établir la formule

∑k=pn(kp)=(n+1p+1).\sum_{k=p}^{n}\binom{k}{p}=\binom{n+1}{p+1}.
Solution :(cliquer pour afficher)

Par récurrence sur n⩾pn\geqslant p, à pp fixé.

Initialisation. Pour n=pn=p, la somme se réduit à son unique terme (pp)=1\dbinom{p}{p}=1, et le membre de droite vaut (p+1p+1)=1\dbinom{p+1}{p+1}=1.

Hérédité. Supposons la formule acquise au rang n⩾pn\geqslant p. Alors

∑k=pn+1(kp)=(∑k=pn(kp))+(n+1p)=(n+1p+1)+(n+1p),\sum_{k=p}^{n+1}\binom{k}{p}=\left(\sum_{k=p}^{n}\binom{k}{p}\right)+\binom{n+1}{p}=\binom{n+1}{p+1}+\binom{n+1}{p},

par hypothèse de récurrence. La formule du triangle de Pascal, appliquée avec l'entier n+1n+1 à la place de nn, donne précisément

(n+1p)+(n+1p+1)=(n+2p+1),\binom{n+1}{p}+\binom{n+1}{p+1}=\binom{n+2}{p+1},

ce qui est la formule au rang n+1n+1.

Conclusion. L'égalité est vraie pour tout n⩾pn\geqslant p.

Question

Développer (a+b)n(a+b)^n, c'est choisir dans chacune des nn parenthèses soit aa, soit bb, puis regrouper les termes semblables. Le coefficient de akbn−ka^k b^{n-k} compte donc le nombre de façons de désigner les kk parenthèses où l'on a pris aa — c'est-à-dire une partie à kk éléments d'un ensemble à nn éléments. Le lien avec les coefficients binomiaux est-il vraiment aussi direct, et quelle hypothèse ce raisonnement suppose-t-il sur aa et bb ?

Théorème 2 : Formule du binôme de Newton

Soient n∈Nn\in\mathbb{N} et a,ba,b deux éléments qui commutent. Alors

(a+b)n=∑k=0n(nk)akbn−k.(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^k b^{n-k}.

Démonstration :

Les coefficients binomiaux comptent le nombre de façons d'obtenir akbn−ka^k b^{n-k} en choisissant un facteur dans chaque parenthèse du produit développé.

Test 2 : Sans hypothèse de commutation

Pour toutes matrices carrées AA et BB de même taille et tout n∈Nn\in\mathbb{N}, on a (A+B)n=∑k=0n(nk)AkBn−k(A+B)^n=\displaystyle\sum_{k=0}^{n}\binom{n}{k}A^k B^{n-k}.

Question

On sait compter les parties de EE à pp éléments fixé. Mais si l'on veut compter toutes les parties de EE, sans contrainte sur leur taille ? L'ensemble P(E)\mathcal{P}(E) se répartit selon le nombre d'éléments, et chaque paquet est déjà compté : il ne reste plus qu'à sommer. Que vaut cette somme ?

Théorème 3

Si EE est un ensemble fini, alors l'ensemble P(E)\mathcal{P}(E) de ses parties est fini, non vide, et

Card⁡P(E)=2 Card⁡E.\operatorname{Card}\mathcal{P}(E)=2^{\,\operatorname{Card} E}.

Démonstration :

On note n=Card⁡En=\operatorname{Card} E et on suppose n⩾1n\geqslant 1. On énumère les parties de EE selon leur nombre d'éléments : en notant Pk\mathcal{P}_k l'ensemble des parties de EE à kk éléments, on a, pour 0⩽k⩽n0\leqslant k\leqslant n, Card⁡Pk=(nk)\operatorname{Card}\mathcal{P}_k=\dbinom{n}{k}. Or P(E)\mathcal{P}(E) est l'union disjointe de ces ensembles :

P(E)=⨆k=0nPk.\mathcal{P}(E)=\bigsqcup_{k=0}^{n}\mathcal{P}_k.

D'après la formule du binôme de Newton, appliquée avec a=b=1a=b=1,

Card⁡P(E)=∑k=0n(nk)=(1+1)n=2n.\operatorname{Card}\mathcal{P}(E)=\sum_{k=0}^{n}\binom{n}{k}=(1+1)^n=2^n.

C'est également vrai si EE est vide, car alors P(E)={∅}\mathcal{P}(E)=\{\varnothing\}.

Test 3 : Parties d'un ensemble à cinq éléments

Un ensemble à 55 éléments possède exactement 3232 parties, l'ensemble vide et l'ensemble tout entier compris.

Exercice 3 : Autant de parties paires que de parties impaires

Soit EE un ensemble fini de cardinal n⩾1n\geqslant 1. Montrer que le nombre de parties de EE ayant un nombre pair d'éléments est égal au nombre de parties de EE ayant un nombre impair d'éléments, et calculer ce nombre commun.

Solution :(cliquer pour afficher)

Notons A\mathcal{A} l'ensemble des parties de EE de cardinal pair et B\mathcal{B} celui des parties de cardinal impair. En triant les parties selon leur cardinal,

Card⁡A=∑0⩽k⩽nk pair(nk),Card⁡B=∑0⩽k⩽nk impair(nk).\operatorname{Card}\mathcal{A}=\sum_{\substack{0\leqslant k\leqslant n \\ k \text{ pair}}}\binom{n}{k}, \qquad \operatorname{Card}\mathcal{B}=\sum_{\substack{0\leqslant k\leqslant n \\ k \text{ impair}}}\binom{n}{k}.

Appliquons la formule du binôme avec a=−1a=-1 et b=1b=1, qui commutent :

0=(−1+1)n=∑k=0n(nk)(−1)k=Card⁡A−Card⁡B,0=(-1+1)^n=\sum_{k=0}^{n}\binom{n}{k}(-1)^k=\operatorname{Card}\mathcal{A}-\operatorname{Card}\mathcal{B},

puisque (−1)k(-1)^k vaut 11 pour kk pair et −1-1 pour kk impair. On en déduit Card⁡A=Card⁡B\operatorname{Card}\mathcal{A}=\operatorname{Card}\mathcal{B}.

Par ailleurs A\mathcal{A} et B\mathcal{B} sont disjoints de réunion P(E)\mathcal{P}(E), donc

Card⁡A+Card⁡B=2n,\operatorname{Card}\mathcal{A}+\operatorname{Card}\mathcal{B}=2^n,

d'où Card⁡A=Card⁡B=2n−1\operatorname{Card}\mathcal{A}=\operatorname{Card}\mathcal{B}=2^{n-1}.

L'hypothèse n⩾1n\geqslant 1 est indispensable : pour E=∅E=\varnothing, il y a une partie de cardinal pair (∅\varnothing) et aucune de cardinal impair.

Remarque :

Somme ou produit ? Le choix entre addition et multiplication repose sur une question simple : à quelle étape du raisonnement suis-je ?

  • On additionne quand on regroupe des situations incompatibles qui constituent ensemble toutes les possibilités : chaque terme compte les issues d'un cas, et les cas ne se chevauchent pas. Il faut s'assurer de n'en oublier aucun et de ne pas en compter deux fois (principe des cas disjoints, ou formule du crible si les cas se recoupent).
  • On multiplie quand une issue résulte de plusieurs choix successifs ou simultanés indépendants : chaque facteur compte les possibilités d'une partie du tirage, les autres étant fixées. La règle du produit s'applique chaque fois que l'on peut décomposer l'expérience en étapes dont le nombre de choix ne dépend pas des étapes précédentes.