Exercice 29 Chaînes dans un graphe complet

1. Dans $K_{n}$, deux sommets distincts sont toujours adjacents et il n'y a pas de boucle : $M$ a des $1$ partout sauf sur la diagonale, d'où $M=J-I$. Chaque coefficient de $J^{2}$ est une somme de $n$ produits $1\times 1$, donc vaut $n$ : $J^{2}=nJ$. Comme $I$ commute avec $J$ : $$M^{2}=(J-I)^{2}=J^{2}-2J+I=nJ-2J+I=(n-2)J+I$$ En remplaçant $J$ par $M+I$ : $$\boxed{M^{2}=(n-2)(M+I)+I=(n-2)M+(n-1)I}$$

2. On note $\mathcal{P}_{p}$ : « $M^{p}=a_{p}M+b_{p}I$ », avec les suites définies par l'énoncé.

Initialisation : $M^{1}=1\times M+0\times I$.

Hérédité : Si $\mathcal{P}_{p}$ est vraie pour un $p\in\mathbb{N}^{*}$, alors, d'après la question 1 : $$M^{p+1}=M^{p}M=a_{p}M^{2}+b_{p}M=a_{p}\big((n-2)M+(n-1)I\big)+b_{p}M=\big((n-2)a_{p}+b_{p}\big)M+(n-1)a_{p}I$$ c'est-à-dire $M^{p+1}=a_{p+1}M+b_{p+1}I$.

Conclusion : $\mathcal{P}_{p}$ est vraie pour tout $p\in\mathbb{N}^{*}$.

3. Pour tout $p\in\mathbb{N}^{*}$ : $a_{p+2}=(n-2)a_{p+1}+b_{p+1}=(n-2)a_{p+1}+(n-1)a_{p}$.

On note $\mathcal{Q}_{p}$ : « $a_{p}=\dfrac{(n-1)^{p}-(-1)^{p}}{n}$ et $a_{p+1}=\dfrac{(n-1)^{p+1}-(-1)^{p+1}}{n}$ ». Cette récurrence porte sur deux termes consécutifs, puisque $a_{p+2}$ dépend de $a_{p+1}$ et de $a_{p}$.

Initialisation : $a_{1}=1=\dfrac{(n-1)+1}{n}$ et $a_{2}=(n-2)\times 1+0=n-2=\dfrac{n^{2}-2n}{n}=\dfrac{(n-1)^{2}-1}{n}$.

Hérédité : Supposons $\mathcal{Q}_{p}$ vraie. Les réels $q=n-1$ et $q=-1$ vérifient tous deux $q^{2}=(n-2)q+(n-1)$, puisque $(n-1)^{2}=n^{2}-2n+1=(n-2)(n-1)+(n-1)$ et $1=-(n-2)+(n-1)$. On les multiplie par $q^{p}$ : $q^{p+2}=(n-2)q^{p+1}+(n-1)q^{p}$. Alors : $$n\,a_{p+2}=(n-2)\left[(n-1)^{p+1}-(-1)^{p+1}\right]+(n-1)\left[(n-1)^{p}-(-1)^{p}\right]=(n-1)^{p+2}-(-1)^{p+2}$$ donc $\mathcal{Q}_{p+1}$ est vraie.

Conclusion : Pour tout $p\in\mathbb{N}^{*}$, $\boxed{a_{p}=\dfrac{(n-1)^{p}-(-1)^{p}}{n}}$.

4. La matrice $M$ a des $0$ sur la diagonale et des $1$ ailleurs. Le coefficient de $M^{p}=a_{p}M+b_{p}I$ hors diagonale vaut donc $a_{p}$, et le coefficient diagonal vaut $b_{p}$. Pour $p\geqslant 2$, $b_{p}=(n-1)a_{p-1}$, et la formule obtenue vaut aussi pour $p=1$ puisque $b_{1}=0$ : $$\boxed{\begin{array}{c} \text{chaînes de longueur } p \text{ entre deux sommets distincts : } \dfrac{(n-1)^{p}-(-1)^{p}}{n} \\[3mm] \text{chaînes fermées de longueur } p \text{ partant d'un sommet : } \dfrac{(n-1)^{p}+(n-1)(-1)^{p}}{n} \end{array}}$$ Le calcul de $b_{p}$ est le suivant : $(n-1)\dfrac{(n-1)^{p-1}-(-1)^{p-1}}{n}=\dfrac{(n-1)^{p}+(n-1)(-1)^{p}}{n}$.

5. Pour $n=4$ et $p=3$ : $a_{3}=\frac{27+1}{4}=7$ et $b_{3}=\frac{27-3}{4}=6$. Ce sont exactement les coefficients de $K^{3}$ calculés à l'exercice 21.

Depuis un sommet donné, on compte les chaînes fermées, plus celles qui aboutissent à l'un des $n-1$ autres sommets : $$b_{p}+(n-1)a_{p}=\frac{(n-1)^{p}+(n-1)(-1)^{p}+(n-1)(n-1)^{p}-(n-1)(-1)^{p}}{n}=\frac{n(n-1)^{p}}{n}$$ soit $b_{p}+(n-1)a_{p}=(n-1)^{p}$. Directement : à chaque étape, on peut aller vers n'importe lequel des $n-1$ autres sommets, d'où $(n-1)^{p}$ chaînes de longueur $p$. La formule de $a_{p}$ dit alors que ces chaînes se répartissent presque également entre les $n$ sommets d'arrivée, à $\pm 1$ près.