Compter toutes les chaînes de longueur $d$

La somme des coefficients. D'après le théorème des puissances, $(A^d{)}_{ij}$ est le nombre de chaînes de longueur $d$ allant de $i$ à $j$. Toute chaîne de longueur $d$ a un unique sommet de départ et un unique sommet d'arrivée : les ensembles de chaînes comptés par les $(A^d{)}_{ij}$ sont donc deux à deux disjoints, et leur réunion est l'ensemble de toutes les chaînes de longueur $d$. En sommant sur $i$ et $j$ : $$\sum _{i=1}^n\sum _{j=1}^n(A^d{)}_{ij}=\text{nombre total de chaıˆnes de longueur }d.$$

Le cas de $K_n$. Comptons directement, sans matrice. Une chaîne de longueur $d$ est une suite $s_0,s_1,\dots ,s_d$ où deux sommets consécutifs sont reliés. Dans $K_n$, deux sommets sont reliés dès qu'ils sont distincts :

• le sommet de départ $s_0$ se choisit librement : $n$ possibilités ;
• chaque sommet suivant doit seulement différer du précédent : $n-1$ possibilités, et ce choix ne dépend pas des précédents.

Ces choix étant successifs et indépendants, le nombre total vaut $$n(n-1{)}^d.$$

Application à $K_4$, $d=3$. On obtient $4\times 3^3=4\times 27=108$ chaînes de longueur $3$.

Le point délicat est de ne pas confondre « chaîne » et « chaîne à sommets distincts » : ici on autorise les allers-retours, et c'est précisément ce que compte $A^d$.