Bonjour,
Saurez-vous dénombrer à l'aide d'un graphe et de sa matrice d'adjacence combien d'entiers s'écrivent avec 4 chiffres allant de 1 à 7 rangés en ordre croissant?
Ainsi 2267, 1116 etc sont des candidats , comme 3355 1234 et autres...
C'est un calcul classique en soi ( à partir de suites str. croissantes ), mais je vous propose d'imaginer une solution dans l'esprit des graphes...
▼réponse
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 &1 \\
0 & 1 & 1 & 1 & 1 & 1 &1 \\
0 & 0 & 1 & 1 & 1 & 1 &1 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{bmatrix}
représente le graphe orienté de la relation d'ordre sur les chiffres 1,2,....,7
Une combinaison de chiffres pour la question posée est un chemin quelconque en exactement 3 étapes en suivant le graphe.
On calcule donc la puissance 3ième de la matrice, dont les éléments sont le nombre de chemins pour aller d'un sommet i à un sommet j (4 sommets, 3 étapes).
Il suffira alors de sommer tous les éléments de la matrice.
La quantité cherchée est 210, ce qui est bien égal au calcul direct $\binom{10}{4}$
Remarque: la matrice des trajets de longueur fixée (3 ici) fait apparaître une constance selon les 7 diagonales // à la diagonale principale.
En effet il y a clairement autant de combinaisons commençant par i et finissant par j que commençant par i+k et finissant par j+k pour tout k, par bijection des translations permises de "vecteur" (k,k,k,k).
Bon courage
