Forum de mathématiques - Bibm@th.net

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 871

Variante d'un dénombrement

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

Dernière modification par bridgslam (04-12-2025 06:49:43)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."