Principales propriétés des coefficients binomiaux

article-prépa-scientifique

Cet article présente l’essentiel de ce qu’il faut savoir au sujet des coefficients binomiaux, au niveau des deux premières années d’enseignement supérieur.

Ces entiers, qui doivent leur nom à la formule du binôme (cf. section 6 plus bas) interviennent dans une foule de problèmes mathématiques, notamment en combinatoire et en arithmétique.

Le sujet étant vaste, nous devons nous limiter à quelques unes des propriétés les plus simples et / ou les plus fréquemment rencontrées.

 

1 – Préambule et notations

Pour tout entier naturel n, on désigne par \mathbb{N}_{n} l’ensemble des entiers k vérifiant 1\leqslant k\leqslant n. Avec cette définition : \mathbb{N}_{0}=\emptyset.

Un ensemble E est dit fini lorsqu’il existe un entier naturel n et une bijection de \mathbb{N}_{n} vers E. On peut montrer l’unicité d’un tel n : c’est le cardinal de E, noté \text{card}\left(E\right). Intuitivement, \text{card}\left(E\right) indique le nombre d’éléments de E.

On peut montrer (nous l’admettrons ici) que si E est fini de cardinal n, alors toute partie A de E est aussi finie et \text{card}\left(A\right)\leqslant n, avec égalité si, et seulement si, A=E.

On sait que la composée de deux bijections est une bijection. Il en résulte aussitôt qu’étant donnés deux ensembles E et F, si E est fini et s’il existe une bijection de E vers F, alors F est fini et \text{card}\left(E\right)=\text{card}\left(F\right).
On note classiquement \mathcal{P}\left(E\right) l’ensemble des parties d’un ensemble E.
Si E est fini et k\in\mathbb{N}, on note \mathcal{P}_{k}\left(E\right) la partie de \mathcal{P}\left(E\right) constituée des parties de E de cardinal k.

Il est donc clair que :

  • \mathcal{P}_0(E)=\{\emptyset\}
  • \mathcal{P}_{\text{card}\left(E\right)}\left(E\right)=\left\{ E\right\}
  • si k>\text{card}\left(E\right), alors \mathcal{P}_{k}\left(E\right)=\emptyset

Nous aurons enfin à utiliser le « principe additif » suivant : si E,F sont deux ensembles finis et disjoints, alors E\cup F est fini et :

    \[ \text{card}\left(E\cup F\right)=\text{card}\left(E\right)+\text{card}\left(F\right) \]

Plus généralement, si E_{1},\cdots,E_{p} sont des ensembles finis deux à deux disjoints, alors :

    \[ \text{card}\left(\bigcup_{i=1}^{p}E_{i}\right)=\sum_{i=1}^{p}\text{card}\left(E_{i}\right) \]

 

2 – Définition combinatoire des coefficients binomiaux

Soient n et k deux entiers naturels tels que 0\leqslant k\leqslant n. On pose, par définition :

    \[ \binom{n}{k}=\text{card}\left(\mathcal{P}_{k}\left(\mathbb{N}_{n}\right)\right) \]

Le membre de gauche de cette égalité se lit « k parmi n ».

En d’autres termes, \displaystyle{\binom{n}{k}} désigne le nombre de parties de \mathbb{N}_{n} qui sont de cardinal k.

Si E est de cardinal n, il est facile de voir que les ensembles \mathcal{P}_{k}\left(E\right) et \mathcal{P}_{k}\left(\mathbb{N}_{n}\right) sont équipotents (c’est-à-dire qu’il existe une bijection de l’un vers l’autre); il en résulte que :

\displaystyle{\binom{n}{k}} désigne le nombre de parties de cardinal k dans un ensemble de cardinal n
A titre d’exemple, calculons \displaystyle{\binom{4}{2}}.Pour cela, considérons un ensemble à quatre éléments, que nous noterons E=\left\{ a,b,c,d\right\} et énumérons ses parties de cardinal 2 :

    \[ \left\{ a,b\right\} ,\;\left\{ a,c\right\} ,\:\left\{ a,d\right\} ,\:\left\{ b,c\right\} ,\:\left\{ b,d\right\} ,\:\left\{ c,d\right\} \]

Manifestement, il en existe six. Par conséquent :\displaystyle{\binom{4}{2}=6}.

Cependant, cette méthode d’énumération exhaustive atteint très vite ses limites ! Si l’on voulait faire de même pour calculer \displaystyle{\binom{20}{10}}, il faudrait dresser la liste complète des parties de cardinal 10 dans un ensemble de cardinal 20, ce qui est difficilement imaginable quand on sait (voir la formule de Fermat, section 5) que :

    \[ \binom{20}{10}=184\thinspace756 \]

Et ne parlons pas de :

    \[ \binom{60}{30}=118\thinspace264\thinspace581\thinspace564\thinspace861\thinspace424 \]

Même si nous étions capables de passer en revue les parties de cardinal 30 d’un ensemble de cardinal 60, à raison d’une par seconde, sans jamais faire de pause, il ne nous faudrait pas moins de 37 milliards d’années pour en venir à bout !!

Une formule pour le calcul direct de \displaystyle{\binom{n}{k}} s’avère donc nécessaire. Nous l’obtiendrons à la section 5.

 

3 – Formule de symétrie

Choisir k éléments parmi n, revient à en sélectionner n-k éléments qui ne seront pas choisis. Ces n-k éléments, qui sont mis de côté, sont donc – en un sens – « choisis » eux aussi ! Il n’est donc pas surprenant qu’on ait :

    \[ \forall n\in\mathbb{N},\thinspace\forall k\in\left\{ 0,\cdots,n\right\} ,\:\binom{n}{k}=\binom{n}{n-k} \]

C’est la formule de symétrie des coefficients binomiaux.

Donnons un argument plus « rigoureux » pour justifier cela…

Soit E un ensemble de cardinal n. Pour chaque partie A de E, notons \overline{A} le complémentaire de A dans E et considérons les applications :

    \[ \varphi:\mathcal{P}_{k}\left(E\right)\rightarrow\mathcal{P}_{n-k}\left(E\right),\thinspace A\mapsto\overline{A} \]

et

    \[ \psi:\mathcal{P}_{n-k}\left(E\right)\rightarrow\mathcal{P}_{k}\left(E\right),\thinspace A\mapsto\overline{A} \]

Comme le complémentaire du complémentaire d’une partie A n’est autre que A, il est clair que :

    \[ \psi\circ\varphi=id_{\mathcal{P}_{k}\left(E\right)}\qquad\text{et}\qquad\varphi\circ\psi=id_{\mathcal{P}_{n-k}\left(E\right)} \]

Il s’ensuit que \varphi et \psi sont des bijections (et que chacune est la réciproque de l’autre). En particulier, \mathcal{P}_{k}\left(E\right) et \mathcal{P}_{n-k}\left(E\right) sont équipotents, d’où la formule.

 

4 – Formule de Pascal

Soient n,k deux entiers naturels tels que n\geqslant 1 et 0\leqslant k\leqslant n-1. Considérons un ensemble E de cardinal n+1 ainsi qu’un élément particulier de E, que nous notons x. Les parties de E de cardinal k+1, qui sont au nombre de \displaystyle{\binom{n+1}{k+1}}, peuvent être classées en deux catégories :

  • celles qui contiennent x,
  • celles qui ne contiennent pas x.

Les premières sont les parties de cardinal k+1 de E-\left\{ x\right\}. Il en existe \displaystyle{\binom{n}{k+1}}.

Les autres s’obtiennent en ajoutant x à une partie de cardinal k de E-\left\{ x\right\} : il en existe donc autant que de parties de cardinal k de E-\left\{ x\right\}, c’est-à-dire \displaystyle{\binom{n}{k}}.

Ce raisonnement prouve, via le principe additif, que :

    \[ \forall n\geqslant1,\,\forall k\in\{0,\cdots,n-1\},\,\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k} \]

C’est la formule de Pascal, qui permet de construire un tableau à double-entrée, appelé « triangle de Pascal » et qui renferme les valeurs des coefficients binomiaux.

La valeur de \displaystyle{\binom{n}{k}} est placée à l’intersection de la ligne n et de la colonne k.
Comme \displaystyle{\binom{n}{0}=\binom{n}{n}=1} pour tout n\in\mathbb{N}, on place au préalable des ‘1’ sur la colonne 0 et sur la diagonale.
Ensuite, on utilise la formule encadrée pour « garnir » la table, ligne par ligne.

L’animation suivante montre le remplissage du triangle de Pascal, jusqu’à la ligne 8 :

triangle-pascal-anime

 

5 – Formule de Fermat

Nous sommes maintenant en mesure d’établir une formule adaptée au calcul direct de \displaystyle{\binom{n}{k}}.
Il s’agit de la « formule de Fermat » :

    \[ \forall n\in\mathbb{N},\thinspace\forall k\in\left\{ 0,\cdots,n\right\} ,\:\binom{n}{k}=\frac{n!}{k!\left(n-k\right)!} \]

Si la notion de factorielle vous est peu familière, je vous suggère la lecture des articles suivants :

La formule encadrée se prouve par récurrence sur n. Pour n=0, il est clair que :

    \[ \binom{0}{0}=1=\frac{0!}{0!\:\left(0-0\right)!} \]

ce qui amorce la récurrence.
Supposons ensuite que, pour un certain n\in\mathbb{N}, on ait pour tout k\in\left\{ 0,\cdots,n\right\} :

    \[ \binom{n}{k}=\frac{n!}{k!\left(n-k\right)!} \]

Alors, pour tout k\in\mathbb{N}_{n} :

    \begin{eqnarray*} \binom{n+1}{k} & = & \binom{n}{k}+\binom{n}{k-1}\\ \\ & = & \frac{n!}{k!\left(n-k\right)!}+\frac{n!}{\left(k-1\right)!\left(n-k+1\right)!}\\ \\ & = & \frac{n!}{\left(k-1\right)!\left(n-k\right)!}\left[\frac{1}{k}+\frac{1}{n-k+1}\right]\\ \\ & = & \frac{n!}{\left(k-1\right)!\left(n-k\right)!}\:\frac{n+1}{k\left(n-k+1\right)}\\ \end{eqnarray*}

c’est-à-dire, comme souhaité :

    \[ \binom{n+1}{k}=\frac{\left(n+1\right)!}{k!\left(n+1-k\right)!} \]

Cette égalité est encore vraie pour k=0 et pour k=n+1, et la formule de Fermat est donc établie.

Pour les calculs numériques, il est pratique d’en utiliser la version simplifiée suivante :

    \[ \forall n\in\mathbb{N}^{\star},\thinspace\forall k\in\mathbb{N}_{n},\quad\binom{n}{k}=\frac{n\left(n-1\right)\cdots\left(n-k+1\right)}{k!} \]

On retiendra que le numérateur et le dénominateur de cette fraction sont chacun le produit de k entiers consécutifs. Ceci peut aider à mémoriser la formule correcte.

Ainsi, par exemple :

    \[ \binom{16}{6}=\frac{16\times15\times14\times13\times12\times11}{6\times5\times4\times3\times2\times1}=4\times14\times13\times11=8\thinspace008 \]

Autre exemple : une grille de loto comporte 49 numéros, parmi lesquels 6 sont choisis par le joueur. Le nombre de possibilités qui s’offrent à lui est :

    \[ \binom{49}{6}=\frac{49\times48\times47\times46\times45\times44}{6\times5\times4\times3\times2\times1}=49\times47\times46\times3\times44=13\thinspace983\thinspace816 \]

Remarquons, pour conclure cette section, que la formule de Fermat exprime une propriété arithmétique intéressante en soi, à savoir qu’étant donné un entier k\geqslant2, tout produit de k entiers consécutifs est multiple de la factorielle de k. En effet, étant donné N\in\mathbb{N} :

    \[ \left(N+1\right)\cdots\left(N+k\right)=k!\:\binom{N+k}{k} \]

Pour plus de détails au sujet de cette propriété, je vous invite à lire l’article (n+1)(n+2)…(n+k) est multiple de k!
 

6 – Formule du binôme de Newton

Au collège, nous avons appris à développer \left(a+b\right)^{2}.
La formule du binôme généralise ce calcul au cas d’un exposant quelconque :

    \[ \forall(a,b)\in\mathbb{C}^2,\,\forall n\in\mathbb{N},\,\left(a+b\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k} \]

Commençons par en donner une preuve combinatoire.

En développant « brutalement » l’expression \left(a+b\right)^{n}, on obtient 2^{n} termes, qui sont tous de la forme a^{k}b^{n-k} pour un certain k\in\left\{ 0,\cdots,n\right\}.

Pour une valeur donnée de k, combien de fois le terme a^{k}b^{n-k} apparaît-il ? C’est simple : il suffit de voir que, pour obtenir ce terme, on doit sélectionner la lettre a dans k facteurs et la lettre b dans les n-k autres, ce qui peut se faire de \displaystyle{\binom{n}{k}} façons.

Un exemple :
 
Si n=6 et k=2, le terme a^{2}b^{4} sera obtenu en choisissant deux facteurs parmi les six : on y sélectionnera le terme a, tandis que dans les quatre autres, on sélectionnera le terme b. Enumérons les possibilités (les deux facteurs sélectionnés sont représentés en rouge) :

(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)
(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)
(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)
etc …
(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)
(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)
(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)

Bref : il existe \display{\binom{6}{2}}=15 possibilités. L’expression développée de \left(a+b\right)^{6} comporte donc, après regroupement des termes identiques, le terme a^{2}b^{6} affecté d’un coefficient 15.

Pour chaque k\in\left\{ 0,\cdots,n\right\} , le terme a^{k}b^{n-k} apparaît donc \displaystyle{\binom{n}{k}} fois dans le développement de \left(a+b\right)^{n}. La formule du binôme en résulte.

On peut aussi envisager une démonstration par récurrence…

Etant donnés a,b\in\mathbb{C}, on considère l’assertion :

    \[ \left(\mathcal{A}_{n}\right)\::\qquad\qquad\left(a+b\right)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k} \]

\left(\mathcal{A}_{0}\right) est vraie, puisque :

    \[ \left(a+b\right)^{0}=1=\binom{0}{0}\,a^{0}\,b^{0-0} \]

Supposons \left(\mathcal{A}_{n}\right) vraie pour un certain n\in\mathbb{N}. Alors :

    \begin{eqnarray*} \left(a+b\right)^{n+1} & = &\left(a+b\right)\left(a+b\right)^{n}\\ \\ & = & \left(a+b\right)\sum_{k=0}^{n}\,\binom{n}{k}a^{k}b^{n-k}\\ \\ & = & \sum_{k=0}^{n}\,\binom{n}{k}a^{k+1}b^{n-k}\,+\,\sum_{k=0}^{n}\,\binom{n}{k}a^{k}b^{n+1-k} \end{eqnarray*}

Si l’on effectue dans la première somme le changement d’indice j=k+1, il vient :

    \begin{eqnarray*} \left(a+b\right)^{n+1} & = & \sum_{j=1}^{n+1}\,\binom{n}{j-1}a^{j}b^{n+1-j}+\sum_{j=0}^{n}\,\binom{n}{j}a^{j}b^{n+1-j}\\ \\ & = & a^{n+1}+b^{n+1}+\sum_{j=1}^{n}\,\left[\binom{n}{j-1}+\binom{n}{j}\right]a^{j}b^{n+1-j}\\ \\ & = & a^{n+1}+b^{n+1}+\sum_{j=1}^{n}\binom{n+1}{j}a^{j}b^{n+1-j}\\ \\ & = & \sum_{j=0}^{n+1}\,\binom{n+1}{j}a^{j}b^{n+1-j} \end{eqnarray*}

L’avant-dernière égalité résulte de la formule de Pascal. La dernière s’obtient en ré-insérant les termes a^{n+1} et b^{n+1} dans le \Sigma (ils correspondent respectivement à j=n+1 et à j=0). L’assertion \left(\mathcal{A}_{n+1}\right) est donc établie, ce qui achève la démonstration.

 

7 – Formule du pion

On appelle parfois « formule du pion » l’égalité :

    \[ k\binom{n}{k}=n\binom{n-1}{k-1} \]

valable pour tout couple \left(n,k\right) d’entiers naturels tels que 1\leqslant k\leqslant n.

Cette appellation est sans doute due à une vague analogie avec le jeu d’échec : lorsqu’un pion attaque un pion adverse, il se déplace d’une case en diagonale (disons depuis la case située à l’intersection de la ligne n et de la colonne k, vers celle située à l’intersection de la ligne n-1 et de la colonne k-1), comme l’indique le schéma ci-dessous :

echecs-et-formule-du-pion

Cette formule peut être établie de deux manières : par un calcul ou bien par un raisonnement combinatoire.

Avec la formule de Fermat, on voit facilement que :

    \begin{eqnarray*} k\binom{n}{k} & = & k\:\frac{n!}{k!\left(n-k\right)}\\ \\ & = & \frac{n\left(n-1\right)!}{\left(k-1\right)!\left[\left(n-1\right)-\left(k-1\right)\right]!}\\ \\ & = & n\binom{n-1}{k-1} \end{eqnarray*}

Mais le point de vue combinatoire est clairement plus instructif…

Etant donné un ensemble E de cardinal n et un entier k tel que 1\leqslant k\leqslant n, on va dénombrer les couples \left(X,a\right) tels que :

    \[ X\in\mathcal{P}_{k}\left(E\right)\qquad\text{et}\qquad a\in X \]

Pour cela, on peut choisir d’abord X de \displaystyle{\binom{n}{k}} façons, puis choisir a\in X de k façons : au total, on trouve \displaystyle{k\binom{n}{k}} couples.Une autre méthode consiste à choisir d’abord a\in E de n façons, puis à « l’entourer » de k-1 éléments choisis dans E-\left\{ a\right\}, et ce de \displaystyle{\binom{n-1}{k-1}} façons : au total, on trouve \displaystyle{n\binom{n-1}{k-1}} couples.La formule du pion en résulte !

Vous en trouverez un exemple d’utilisation dans la vidéo Calcul de sommes – 01.

L’illustration ci-dessous permet de visualiser les deux manières de compter :

preuve-combinatoire-formule-du-pion

 

8 – Formule de Vandermonde

Considérons un ensemble E de cardinal 2n. Le nombre de parties de E qui sont de cardinal n est, par définition \displaystyle{q_{n}=\binom{2n}{n}}. Mais on peut raisonner autrement.

On commence par fixer deux parties complémentaires et de même cardinal n (autrement dit : on place une « cloison » dans E). Se donner une partie de E de cardinal n revient alors à choisir, pour un certain k\in\left\{ 0,\cdots,n\right\}, k éléments d’un côté de la cloison et n-k éléments de l’autre. La figure ci-dessous montre l’une des \displaystyle{\binom{56}{12}} manières de choisir 12 objets parmi 56 :

visualisation-12-parmi-56

 

Pour k donné, le nombre de ces double-choix est \displaystyle{\binom{n}{k}\binom{n}{n-k}}, c’est-à-dire \displaystyle{\binom{n}{k}^{2}}. En ajoutant ces possibilités (qui s’excluent mutuellement, ce qui autorise l’usage du principe additif mentionné à la section 1), il vient :

    \[ q_{n}=\sum_{k=0}^{n}\binom{n}{k}^{2} \]

Par conséquent :

    \[ \forall n\in\mathbb{N},\thinspace\sum_{k=0}^{n}\binom{n}{k}^{2}=\binom{2n}{n} \]

On peut aisément généraliser : pour dénombrer les parties d’un ensemble F de cardinal a+b qui sont de cardinal n (avec 0\leqslant n\leqslant a+b). On cloisonne F en deux parties de cardinaux respectifs a et b puis, en raisonnant comme ci-dessus, on parvient la « formule de Vandermonde » :

    \[ \boxed{\forall\left(a,b\right)\in\mathbb{N}^{2},\:\forall n\in\left\{ 0,\cdots,a+b\right\} ,\thinspace\sum_{k=\max\left\{ 0,n-b\right\} }^{\min\left\{ a,n\right\} }\binom{a}{k}\binom{b}{n-k}=\binom{a+b}{n}} \]

Si l’on convient que \displaystyle{\binom{j}{i}=0} dès que i<0 ou i>j, cette formule s’écrit plus simplement :

    \[ \forall\left(a,b\right)\in\mathbb{N}^{2},\:\forall n\in\left\{ 0,\cdots,a+b\right\} ,\thinspace\sum_{k=0}^{n}\binom{a}{k}\binom{b}{n-k}=\binom{a+b}{n} \]

En voici une illustration « concrète ». Etant donné un jeu de 32 cartes, on peut compter le nombres de « mains » (une main est un ensemble de 5 cartes extraites du jeu) : il en existe évidemment \displaystyle{\binom{32}{5}}. Si l’on note N_{k} le nombre de mains comportant exactement k rois (pour 0\leqslant k\leqslant4), on voit que :

    \[ N_{0}=\binom{28}{5}\qquad N_{1}=\binom{4}{1}\binom{28}{4}\qquad N_{2}=\binom{4}{2}\binom{28}{3}\qquad N_{3}=\binom{4}{3}\binom{28}{2}\qquad N_{4}=\binom{28}{1} \]

Par exemple, N_{2} se calcule en considérant que, pour former une main comportant exactement deux rois, il faut choisir deux cartes parmi les quatre rois ainsi que trois cartes parmi les 28 qui restent (celles qui ne sont pas des rois). En notant \mathcal{M} l’ensemble des mains et \mathcal{R}_{k} celui des mains comportant exactement k rois, il est alors clair que :

    \[ \mathcal{R}_{0}\cup\mathcal{R}_{1}\cup\mathcal{R}_{2}\cup\mathcal{R}_{3}\cup\mathcal{R}_{4}=\mathcal{M}\qquad\text{(union disjointe)} \]

d’où, en passant aux cardinaux :

    \[ N_{0}+N_{1}+N_{2}+N_{3}+N_{4}=\binom{32}{5} \]

ce qui correspond à la formule de Vandermonde pour a=4, b=28 et n=5.

 

9 – Somme d’une colonne dans le triangle de Pascal

Reprenons le triangle de Pascal et examinons ce qui se passe lorsqu’on ajoute les termes d’une colonne, depuis le terme diagonal (qui vaut 1) jusqu’à une certaine profondeur.

somme-colonne-35somme-colonne-56

 
Après quelques essais, on conjecture qu’une telle somme est égale au coefficient binomial situé « en-dessous, à droite » de la colonne considérée. Plus formellement :

    \[ \forall p\in\mathbb{N},\:\forall n\geqslant p,\;\sum_{k=p}^{n}\binom{k}{p}=\binom{n+1}{p+1} \]

Ceci se prouve aisément au moyen d’une sommation télescopique (pour savoir ce qu’est une “sommation télescopique”, voir l’article : Manipulation de sommes à l’aide du symbole ∑)

 

    \begin{eqnarray*} \sum_{k=p}^{n}\binom{k}{p} & = & 1+\sum_{k=p+1}^{n}\binom{k}{p}\\ \\ & = & 1+\sum_{k=p+1}^{n}\left[\binom{k+1}{p+1}-\binom{k}{p+1}\right]\\ \\ & = & 1+\binom{n+1}{p+1}-\binom{p+1}{p+1}\\ \ & = & \binom{n+1}{p+1} \end{eqnarray*}

Là encore, il est intéressant d’interpréter le résultat de manière combinatoire.

Notons S_{q,m} l’ensemble des applications strictement croissantes de \mathbb{N}_{q} vers \mathbb{N}_{m}, pour 1\leqslant q\leqslant m. Une telle application est parfaitement déterminée par la donnée d’une partie de \mathbb{N}_{m} de cardinal q : en effet, connaissant les éléments atteints, le plus petit d’entre-eux sera l’image de 1, celui immédiatement supérieur sera l’image de 2, etc … Il s’ensuit que :

    \[ \text{card}\left(S_{q,m}\right)=\binom{m}{q} \]

Changeons de point de vue… Pour f\in S_{q,m}, le maximum de f – c’est-à-dire le plus grand des nombres f\left(1\right),\cdots,f\left(q\right) – est un entier M compris (au sens large) entre q et m. Etant donné un tel entier M, il existe \displaystyle{\binom{M-1}{q-1}} éléments de S_{q,m} dont le maximum est M. En effet, se donner un application strictement croissante de \mathbb{N}_{q} vers \mathbb{N}_{m} ayant M pour maximum, équivaut à se donner une application strictement croissante de \mathbb{N}_{q-1} vers \mathbb{N}_{M-1}.En appliquant le principe additif, on voit ainsi que :

    \[ \text{card}\left(S_{q,m}\right)=\sum_{M=q}^{m}\binom{M-1}{q-1} \]

d’où l’égalité :

    \[ \sum_{M=q}^{m}\binom{M-1}{q-1}=\binom{m}{q} \]

Pour retrouver la formule encadrée plus haut, il suffit de remplacer \left(q,m\right) par \left(p+1,n+1\right) et d’effectuer le changement d’indice défini par k=M-1.

 

10 – Coefficients binomiaux et nombres de Fibonacci

Reprenons le triangle de Pascal et ajoutons cette fois les termes d’une diagonale ascendante, comme indiqué sur la figure ci-dessous :

triangle-de-Pascal-et-Fibonacci

 

On voit apparaître une suite, qui commence par : 1, 1, 2, 3, 5, 8, 13, 21, 55, 89, 144, …

Vous aurez probablement reconnu les premiers termes de la célèbre suite de Fibonacci. Rappelons que cette suite est définie par :

    \[ F_{0}=0\qquad F_{1}=1\qquad\forall n\in\mathbb{N}^{\star},\thinspace F_{n+1}=F_{n}+F_{n-1} \]

Cette observation nous amène à conjecturer que :

    \[ \forall n\in\mathbb{N}^{\star},\:\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\binom{n-k}{k}=F_{n+1} \]

On peut démontrer ceci à l’aide d’une récurrence d’ordre 2. L’égalité se vérifie sans peine pour n\in\left\{ 0,1\right\}. Supposons-la vraie pour aux rangs n-1 et n, pour un certain entier n\geqslant1 et montrons qu’alors :

    \[ \sum_{k=0}^{\left\lfloor \frac{n+1}{2}\right\rfloor }\binom{n+1-k}{k}=F_{n+2} \]

Pour cela, distinguons deux cas, selon la parité de n+1.Si n+1 est pair, on voit en posant n+1=2p+2 et en invoquant pour commencer la formule de Pascal, que :

    \begin{eqnarray*} \sum_{k=0}^{p+1}\binom{2p+2-k}{k} & = & \binom{2p+2}{0}+\sum_{k=1}^{p}\left[\binom{2p+1-k}{k}+\binom{2p+1-k}{k-1}\right]+\binom{p+1}{p+1}\\ \\ & = & \left[1+\sum_{k=1}^{p}\binom{2p+1-k}{k}\right]+\left[1+\sum_{j=0}^{p-1}\binom{2p-j}{j}\right]\qquad\text{(Poser }j=k-1\text{)}\\ \\ & = & \sum_{k=0}^{p}\binom{2p+1-k}{k}+\sum_{k=0}^{p}\binom{2p-k}{k}\\ \\ & = & \sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\binom{n-k}{k}+\sum_{k=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor }\binom{n-1-k}{k}\\ \\ & = & F_{n}+F_{n-1}\qquad\text{(hypothèse de récurrence)}\\ \\ & = & F_{n+1} \end{eqnarray*}

Si n+1 est impair, on pose cette fois n+1=2p+1 et le calcul est similaire :

    \begin{eqnarray*} \sum_{k=0}^{p}\binom{2p+1-k}{k} & = & 1+\sum_{k=1}^{p}\left[\binom{2p-k}{k}+\binom{2p-k}{k-1}\right]\\ \\ & = & \left[1+\sum_{k=1}^{p}\binom{2p-k}{k}\right]+\sum_{j=0}^{p-1}\binom{2p-1-j}{j}\\ \\ & = & \sum_{k=0}^{p}\binom{2p-k}{k}+\sum_{k=0}^{p-1}\binom{2p-1-k}{k}\\ \\ & = & \sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\binom{n-k}{k}+\sum_{k=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor }\binom{n-1-k}{k}\\ \\ & = & F_{n}+F_{n-1}\\ \\ & = & F_{n+1} \end{eqnarray*}

La proposition est établie.

Donnons-en maintenant une lecture combinatoire…

Imaginons un petite grenouille, confortablement installée au pied d’un escalier. Elle doit le gravir, mais en respectant une consigne : elle ne peut effectuer que des sauts dirigés vers le haut de l’escalier et ne franchit qu’une marche ou deux à chaque fois.

escalier-grenouille

 
De combien de façons la grenouille peut-elle gravir l’escalier ? Notons u_{n} la réponse, qui dépend bien sûr du nombre n de marches …

On calcule facilement u_{n} « à la main » pour les petites valeurs de n :

 
Ces quelques observations suggèrent la formule générale :

    \[ \boxed{\forall n\in\mathbb{N}^{\star},\,u_{n}=F_{n+1}}\qquad\left(\spadesuit\right) \]

Celle-ci se prouve à l’aide d’une récurrence d’ordre 2.

Manifestement : u_{1}=1=F_{2}, u_{2}=2=F_{3}. Supposons (hypothèse de récurrence) que u_{n-1}=F_{n} et u_{n}=F_{n+1}.

Etant donné un escalier de n+1 marches (avec n\geqslant2), il existe u_{n-1} manières de le gravir en terminant par un saut de deux marches, et il en existe u_{n} autres se terminant par le franchissement d’une seule marche. Au total : u_{n+1}=u_{n-1}+u_{n}=F_{n}+F_{n+1}=F_{n+2}, comme souhaité.

Changeons maintenant de point de vue pour le calcul de u_n. Etant donné un entier naturel k, considérons le nombre de façons de gravir un escalier de n marches, en effectuant exactement k sauts de deux marches (ce qui impose 2k\leqslant n).
Le nombre total de sauts effectués est alors : k+\left(n-2k\right)=n-k. Une telle façon de gravir l’escalier s’identifie à un mot de n-k lettres, chaque lettre pouvant être ‘1’ ou ‘2’ et le mot comportant un total de k lettres ‘2’ : il existe \displaystyle{\binom{n-k}{k}} tels mots. Le nombre de façons de gravir l’escalier est donc :

    \[ \boxed{\forall n\in\mathbb{N}^{\star},\,u_{n}=\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\,\binom{n-k}{k}}\qquad\left(\clubsuit\right) \]

En confrontant (\spadesuit) et (\clubsuit), nous retrouvons le fait que :

    \[ \sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor }\,\binom{n-k}{k}=F_{n+1} \]

 


 

J’espère que cet article vous aura été utile 🙂
Merci de me laisser un commentaire pour toute remarque ou question.

Partager cet article
  •  
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu