7.7 Applications des récurrences

Le problème de la tour de Hanoï

Le problème mathématique des tours de Hanoï a été inventé par Édouard Lucas. Il est publié dans le tome 3 de ses Récréations mathématiques, parues à titre posthume en 1892. Le problème consiste à déplacer des disques de diamètres différents d’une tour de départ à une tour d’arrivée en passant par une tour intermédiaire, et ceci en un minimum de coups, tout en respectant les règles suivantes :

  1. 1.
    ​

    On ne peut déplacer plus d’un disque à la fois ;

  2. 2.
    ​

    On ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

  3. 3.
    ​

    On suppose que cette dernière règle est également respectée dans la configuration de départ.

La question est alors combien de coup est nécessaire pour résoudre le problème avec n\displaystyle n disques de départ.

[Uncaptioned image]

Il existe plusieurs méthodes pour résoudre ce problème. Dans tous les cas, le problème revient à trouver premièrement une relation de récurrence d’écrivant le problème. C’est ce que nous ferons premièrement. Pour ce faire, remarquons que si nous avons un seul disque, un seul coup est nécessaire. Si nous avons deux disques, il s’agit de déplacer le petit disque sur la tour intermédiaire, on déplace ensuite le plus grand disque sur la tour finale, puis on déplace le petit disque sur la tour finale. Donc trois coups sont nécessaires. Maintenant, si nous avons n\displaystyle n disques, nous devons commencer par déplacer les n−1\displaystyle n-1 plus petits disques sur la tour intermédiaire, plus on déplace le plus grand disque sur la tout finale, et finalement on déplace les n−1\displaystyle n-1 plus petit disque sur la tour finale. Donc si on dénote le nombre de coup nécessaire pour déplacer n\displaystyle n disque par Hn\displaystyle H_{n}, on obtient donc la relation suivante:

Hn=Hn−1+1+Hn−1=2⁢Hn−1+1,∀n≥2\displaystyle H_{n}=H_{n-1}+1+H_{n-1}=2H_{n-1}+1,\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 2

Donc à partir de la valeur de H1\displaystyle H_{1} que nous avons trouvé, on peut ensuite calculer la valeur de Hn\displaystyle H_{n} pour chaque entier positif n\displaystyle n. On obtient donc le tableau suivant:

n\displaystyle n 1 2 3 4 5 6 7
Hn\displaystyle H_{n} 1 3 7 15 31 63 127

Nous allons maintenant étudier différente approche pour résoudre cette récurrence.

L’induction: En observant les valeurs obtenues dans notre tableau, on est amener à faire l’hypothèse que Hn=2n−1\displaystyle H_{n}=2^{n}-1. Pour le démontrer, on utilise l’induction. On a donc:

  1. 1.
    ​

    Si n=1\displaystyle n=1, nous avons 21−1=1\displaystyle 2^{1}-1=1, ce qui correspond à la valeur que nous avions calculer.

  2. 2.
    ​

    Supposons que notre formule est vrai pour n=k\displaystyle n=k, c’est à dire supposons que Hk=2k−1\displaystyle H_{k}=2^{k}-1.

  3. 3.
    ​

    Si n=k+1\displaystyle n=k+1, on obtient alors:

    Hk+1\displaystyle\displaystyle H_{k+1} =\displaystyle\displaystyle= 2⁢Hk+1\displaystyle\displaystyle 2H_{k}+1
    =\displaystyle\displaystyle= 2⁢(2k−1)+1\displaystyle\displaystyle 2\left(2^{k}-1\right)+1
    =\displaystyle\displaystyle= 2k+1−2+1\displaystyle\displaystyle 2^{k+1}-2+1
    =\displaystyle\displaystyle= 2k+1−1\displaystyle\displaystyle 2^{k+1}-1

Par induction, on peut donc affirmer que notre formule est correcte. La solution du problème des tour de Hanoi est donc Hn=2n−1\displaystyle H_{n}=2^{n}-1.

Les sommes géométriques: Une deuxième approche pour résoudre notre récurrence consiste à essayer de la développer, tout en espérant pour obtenir une forme que nous connaissons déjà. En commençant à nouveau avec notre suite définie par récurrence, nous avons les égalités suivantes:

Hn\displaystyle\displaystyle H_{n} =\displaystyle\displaystyle= 2⁢Hn−1+1=2⁢(2⁢Hn−2+1)+1=22⁢Hn−2+2+1\displaystyle\displaystyle 2H_{n-1}+1=2\left(2H_{n-2}+1\right)+1=2^{2}H_{n-2}+% 2+1
=\displaystyle\displaystyle= 22⁢(2⁢Hn−3+1)+2+1=23⁢Hn−3+22+2+1\displaystyle\displaystyle 2^{2}\left(2H_{n-3}+1\right)+2+1=2^{3}H_{n-3}+2^{2}% +2+1
=\displaystyle\displaystyle= 23⁢(2⁢Hn−4+1)+22+2+1=24⁢Hn−4+23+22+2+1\displaystyle\displaystyle 2^{3}\left(2H_{n-4}+1\right)+2^{2}+2+1=2^{4}H_{n-4}% +2^{3}+2^{2}+2+1
=\displaystyle\displaystyle= …\displaystyle\displaystyle...
=\displaystyle\displaystyle= 2n−1+2n−2+…+23+22+2+1(Somme géométrique)\displaystyle\displaystyle 2^{n-1}+2^{n-2}+...+2^{3}+2^{2}+2+1\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \textrm{(Somme g\'{e}om\'{% e}trique)}
=\displaystyle\displaystyle= ∑i=0n−12i=2n−12−1=2n−1\displaystyle\displaystyle\sum_{i=0}^{n-1}2^{i}=\frac{2^{n}-1}{2-1}=2^{n}-1

Remarquer que cette fois, nous avons pu trouver une forme simple dû au fait que nous avons reconnu qu’il s’agissait d’une somme géométrique.

Les fonctions génératrices: Nous allons maintenant regarder comment les fonctions génératrices peuvent être utilisé pour résoudre le problème des tours de Hanoï. Pour ce faire, nous commençons à nouveau avec la même relation de récurrence. Nous avons donc:

∑i=1∞Hi⁢xi\displaystyle\displaystyle\sum_{i=1}^{\infty}H_{i}x^{i} =\displaystyle\displaystyle= ∑i=2∞Hi⁢xi+H1⁢x=∑i=2∞(2⁢Hi−1+1)⁢xi+H1⁢x=2⁢∑i=2∞Hi−1⁢xi+∑i=2∞xi+x\displaystyle\displaystyle\sum_{i=2}^{\infty}H_{i}x^{i}+H_{1}x=\sum_{i=2}^{% \infty}\left(2H_{i-1}+1\right)x^{i}+H_{1}x=2\sum_{i=2}^{\infty}H_{i-1}x^{i}+% \sum_{i=2}^{\infty}x^{i}+x
=\displaystyle\displaystyle= 2⁢∑i=1∞Hi⁢xi+1+∑i=2∞xi+x=2⁢x⁢∑i=1∞Hi⁢xi+∑i=0∞xi−1−x+x=2⁢x⁢∑i=1∞Hi⁢xi+11−x−1\displaystyle\displaystyle 2\sum_{i=1}^{\infty}H_{i}x^{i+1}+\sum_{i=2}^{\infty% }x^{i}+x=2x\sum_{i=1}^{\infty}H_{i}x^{i}+\sum_{i=0}^{\infty}x^{i}-1-x+x=2x\sum% _{i=1}^{\infty}H_{i}x^{i}+\frac{1}{1-x}-1

Maintenant, en isolant la somme, on obtient:

(1−2⁢x)⁢∑i=1∞Hi⁢xi=11−x−1⇒∑i=1∞Hi⁢xi=1(1−x)⁢(1−2⁢x)−11−2⁢x\displaystyle(1-2x)\sum_{i=1}^{\infty}H_{i}x^{i}=\frac{1}{1-x}-1\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \sum_{i=1}^{% \infty}H_{i}x^{i}=\frac{1}{(1-x)(1-2x)}-\frac{1}{1-2x}

Maintenant, rendu à cette étape, on utilise la décomposition en fractions partielles qui nous affirme qu’il existe des constantes A\displaystyle A et B\displaystyle B de sorte qu’on est l’égalité suivante:

1(1−x)⁢(1−2⁢x)=A1−x+B1−2⁢x=A⁢(1−2⁢x)+B⁢(1−x)(1−x)⁢(1−2⁢x)=(−2⁢A−B)⁢x+(A+B)(1−x)⁢(1−2⁢x)\displaystyle\frac{1}{(1-x)(1-2x)}=\frac{A}{1-x}+\frac{B}{1-2x}=\frac{A(1-2x)+% B(1-x)}{(1-x)(1-2x)}=\frac{(-2A-B)x+(A+B)}{(1-x)(1-2x)}

Comme les dénominateurs sont égaux, les numérateurs doivent aussi être égaux, ce qui nous amène à résoudre le système d’équations linéaires suivant:

{−2⁢A−B=0A+B=1\displaystyle\left\{\begin{array}[]{l}-2A-B=0\\ A+B=1\end{array}\right.

qui a comme solution A=−1\displaystyle A=-1 et B=2\displaystyle B=2. En revenant à notre somme, on a donc:

∑i=1∞Hi⁢xi\displaystyle\displaystyle\sum_{i=1}^{\infty}H_{i}x^{i} =\displaystyle\displaystyle= 1(1−x)⁢(1−2⁢x)−11−2⁢x=−11−x+21−2⁢x−11−2⁢x=−11−x+11−2⁢x=−∑i=0∞xi+∑i=0∞(2⁢x)i\displaystyle\displaystyle\frac{1}{(1-x)(1-2x)}-\frac{1}{1-2x}=\frac{-1}{1-x}+% \frac{2}{1-2x}-\frac{1}{1-2x}=\frac{-1}{1-x}+\frac{1}{1-2x}=-\sum_{i=0}^{% \infty}x^{i}+\sum_{i=0}^{\infty}(2x)^{i}
=\displaystyle\displaystyle= −∑i=0∞xi+∑i=0∞2i⁢xi=∑i=0∞(2i−1)⁢xi=∑i=1∞(2i−1)⁢xi\displaystyle\displaystyle-\sum_{i=0}^{\infty}x^{i}+\sum_{i=0}^{\infty}2^{i}x^% {i}=\sum_{i=0}^{\infty}\left(2^{i}-1\right)x^{i}=\sum_{i=1}^{\infty}\left(2^{i% }-1\right)x^{i}

Finalement, pour que les deux sommes (séries) soient égales, les coefficients doivent être égaux, ce qui nous donne:

Hn=2n−1,∀n≥1\displaystyle H_{n}=2^{n}-1,\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \forall n\geq 1

Ce qui est encore une fois la même solution que nous avions déjà trouvé.

La dérivation symbolique: Comme dernière approche, nous allons utiliser la méthode de dérivation symbolique. En commençant à nouveau avec la même relation de récurrence, nous avons:

{Hn=2⁢Hn−1+1Hn−1=2⁢Hn−2+1⇒{Hn−2⁢Hn−1=1Hn−1−2⁢Hn−2=1⇒Hn−2⁢Hn−1=Hn−1−2⁢Hn−2⇒Hn−3⁢Hn−1+2⁢Hn−2=0\displaystyle\left\{\begin{array}[]{l}H_{n}=2H_{n-1}+1\\ H_{n-1}=2H_{n-2}+1\end{array}\right.\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \left\{\begin{array}[]{l}H_{n}-2H_{n-1}=1\\ H_{n-1}-2H_{n-2}=1\end{array}\right.\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ H_{n}-2H_{n-1}=H_{n-1}-2H_{n-2}\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ H_{n}-3H_{n-1}+2H_{n-2}=0

qui est une relation de récurrence linéaire, homogène et à coefficients constants. Nous pouvons donc appliquer la méthode du polynôme caractéristique. On a donc:

λ2−3⁢λ+2=(λ−1)⁢(λ−2)=0\displaystyle\lambda^{2}-3\lambda+2=(\lambda-1)(\lambda-2)=0

La forme générale de notre suite est donc Hn=C1+2n⁢C2\displaystyle H_{n}=C_{1}+2^{n}C_{2}. Pour trouver les constantes, nous avons besoin de deux conditions initiales. En utilisant les valeurs de C1\displaystyle C_{1} et C2\displaystyle C_{2} que nous avons trouver dans notre tableau, on obtient donc le système d’équations linéaires suivant:

{C1+2⁢C2=1C1+4⁢C2=3\displaystyle\left\{\begin{array}[]{l}C_{1}+2C_{2}=1\\ C_{1}+4C_{2}=3\end{array}\right.

Ce qui nous permet d’obtenir facilement que C1=−1\displaystyle C_{1}=-1 et C2=1\displaystyle C_{2}=1. La solution de notre récurrence est donc: Hn=−1+2n=2n−1\displaystyle H_{n}=-1+2^{n}=2^{n}-1 pour tout n≥1\displaystyle n\geq 1.

Le problème des lapins de Fibonacci

En 1202, Leonardo Pisano dit Fibonacci, un mathématicien italien, énonce dans son livre liber abaci le problème connu aujourd’hui sous le nom du problème des lapins. Au premier mois, il y a une paire de lapereaux, trop jeune pour procréer. Si chaque couple de lapereaux prend un mois avant de devenir adulte, et si chaque couple adulte donne naissance chaque mois à un couple de lapereaux après un mois de gestation, combien de lapin aurons nous après x\displaystyle x mois ? Ce problème donna naissance à ce qu’on appelle aujourd’hui la suite de Fibonacci, et il est facile d’en trouver les premières valeurs de la suite. Si on dénote par Fn\displaystyle F_{n} le nombre de lapin présent au ne\displaystyle n^{e} mois, on a donc:

n\displaystyle n 0\displaystyle 0 1\displaystyle 1 2\displaystyle 2 3\displaystyle 3 4\displaystyle 4 5\displaystyle 5 6\displaystyle 6 7\displaystyle 7 8\displaystyle 8
Fn\displaystyle F_{n} 1\displaystyle 1 1\displaystyle 1 2\displaystyle 2 3\displaystyle 3 5\displaystyle 5 8\displaystyle 8 13\displaystyle 13 21\displaystyle 21 34\displaystyle 34

De plus, il est facile de voir que notre suite satisfait la récurrence suivante:

{Fn=Fn−1+Fn−2,∀n≥2F0=1F1=1\displaystyle\left\{\begin{array}[]{l}F_{n}=F_{n-1}+F_{n-2},\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 2\\ F_{0}=1\\ F_{1}=1\end{array}\right.

Nous allons maintenant utiliser la méthode du polynôme caractéristique pour trouver une formule explicite au problème des lapins. On doit commencer par trouver les racines du polynôme suivant:

λ2=λ+1⇒λ2−λ−1=0\displaystyle\lambda^{2}=\lambda+1\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \lambda^{2}-\lambda-1=0

En applicant la formule quadratique, on obtient facilement que les racines sont:

1±(−1)2−4⁢(1)⁢(−1)2⁢(1)=1±52\displaystyle\frac{1\pm\sqrt{(-1)^{2}-4(1)(-1)}}{2(1)}=\frac{1\pm\sqrt{5}}{2}

Ce qui nous donne une solution générale de la forme:

Fn=C1⁢(1+52)n+C2⁢(1−52)n\displaystyle F_{n}=C_{1}\left(\frac{1+\sqrt{5}}{2}\right)^{n}+C_{2}\left(% \frac{1-\sqrt{5}}{2}\right)^{n}

Il reste maintenant à trouver les deux constantes. Pour ce faire, on utilise la valeur de F1\displaystyle F_{1} et F2\displaystyle F_{2}, ce qui nous donne le système d’équations linéaires suivant:

{C1+C2=1C1⁢(1+52)+C2⁢(1−52)=1\displaystyle\left\{\begin{array}[]{l}C_{1}+C_{2}=1\\ C_{1}\left(\frac{1+\sqrt{5}}{2}\right)+C_{2}\left(\frac{1-\sqrt{5}}{2}\right)=% 1\\ \end{array}\right.

Ce qui a comme solution les valeurs C1=15⁢(1+52)\displaystyle C_{1}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right) et C2=−15⁢(1−52)\displaystyle C_{2}=\frac{-1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right). La solution de l’équation définie par récurrence est donc:

Fn=15⁢(1+52)n+1−15⁢(1−52)n+1,∀n≥0\displaystyle F_{n}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-% \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1},\leavevmode\nobreak% \ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 0

Remarquez que bien que cette suite est été introduit en Europe par Fibonacci, elle était déjà connu beaucoup plus tôt en Inde en lien avec d’autres problèmes.

Le problème des droites

Combien de régions sont obtenu en dessinant n\displaystyle n droites non parallèles dans le plan de sorte qu’il n’y est pas 3\displaystyle 3 droites ayant un point d’intersection commun ? Pour résoudre le problème, il s’agit premièrement de remarquer que chaque nouvelle droite doit couper chacune des droite déjà présente. C’est à dire que si n−1\displaystyle n-1 droite sont déjà présente, alors la nieme droite se fait couper en n−1\displaystyle n-1 endroit, ce qui revient à dire qu’elle est coupé en n\displaystyle n morceau. Chacun de ces morceaux donne lieu à un nouvelle région, ce qui nous permet d’obtenir la récurrence suivante:

{an=an−1+na0=1\displaystyle\left\{\begin{array}[]{l}a_{n}=a_{n-1}+n\\ a_{0}=1\end{array}\right.

Pour trouver une formule explicite, nous allons utiliser la méthode de dérivation symbolique. On a donc:

{an=an−1+nan−1=an−2+(n−1)⇒{n=an−an−1n=an−1−an−2+1⇒an−an−1=an−1−an−2+1⇒an=2⁢an−1−an−2+1\displaystyle\left\{\begin{array}[]{l}a_{n}=a_{n-1}+n\\ a_{n-1}=a_{n-2}+(n-1)\end{array}\right.\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \left\{\begin{array}[]{l}n=a_{n}-a_{n-1}\\ n=a_{n-1}-a_{n-2}+1\end{array}\right.\leavevmode\nobreak\ \leavevmode\nobreak% \ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ a_{n}-a_{n-1}=a_{n-1}-a_{n-2}+1\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ a_{n}=2a_{n-1}-a_{n-2}+1

Comme cette nouvelle récurrence n’est toujours pas homogène, nous appliquons à nouveau la dérivation symbolique, ce qui nous donne:

{an=2⁢an−1−an−2+1an−1=2⁢an−2−an−3+1⇒{1=an−2⁢an−1+an−21=an−1−2⁢an−2+an−3⇒an−2⁢an−1+an−2=an−1−2⁢an−2+an−3\displaystyle\left\{\begin{array}[]{l}a_{n}=2a_{n-1}-a_{n-2}+1\\ a_{n-1}=2a_{n-2}-a_{n-3}+1\end{array}\right.\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \left\{\begin{array}[]{l}1=a_{n}-2a_{n-1}+a_{n-% 2}\\ 1=a_{n-1}-2a_{n-2}+a_{n-3}\end{array}\right.\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ a_{n}-2a_{n-1}+a_{n-2}=a_{n-1}-2a_{n-2}+a_{n-3}

Ce qui nous donne finalement la récurrence suivante:

an−3⁢an−1+3⁢an−2−an−3=0\displaystyle a_{n}-3a_{n-1}+3a_{n-2}-a_{n-3}=0

Nous appliquons maintenant la méthode du polynôme caractéristique. On doit donc trouver les racines du polynôme suivant:

λ3−3⁢λ2+3⁢λ−1=(λ−1)3=0\displaystyle\lambda^{3}-3\lambda^{2}+3\lambda-1=(\lambda-1)^{3}=0

La forme générale de notre solution est donc:

an=C1+C2⁢n+C3⁢n2\displaystyle a_{n}=C_{1}+C_{2}n+C_{3}n^{2}

Pour trouver la valeur des constantes, nous avons maintenant besoin de 3\displaystyle 3 valeurs initiales, ce qui peut être accompli facilement à partir de la valeur a0=1\displaystyle a_{0}=1 en combinaison avec notre récurrence originale. On obtient donc a1=a0+1=2\displaystyle a_{1}=a_{0}+1=2 et a2=a1+2=4\displaystyle a_{2}=a_{1}+2=4. Ceci nous permet donc d’obtenir le système d’équations linéaires suivant:

{C1=1C1+C2+C3=2C1+2⁢C2+4⁢C3=4\displaystyle\left\{\begin{array}[]{l}C_{1}=1\\ C_{1}+C_{2}+C_{3}=2\\ C_{1}+2C_{2}+4C_{3}=4\end{array}\right.

Que l’on peut résoudre facilement pour obtenir C1=1\displaystyle C_{1}=1, C2=12\displaystyle C_{2}=\frac{1}{2} et C3=12\displaystyle C_{3}=\frac{1}{2}. Notre solution explicite est donc:

an=1+12⁢n+12⁢n2=1+n⁢(n+1)2\displaystyle a_{n}=1+\frac{1}{2}n+\frac{1}{2}n^{2}=1+\frac{n(n+1)}{2}

Les nombres de dérangement

Nous avons déjà étudier les nombres de dérangement lorsque nous avons étudier le problème des chapeaux, mais nous allons ici prendre une approche différente. Rappelons qu’un dérangement d’un ensemble de n\displaystyle n élément est une permutation des n\displaystyle n éléments de sorte qu’aucun d’entre eux ne se retrouve à sa position originale. Le nombre de dérangement est dénoté par Dn\displaystyle D_{n}. Nous avons déjà obtenu une formule explicite pour le nombre de dérangement à l’aide du principe d’inclusion-d’exclusion, mais nous allons ici développer la même formule à l’aide des récurrences.

Pour compter le nombre de dérangement d’un ensemble de n\displaystyle n éléments, remarquons premièrement que le premier élément de l’ensemble peut se retrouver dans n−1\displaystyle n-1 positions différentes après dérangement. En échangeant le premier élément, alors l’un des n−1\displaystyle n-1 éléments restant, deux options se présente à nous. On peut garder le premier élément fixe à sa nouvelle position, ou le déplacer à nouveau à l’emplacement d’un des n−2\displaystyle n-2 éléments restant. Si on le garde fixe, il faut alors faire un dérangement des n−2\displaystyle n-2 autres éléments, ce qui peut être fait de Dn−2\displaystyle D_{n-2} façons. Si on le déplace à nouveau, il faut alors faire un dérangement des n−1\displaystyle n-1 éléments, ce qui peut être fait de Dn−1\displaystyle D_{n-1} façons. On obtient donc la récurrence suivante:

Dn=(n−1)⁢(Dn−1+Dn−2),∀n≥3\displaystyle D_{n}=(n-1)\left(D_{n-1}+D_{n-2}\right),\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 3

Pour pouvoir calculer les différentes valeurs de Dn\displaystyle D_{n}, il nous faut maintenant ajouter deux valeurs initiales. Il est facile de voir par simple énumération que D1=0\displaystyle D_{1}=0 et D2=1\displaystyle D_{2}=1.

Cette récurrence est particulièrement difficile à résoudre sous cette forme. Nous allons donc faire une petite astuce. Remarquons que:

Dn=n⁢Dn−1+n⁢Dn−2−Dn−1−Dn−2\displaystyle\displaystyle D_{n}=nD_{n-1}+nD_{n-2}-D_{n-1}-D_{n-2} ⇒\displaystyle\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ Dn−n⁢Dn−1=n⁢Dn−2−Dn−1−Dn−2\displaystyle\displaystyle D_{n}-nD_{n-1}=nD_{n-2}-D_{n-1}-D_{n-2}
⇒\displaystyle\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ Dn−n⁢Dn−1=−Dn−1+(n−1)⁢Dn−2\displaystyle\displaystyle D_{n}-nD_{n-1}=-D_{n-1}+(n-1)D_{n-2}
⇒\displaystyle\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ Dn−n⁢Dn−1=−[Dn−1−(n−1)⁢Dn−2]\displaystyle\displaystyle D_{n}-nD_{n-1}=-\left[D_{n-1}-(n-1)D_{n-2}\right]

Remarquons que nous avons une forme de symétrie. Si on pose An=Dn−n⁢Dn−1\displaystyle A_{n}=D_{n}-nD_{n-1}, on remarque que An=−An−1\displaystyle A_{n}=-A_{n-1}. Ceci signifie que

An=−An−1=An−2=−An−3=…=±A2\displaystyle A_{n}=-A_{n-1}=A_{n-2}=-A_{n-3}=...=\pm A_{2}

Il est facile de voir que A2=D2−2⁢D1=1−2⁢(0)=1\displaystyle A_{2}=D_{2}-2D_{1}=1-2(0)=1. On a donc que An=(−1)n\displaystyle A_{n}=(-1)^{n}, ce qui nous donne la récurrence suivante:

{Dn=n⁢Dn−1+(−1)nD1=0\displaystyle\left\{\begin{array}[]{l}D_{n}=nD_{n-1}+(-1)^{n}\\ D_{1}=0\end{array}\right.

Pour résoudre cette nouvelle récurrence, nous allons appliquer la méthode des fonctions génératrices exponentielles. Pour ce faire, nous allons premièrement ajouter la valeur de D0\displaystyle D_{0} à notre suite pour simplifier les calculs. Nous avons donc D1=1⁢D0+(−1)1=D0−1\displaystyle D_{1}=1D_{0}+(-1)^{1}=D_{0}-1. Sachant que D1=0\displaystyle D_{1}=0, on obtient donc que D0=1\displaystyle D_{0}=1. On a donc:

∑n=0∞Dn⁢xnn!\displaystyle\displaystyle\sum_{n=0}^{\infty}\frac{D_{n}x^{n}}{n!} =\displaystyle\displaystyle= 1+∑n=1∞Dn⁢xnn!=1+∑n=1∞(n⁢Dn−1+(−1)n)⁢xnn!=1+x⁢∑n=1∞Dn−1⁢xn−1(n−1)!+∑n=1∞(−1)n⁢xnn!\displaystyle\displaystyle 1+\sum_{n=1}^{\infty}\frac{D_{n}x^{n}}{n!}=1+\sum_{% n=1}^{\infty}\frac{\left(nD_{n-1}+(-1)^{n}\right)x^{n}}{n!}=1+x\sum_{n=1}^{% \infty}\frac{D_{n-1}x^{n-1}}{(n-1)!}+\sum_{n=1}^{\infty}\frac{(-1)^{n}x^{n}}{n!}
=\displaystyle\displaystyle= x⁢∑n=0∞Dn⁢xnn!+∑n=0∞(−x)nn!=x⁢∑n=0∞Dn⁢xnn!+e−1\displaystyle\displaystyle x\sum_{n=0}^{\infty}\frac{D_{n}x^{n}}{n!}+\sum_{n=0% }^{\infty}\frac{(-x)^{n}}{n!}=x\sum_{n=0}^{\infty}\frac{D_{n}x^{n}}{n!}+e^{-1}

En isolant la série, on obtient donc:

∑n=0∞Dn⁢xnn!=e−11−x=e−1⋅11−x=(∑n=0∞(−1)nn!⁢xn)⁢(∑n=0∞xn)=∑n=0∞(∑k=0n(−1)kk!)⁢xn=∑n=0∞(∑k=0n(−1)k⁢n!k!)⁢xnn!\displaystyle\sum_{n=0}^{\infty}\frac{D_{n}x^{n}}{n!}=\frac{e^{-1}}{1-x}=e^{-1% }\cdot\frac{1}{1-x}=\left(\sum_{n=0}^{\infty}\frac{(-1)^{n}}{n!}x^{n}\right)% \left(\sum_{n=0}^{\infty}x^{n}\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}% \frac{(-1)^{k}}{k!}\right)x^{n}=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\frac{(% -1)^{k}n!}{k!}\right)\frac{x^{n}}{n!}

On obtient donc la formule explicite suivante pour les nombres de dérangement:

Dn=∑k=0n(−1)k⁢n!k!=∑k=0n(−1)k⁢n!⁢(n−k)!k!⁢(n−k)n=∑k=0n(−1)k⁢(nk)⁢(n−k)!\displaystyle D_{n}=\sum_{k=0}^{n}\frac{(-1)^{k}n!}{k!}=\sum_{k=0}^{n}\frac{(-% 1)^{k}n!(n-k)!}{k!(n-k)^{n}}=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)!

Le problème de triangulation et les nombres de Catalan

Rappelons que les nombres de Catalan Cn\displaystyle C_{n} que nous avons définit dans la section LABEL:Catalan1 comptent le nombre de façon de trianguler un polygone convexe à n+2\displaystyle n+2 côtés. Nous avons déjà trouver qu’ils satisfont la récurrence suivante:

{Cn=∑k=0n−1Ck⁢Cn−k−1C0=1\displaystyle\left\{\begin{array}[]{l}C_{n}=\sum_{k=0}^{n-1}C_{k}C_{n-k-1}\\ C_{0}=1\end{array}\right.

Nous avons déjà utiliser cette récurrence pour calculer quelques valeurs de Cn\displaystyle C_{n}, mais nous voulons maintenant aller plus loin et chercher une formule explicite pour les calculer. Pour ce faire, nous allons utiliser les fonctions génératrices. Si on définit f⁢(x)=∑n=0∞Cn⁢xn\displaystyle f(x)=\sum_{n=0}^{\infty}C_{n}x^{n}, nous avons donc:

f⁢(x)\displaystyle\displaystyle f(x) =\displaystyle\displaystyle= ∑n=0∞Cn⁢xn=C0+∑n=1∞Cn⁢xn=C0+∑n=1∞[∑k=0n−1Ck⁢Cn−k−1]⁢xn=C0+∑n=0∞[∑k=0nCk⁢Cn−k]⁢xn+1\displaystyle\displaystyle\sum_{n=0}^{\infty}C_{n}x^{n}=C_{0}+\sum_{n=1}^{% \infty}C_{n}x^{n}=C_{0}+\sum_{n=1}^{\infty}\left[\sum_{k=0}^{n-1}C_{k}C_{n-k-1% }\right]x^{n}=C_{0}+\sum_{n=0}^{\infty}\left[\sum_{k=0}^{n}C_{k}C_{n-k}\right]% x^{n+1}
=\displaystyle\displaystyle= C0+x⁢∑n=0∞[∑k=0nCk⁢Cn−k]⁢xn=C0+x⁢(∑n=0∞Cn⁢xn)⁢(∑n=0∞Cn⁢xn)=1+x⁢[f⁢(x)]2\displaystyle\displaystyle C_{0}+x\sum_{n=0}^{\infty}\left[\sum_{k=0}^{n}C_{k}% C_{n-k}\right]x^{n}=C_{0}+x\left(\sum_{n=0}^{\infty}C_{n}x^{n}\right)\left(% \sum_{n=0}^{\infty}C_{n}x^{n}\right)=1+x[f(x)]^{2}

Maintenant, pour déterminer f⁢(x)\displaystyle f(x), nous devons utiliser la formule quadratique, ce qui nous permet d’obtenir:

f⁢(x)=1+x⁢[f⁢(x)]2⇒x⁢[f⁢(x)]2−f⁢(x)+1=0⇒f⁢(x)=1±1−4⁢x2⁢x\displaystyle f(x)=1+x[f(x)]^{2}\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ x[f(x)]^{2}-f(x)+1=0\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \Rightarrow\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ f(x)=\frac{1\pm\sqrt{1-4x}}{2x}

Remarquez que le ±\displaystyle\pm nous donne en fait deux fonctions, mais une seule des deux est la bonne. Pour déterminer laquelle, on remarque que f⁢(0)\displaystyle f(0) doit être égal à C0\displaystyle C_{0}. Remarquez qu’ici, la fonction n’est pas définie en zéro. Dans ce cas, nous devons avoir recours à la limite. En remarquant que:

limx→0+1+1−4⁢x2⁢x=∞ et limx→0+1−1−4⁢x2⁢x=1\displaystyle\lim_{x\rightarrow 0^{+}}\frac{1+\sqrt{1-4x}}{2x}=\infty% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \textrm{ et }\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \lim_% {x\rightarrow 0^{+}}\frac{1-\sqrt{1-4x}}{2x}=1

On obtient donc que la bonne fonction génératrice est la seconde, c’est à dire:

f⁢(x)=1−1−4⁢x2⁢x\displaystyle f(x)=\frac{1-\sqrt{1-4x}}{2x}

Il nous faut maintenant réécrire notre fonction f⁢(x)\displaystyle f(x) sous forme d’une série. La racine carré et la division vient nous créer quelques difficultés, mais le théorème du binôme généralisé va tout de même nous permettre d’y parvenir. Nous allons commencer par travailler uniquement avec la racine, et reviendrons par la suite à la fonction complète.

1−4⁢x\displaystyle\displaystyle\sqrt{1-4x} =\displaystyle\displaystyle= ∑n=0∞(1/2n)⁢(−4⁢x)n=∑n=0∞(1/2)n¯⁢(−1)n⁢4n⁢xnn!=(12)0¯+∑n=1∞1n!⁢(∏i=0n−1(12−i))⁢(−1)n⁢22⁢n⁢xn\displaystyle\displaystyle\sum_{n=0}^{\infty}\binom{\nicefrac{{1}}{{2}}}{n}(-4% x)^{n}=\sum_{n=0}^{\infty}\frac{(\nicefrac{{1}}{{2}})^{\underline{n}}(-1)^{n}4% ^{n}x^{n}}{n!}=\left(\frac{1}{2}\right)^{\underline{0}}+\sum_{n=1}^{\infty}% \frac{1}{n!}\left(\prod_{i=0}^{n-1}\left(\frac{1}{2}-i\right)\right)(-1)^{n}2^% {2n}x^{n}
=\displaystyle\displaystyle= 1+∑n=1∞1n!⁢(∏i=0n−11−2⁢i2)⁢(−1)n⁢22⁢n⁢xn=1+∑n=1∞(−1)n2n⁢n!⁢(∏i=0n−12⁢i−1)⁢(−1)n⁢22⁢n⁢xn\displaystyle\displaystyle 1+\sum_{n=1}^{\infty}\frac{1}{n!}\left(\prod_{i=0}^% {n-1}\frac{1-2i}{2}\right)(-1)^{n}2^{2n}x^{n}=1+\sum_{n=1}^{\infty}\frac{(-1)^% {n}}{2^{n}n!}\left(\prod_{i=0}^{n-1}2i-1\right)(-1)^{n}2^{2n}x^{n}
=\displaystyle\displaystyle= 1+∑n=1∞2nn!⁢(∏i=0n−12⁢i−1)⁢xn=1+∑n=1∞2n(2⁢n−1)⁢n!⁢(∏i=0n(2⁢i−1))⁢xn\displaystyle\displaystyle 1+\sum_{n=1}^{\infty}\frac{2^{n}}{n!}\left(\prod_{i% =0}^{n-1}2i-1\right)x^{n}=1+\sum_{n=1}^{\infty}\frac{2^{n}}{(2n-1)n!}\left(% \prod_{i=0}^{n}(2i-1)\right)x^{n}
=\displaystyle\displaystyle= 1−∑n=1∞2n(2⁢n−1)⁢n!⁢(1⋅3⋅5⋅7⋅…⋅(2⁢n−1))⁢xn=1−∑n=1∞2n(2⁢n−1)⁢n!⁢((2⁢n)!2⋅4⋅6⋅…⋅(2⁢n))⁢xn\displaystyle\displaystyle 1-\sum_{n=1}^{\infty}\frac{2^{n}}{(2n-1)n!}\left(1% \cdot 3\cdot 5\cdot 7\cdot...\cdot(2n-1)\right)x^{n}=1-\sum_{n=1}^{\infty}% \frac{2^{n}}{(2n-1)n!}\left(\frac{(2n)!}{2\cdot 4\cdot 6\cdot...\cdot(2n)}% \right)x^{n}
=\displaystyle\displaystyle= 1−∑n=1∞2n⁢(2⁢n)!(2⁢n−1)⁢n!⁢2n⁢n!⁢xn=1−∑n=1∞(2⁢nn)⁢12⁢n−1⁢xn\displaystyle\displaystyle 1-\sum_{n=1}^{\infty}\frac{2^{n}(2n)!}{(2n-1)n!2^{n% }n!}x^{n}=1-\sum_{n=1}^{\infty}\binom{2n}{n}\frac{1}{2n-1}x^{n}

Maintenant, considérons la fonction f⁢(x)\displaystyle f(x). En utilisant ce que nous venons de trouver pour la racine, on obtient donc:

f⁢(x)\displaystyle\displaystyle f(x) =\displaystyle\displaystyle= 1−1−4⁢x2⁢x=12⁢x⁢∑n=1∞(2⁢nn)⁢12⁢n−1⁢xn=12⁢x⁢∑n=1∞(2⁢n)!n!⁢n!⁢(2⁢n−1)⁢xn\displaystyle\displaystyle\frac{1-\sqrt{1-4x}}{2x}=\frac{1}{2x}\sum_{n=1}^{% \infty}\binom{2n}{n}\frac{1}{2n-1}x^{n}=\frac{1}{2x}\sum_{n=1}^{\infty}\frac{(% 2n)!}{n!n!(2n-1)}x^{n}
=\displaystyle\displaystyle= 12⁢∑n=0∞(2⁢n+2)!(n+1)!⁢(n+1)!⁢(2⁢n+1)⁢xn=12⁢∑n=0∞(2⁢n)!⁢(2⁢n+1)⁢(2⁢n+2)n!⁢n!⁢(n+1)2⁢(2⁢n+1)⁢xn\displaystyle\displaystyle\frac{1}{2}\sum_{n=0}^{\infty}\frac{(2n+2)!}{(n+1)!(% n+1)!(2n+1)}x^{n}=\frac{1}{2}\sum_{n=0}^{\infty}\frac{(2n)!(2n+1)(2n+2)}{n!n!(% n+1)^{2}(2n+1)}x^{n}
=\displaystyle\displaystyle= 12⁢∑n=0∞(2⁢n+1)⁢(2⁢n+2)(n+1)2⁢(2⁢n+1)⁢(2⁢nn)⁢xn=∑n=0∞1n+1⁢(2⁢nn)⁢xn\displaystyle\displaystyle\frac{1}{2}\sum_{n=0}^{\infty}\frac{(2n+1)(2n+2)}{(n% +1)^{2}(2n+1)}\binom{2n}{n}x^{n}=\sum_{n=0}^{\infty}\frac{1}{n+1}\binom{2n}{n}% x^{n}

Nous obtenons donc finalement la formule suivante pour les nombres de Catalan:

Cn=1n+1⁢(2⁢nn)\displaystyle C_{n}=\frac{1}{n+1}\binom{2n}{n}

qui est étrangement simple considérant le travail qu’il nous a pris pour l’obtenir. Selon Sloane et Plouffe [Sloane, Harris], les nombres de Catalan forment la deuxième famille de nombre la plus souvent rencontrée dans les problèmes de combinatoire après les coefficient binomiaux. Le livre de Stanley [Stanley2] propose une liste de 66 problèmes dans lesquels les nombres de Catalan interviennent. Nous allons maintenant conclure ce chapitre en énonçant certaines applications des nombres de Catalan, plusieurs d’entre elles nous avons déjà eu l’occasion de rencontrer.

  1. 1.
    ​

    Le nombre de façon de trianguler un polygone convexe à n+2\displaystyle n+2 côtés est Cn\displaystyle C_{n}.

  2. 2.
    ​

    Le nombre de façons de placer toutes les parenthèses sur un produit de n+1\displaystyle n+1 facteurs est Cn\displaystyle C_{n}.

  3. 3.
    ​

    Le nombre d’arbre binaire à n+1\displaystyle n+1 feuilles est Cn\displaystyle C_{n}.

  4. 4.
    ​

    Le nombre de trajet sur une grille n×n\displaystyle n\times n qui reste sous ou sur la diagonale est Cn\displaystyle C_{n}.

  5. 5.
    ​

    Le nombre de façon de lancer 2⁢n\displaystyle 2n fois consécutives à pile ou face de sorte qu’à la fin nous ayons obtenu n\displaystyle n piles et n\displaystyle n faces, mais qu’à aucun moment durant les lancer nous ayons un nombre supérieur de face que de pile est Cn\displaystyle C_{n}.