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

icone-math-OS-Exos
exercice 1 facile

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, on a d’après la formule de Pascal :

    \[\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 {\displaystyle \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 {\displaystyle \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 reconnaît une somme télescopique. Il reste :

    \[\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 {\displaystyle \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.

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 :

    \[\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)!}\]

et d’autre part :

    \[\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)!}\]

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 {\displaystyle \binom{r}{q}} façons. Pour chaque tel choix, il existe {\displaystyle \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 {\displaystyle \binom{r}{p}} façons. Pour chaque tel choix, il existe {\displaystyle \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 »

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}}\]

exercice 9 difficile
  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)!
  2. 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 .
  3. 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 {\displaystyle \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 {\displaystyle \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