Solution Exercices Coefficients Binomiaux 02

Solutions détaillées de neuf exercices sur les coefficients binomiaux (fiche 02)
Cliquer ici pour accéder aux énoncés

Dans l’expression développée de $\left(a+2b-c\right)^{9},$ les termes en $a^{4}b^{3}c^{2}$ s’obtiennent en sélectionnant $a$ dans 4 parenthèses, ce qui peut se faire de $\binom{9}{4}$ façons et, pour chaque tel choix, en sélectionnant $2b$ dans 3 parenthèses parmi les 5 restantes, ce qui peut se faire de $\binom{5}{3}$ façons (il reste ensuite 2 parenthèses où l’on doit fatalement sélectionner $-c).$

Le coefficient de $a^{4}b^{3}c^{2}$ dans le développement de $\left(a+2b-c\right)^{9}$ est donc :

$\binom{9}{4}\binom{5}{3}2^{3}\left(-1\right)^{2}=\frac{9\times8\times7\times6}{4\times3\times2}\:\frac{5\times4}{2}\:8=\boxed{10080}$

Pour tout entier $n\geqslant1,$ la formule de Pascal donne :

$\binom{2n}{n}=\binom{2n-1}{n-1}+\binom{2n-1}{n}$

Mais d’après la formule de symétrie :

$\binom{2n-1}{n-1}=\binom{2n-1}{\left(2n-1\right)-\left(n-1\right)}=\binom{2n-1}{n}$

et donc :

$\binom{2n}{n}=2\thinspace\binom{2n-1}{n}$

ce qui prouve la parité de $\binom{2n}{n}.$ Noter que pour $n=0,$ cet entier est impair (il vaut 1).

Remarque

Plus précisément : l’exposant de $2$ dans la décomposition en facteurs premiers de $\binom{2n}{n}$ est égal au nombre de 1 dans l’écriture binaire de $n.$ Cet entier étant non nul puisque $n\geqslant1,$ on retrouve ainsi la parité de ${\displaystyle \binom{2n}{n}}.$ Pour une preuve de ce résultat, voir cet article.

On sait que :

$\binom{n}{k}=\frac{n\left(n-1\right)\cdots\left(n-k+1\right)}{k!}=\prod_{j=0}^{k-1}\frac{n-j}{k-j}$

Si l’on prouve que, pour tout $j\in\llbracket 0,k-1\rrbracket$ :

( $\star$ ) $\frac{n-j}{k-j}\geqslant\frac{n}{k}$

il en résultera que :

$\boxed{\binom{n}{k}\geqslant\left(\frac{n}{k}\right)^{k}}$

Or l’inégalité $\left(\star\right)$ équivaut à :

$\left(n-j\right)k\geqslant n\left(k-j\right)$

donc aussi à $j\left(n-k\right)\geqslant0$ , qui est évidemment vraie.

Soient $n,k$ des entiers tels que $0\leqslant k<n.$ D’après la formule de Pascal :

$\begin{eqnarray*}\sum_{i=0}^{k}\left(-1\right)^{i}\binom{n}{i} & = & 1+\sum_{i=1}^{k}\left(-1\right)^{i}\left[\binom{n-1}{i}+\binom{n-1}{i-1}\right]\\& = & 1+\sum_{i=1}^{k}\left[\left(-1\right)^{i}\binom{n-1}{i}-\left(-1\right)^{i}\binom{n-1}{i-1}\right]\end{eqnarray*}$

On a fait apparaître une sommation télescopique. Au final :

$\sum_{i=0}^{k}\left(-1\right)^{i}\binom{n}{i}=\left(-1\right)^{k}\binom{n-1}{k}$

Remarque

Pour $k=n,$ on trouve $\sum_{i=0}^{n}\left(-1\right)^{i}\binom{n}{i}=\left(1-1\right)^{n}=0.$ La formule obtenue pour $0\leqslant k<n$ s’applique donc aussi lorsque $k=n,$ vu que $\displaystyle{\binom{a}{b}=0}$ si $b>a$ . On retrouve alors le résultat de l’exercice n° 4 de cette fiche.

Notons $S_{p}$ cette somme. On peut la séparer en deux :

$S_{p}=\sum_{k=1}^{p}\left(-1\right)^{k}\binom{2p}{k}+\sum_{k=1}^{p}\left(-1\right)^{k-1}\binom{2p}{k-1}$

puis effectuer, dans la dernière somme, le changement d’indice $j=2p+1-k.$ On obtient :

$S_{p}=\sum_{k=1}^{p}\left(-1\right)^{k}\binom{2p}{k}+\sum_{j=p+1}^{2p}\left(-1\right)^{2p-j}\binom{2p}{2p-j}$

et donc, par symétrie des coefficients binomiaux :

$S_{p}=\sum_{k=1}^{2p}\left(-1\right)^{k}\binom{2p}{k}=-1+\left(1-1\right)^{2p}=-1$

Remarque

On peut aussi exploiter le résultat de l’exercice précédent :

$\begin{eqnarray*}S_{p} & = & \sum_{k=1}^{p}\left(-1\right)^{k}\left[\binom{2p}{k}-\binom{2p}{k-1}\right]\\& = & \sum_{k=1}^{p}\left(-1\right)^{k}\binom{2p}{k}+\sum_{k=0}^{p-1}\left(-1\right)^{k}\binom{2p}{k}\\& = & -1+\sum_{k=0}^{p}\left(-1\right)^{k}\binom{2p}{k}+\sum_{k=0}^{p-1}\left(-1\right)^{k}\binom{2p}{k}\end{eqnarray*}$

d’où la conclusion, puisque les deux dernières sommes valent 0 (d’après l’exercice n° 4).

Si l’on connaît la formule de Stirling :

$n!\sim\left(\frac{n}{e}\right)^{n}\sqrt{2\pi n}$

on voit aussitôt que :

$\binom{2n}{n}=\frac{\left(2n\right)!}{\left(n!\right)^{2}}\sim\frac{\left(\frac{2n}{e}\right)^{2n}\sqrt{4\pi n}}{\left(\left(\frac{n}{e}\right)^{n}\sqrt{2\pi n}\right)^{2}}$

c’est-à-dire :

$\boxed{\binom{2n}{n}\sim\frac{4^{n}}{\sqrt{\pi n}}}$

Commençons par une preuve algébrique (calculatoire … donc pas passionnante). D’une part :

$\begin{eqnarray*}\binom{r}{q}\binom{q}{p}&=&\frac{r!}{q!\:\left(r-q\right)!}\thinspace\frac{q!}{p!\:\left(q-p\right)!}\\&=&\frac{r!}{p!\:\left(q-p\right)!\:\left(r-q\right)!}\end{eqnarray*}$

et d’autre part :

$\begin{eqnarray*}\binom{r}{p}\binom{r-p}{q-p}&=&\frac{r!}{p!\:\left(r-p\right)!}\thinspace\frac{\left(r-p\right)!}{\left(q-p\right)!\:\left[\left(r-p\right)-\left(q-p\right)\right]!}\\&=&\frac{r!}{p!\:\left(q-p\right)!\:\left(r-q\right)!}\end{eqnarray*}$

de sorte que :

$\boxed{\binom{r}{q}\binom{q}{p}=\binom{r}{p}\binom{r-p}{q-p}}$

Passons à une preuve combinatoire. Etant donné un ensemble $E$ de cardinal $r,$ calculons le nombre $N$ de couples $\left(F,G\right)$ de parties de $E$ tels que :

$\text{card}\left(F\right)=q,\quad\text{card}\left(G\right)=p\quad\text{et}\quad G\subset F$

Une première méthode consiste à choisir d’abord $F$ , ce qui peut se faire de $\binom{r}{q}$ façons. Pour chaque tel choix, il existe $\binom{q}{p}$ façons de choisir $G.$ Ainsi :

$N=\binom{r}{q}\binom{q}{p}$

Seconde méthode : on choisit d’abord $G,$ ce qui peut se faire de $\binom{r}{p}$ façons. Pour chaque tel choix, il existe $\binom{r-p}{q-p}$ façons de choisir $F$ (en effet, vu qu’on a déjà choisi $p$ éléments, il faut « entourer » $G$ en sélectionnant $q-p$ éléments parmi les $r-p$ qui restent). Ainsi :

$N=\binom{r}{p}\binom{r-p}{q-p}$

et l’on retrouve bien la formule encadrée.

Remarque

Pour $p=1$ et toujours $1\leqslant q\leqslant r$ , cette formule devient :

$q\binom{r}{q}=r\binom{r-1}{q-1}$

On reconnaît la fameuse « formule du pion » (voir la section 7 de cet article)

Calculons, pour tout entier $p\geqslant1$ :

$J_{p}=\int_{0}^{+\infty}\dfrac{\sin^{2p}\left(t\right)}{t^{2}}\thinspace dt$

Si l’on intègre par parties en posant :

$\begin{eqnarray*}u\left(t\right)=\sin^{2p}\left(t\right) & ; & v'\left(t\right)=\dfrac{1}{t^{2}}\\u'\left(t\right)=2p\sin^{2p-1}\left(t\right)\cos\left(t\right) & ; & v\left(t\right)=-\dfrac{1}{t}\end{eqnarray*}$

il vient :

$J_{p}=2p\int_{0}^{+\infty}\dfrac{\sin^{2p-1}\left(t\right)\cos\left(t\right)}{t}\thinspace dt$

La formule de linéarisation :

$\sin^{2p-1}\left(x\right)=\frac{1}{4^{p-1}}\sum_{k=0}^{p-1}\left(-1\right)^{k}\binom{2p-1}{p-1-k}\sin\left(\left(2k+1\right)x\right)$

donne alors :

$J_{p}=\dfrac{2p}{4^{p-1}}\sum_{k=0}^{p-1}\left(-1\right)^{k}\binom{2p-1}{p-1-k}\int_{0}^{+\infty}\dfrac{\sin\left(\left(2k+1\right)t\right)\cos\left(t\right)}{t}\thinspace dt$

c’est-à-dire, après transformation du produit $\sin\left(\left(2k+1\right)t\right)\cos\left(t\right)$ en somme :

$J_{p}=\dfrac{p}{4^{p-1}}\sum_{k=0}^{p-1}\left(-1\right)^{k}\binom{2p-1}{p-1-k}\int_{0}^{+\infty}\dfrac{\sin\left(\left(2k+2\right)t\right)+\sin\left(2kt\right)}{t}\thinspace dt$

Or on sait (intégrale de Dirichlet) que :

$\int_{0}^{+\infty}\dfrac{\sin\left(t\right)}{t}\thinspace dt=\dfrac{\pi}{2}$

et donc, pour tout $k\in\mathbb{N}$ :

$\int_{0}^{+\infty}\dfrac{\sin\left(\left(2k+2\right)t\right)+\sin\left(2kt\right)}{t}\thinspace dt=\left\{ \begin{array}{cc}\pi & \text{si }k\geqslant1\\\\\dfrac{\pi}{2} & \text{si }k=0\end{array}\right.$

Par conséquent :

$J_{p}=\dfrac{p\pi}{2^{2p-1}}\left[\binom{2p-1}{p-1}+2\sum_{k=1}^{p-1}\left(-1\right)^{k}\binom{2p-1}{p-1-k}\right]$

Dans cette dernière somme, on peut poser $j=p-1-k$ et utiliser le résultat de l’exercice n° 4 :

$\begin{eqnarray*}J_{p} & = & \dfrac{p\pi}{2^{2p-1}}\left[\binom{2p-1}{p-1}+2\left(-1\right)^{p-1}\sum_{j=0}^{p-2}\left(-1\right)^{j}\binom{2p-1}{j}\right]\\& = & \dfrac{p\pi}{2^{2p-1}}\left[\binom{2p-1}{p-1}-2\binom{2p-2}{p-2}\right]\end{eqnarray*}$

En définitive :

$\boxed{J_{p}=\dfrac{\pi}{2^{2p-1}}\binom{2p-2}{p-1}}$

L’application qui, à une chaine $\left(C_{i}\right)_{0\leqslant i\leqslant n},$ associe la permutation $\sigma\in\mathfrak{S}{n}$ définie par
$\forall i\in\left\llbracket 1,n\right\rrbracket ,\thinspace\left\{ \sigma\left(i\right)\right\} =C_{i}-C_{i-1}$
est une bijection. Il existe donc $n!$ chaînes. Soit maintenant $X$ une partie de $E.$ Notons $k=\text{card}\left(X\right).$ Dire que $X$ fait partie d’une chaîne $\left(C_{i}\right)_{0\leqslant i\leqslant n}$ signifie que $C_{k}=X.$ Il existe $k!$ façons de contruire la sous-chaîne $\left(C_{i}\right)_{0\leqslant i\leqslant k}$ puis, pour chaque tel choix, $\left(n-k\right)!$ façons de prolonger celle-ci en une chaîne. Au total, le nombre de chaînes « passant par $X$ » est $k!\thinspace\left(n-k\right)!$
Pour tout $k\in\left\llbracket 0,n\right\rrbracket ,$ l’ensemble des parties de $\left\llbracket 1,n\right\rrbracket$ qui sont de cardinal $k$ est une antichaîne, de cardinal $\binom{n}{k}.$ En particulier pour $k=\left\lfloor \frac{n}{2}\right\rfloor .$
Une majoration :
1. Pour tout $k\in\left\llbracket 0,n\right\rrbracket ,$ notons $\mathcal{A}_{k}=\left\{ X\in\mathcal{A};\thinspace\#X=k\right\} .$ Par définition : $q_{k}=\text{card}\left(\mathcal{A}_{k}\right).$ Comme $\bigsqcup_{k=0}^{n}\mathcal{A}_{k}=\mathcal{A},$ on voit en passant aux cardinaux que :
  ${\displaystyle \sum_{k=0}^{n}q_{k}}=r$
  Pour chaque $k\in\left\llbracket 0,n\right\rrbracket$ et pour chaque élément $X\in\mathcal{A}_{k},$ on considère les $k!\:\left(n-k\right)!$ chaînes qui passent par $X.$ Ceci représente un total de $\sum_{k=0}^{n}q_{k}\thinspace k!\thinspace\left(n-k\right)!$ chaînes, car une même chaîne ne peut pas passer par deux éléments distincts de $\mathcal{A}$ (sans quoi il existerait une relation d’inclusion entre ces deux éléments de $\mathcal{A},$ ce qui est absurde). Ce total étant majoré par le nombre chaînes, il vient :
  $\sum_{k=0}^{n}q_{k}\thinspace k!\thinspace\left(n-k\right)!\leqslant n!$
2. L’inégalité précédente peut s’écrire :
  $\sum_{k=0}^{n}\frac{q_{k}}{\binom{n}{k}}\leqslant1$
  Or, on sait que :
  $\forall k\in\left\llbracket 0,n\right\rrbracket ,\thinspace\binom{n}{k}\leqslant\binom{n}{\left\lfloor \frac{n}{2}\right\rfloor }$
  Il s’ensuit que :
  $\sum_{k=0}^{n}q_{k}\leqslant\binom{n}{\left\lfloor \frac{n}{2}\right\rfloor }$
  c’est-à-dire (cf. 3°-A) :
  $r\leqslant\binom{n}{\left\lfloor \frac{n}{2}\right\rfloor }$
  Compte tenu du 2°, on conclut que le cardinal maximal d’une antichaîne est $\binom{n}{\left\lfloor \frac{n}{2}\right\rfloor }.$

Si un point n’est pas clair ou vous paraît insuffisamment détaillé, n’hésitez pas à poster un commentaire ou à me joindre via le formulaire de contact.

Partager cet article