Eulériens

Circuits Eulériens et chaînes de dominos.
Combien peut-on réaliser de chaînes différentes de 28 dominos ?

Supprimons tout d'abord les doubles du jeu et réalisons une chaîne avec les dominos restants.
Il suffira ensuite d'insérer les doubles à tous les emplacements possibles.

On peut considérer les 21 dominos restants comme les arêtes d'un graphe complet de 7 sommets K₇ numérotés de 0 à 6.
Le domino 1-3 par exemple étant représenté par l'arète reliant le sommet 1 au sommet 3.
Réaliser une chaîne avec les dominos consiste alors à réaliser un parcours Eulérien sur ce graphe, passant une fois et une seule par chaque arète.
Le résultat fondamental concernant ces parcours est qu'il n'est possible que si le nombre de sommets impairs (ayant un nombre impair d'arêtes y arrivant) est 0 ou 2.
S'il y a 0 sommets impairs, on part d'un sommet quelconque et on y revient : circuit (fermé) Eulérien
S'il y a 2 sommets impairs, on part de l'un et on arrive à l'autre, le parcours Eulérien ainsi réalisé n'est pas fermé.

En ce qui concerne K₇, il comporte 7 sommets pairs, il existe donc des circuits Eulériens sur ce graphe.

Répondons tout de suite à la dernière question : quid du jeu de 0-0 au 9-9 ?
Le graphe correspondant est le graphe à 10 sommets K₁₀ tous impairs (9 arêtes chacun).
Il n'existe donc pas de parcours Eulérien et encore moins de circuit Eulérien.
Rajouter les doubles ne change rien à l'affaire.

Il est impossible de réaliser une chaîne complète avec un jeu de 55 dominos du 0-0 au 9-9. Et de même pour tous les jeux du 0-0 au m-m, m impair.

Il n'est pas difficile de réaliser un circuit Eulérien sur le graphe K₇
La question est ici combien y a-t-il de circuits différents ? On va voir que ce nombre est astronomique.

Entraînons nous ainsi au jeu de 6 dominos du 0-0 au 2-2, sur le graphe K₃.
Là c'est assez trivial : il n'y a que deux circuits Eulériens, dans un sens, ou dans l'autre.
On peut alors ajouter les doubles, ici d'une seule façon possible, pour obtenir les deux circuits possibles.
Puis ouvrir ce circuit entre deux dominos quelconques pour former une chaîne.
Il y a donc 6 façons d'ouvrir le cycle et ainsi 6×2 = 12 chaînes différentes :
Toutes les permutations circulaires de (0-0)(0-1)(1-1)(1-2)(2-2)(2-0) et de (0-2)(2-2)(2-1)(1-1)(1-0)(0-0)

Déja avec les 15 dominos du 0-0 au 4-4 (pas la peine d'essayer les 10 dominos du 0-0 au 3-3 n'est-ce pas...) le nombre de possibilités empèche une telle énumération exaustive.

Exprimons tout d'abord quelques formules élémentaires sur le cas général.
Nous nous intéressons exclusivement aux dominos du 0-0 au m-m avec m = 2n pair, donc sur le graphe à 2n+1 sommets K_2n+1
Il y a (n+1)(2n+1) dominos dont 2n+1 doubles
A chaque sommet du graphe aboutissent 2n arêtes.
On passe ainsi n fois par chaque sommet lors du circuit Eulérien.
L'insertion du double correspondant à ce sommet peut se faire alors de n façons différentes, et pour les 2n+1 doubles, il y a n²ⁿ⁺¹ façons d'insérer ces doubles.
Le cycle de (n+1)(2n+1) dominos ainsi obtenu peut être ouvert entre deux dominos quelconques, soit de (n+1)(2n+1) façons.

pour un jeu de (n+1)(2n+1) dominos du 0-0 au 2n-2n en appelant E2n+1 le nombre de circuits Eulériens du graphe K2n+1, le nombre de chaînes est       Sn = (n+1)(2n+1) × n2n+1 × E2n+1

La question fondamentale est donc le nombre de circuits Eulériens du graphe K_2n+1
(Rappel : le nombre de circuits Eulériens du graphe K_2n est 0)

Expliquons la méthode sur K₅
Nous allons éliminer les sommets un par un.
Les chemins passant par le sommet 0 y passent de trois façons différentes :
 - via les chemins a+b et c+d
 - via les chemins a+c et b+d
 - via les chemins a+d et b+c
Le nombre de circuits du graphe K₅ est ainsi la somme des nombres de circuits de chacun des graphes obtenus en supprimant ce sommet 0 de chacune de ces façons.

En fait chacun des graphes obtenu est topologiquement équivallent. En appellant Q le nombre de circuits d'un tel graphe, le nombre de circuits de K₅ est donc de 3Q.
Examinons le dernier graphe comme modèle.
Les 4 arêtes arrivant au sommet 1 : ad, e, f, g éliminent le sommet 1 de trois façons :
 - via les chemins ad+e et f+g
 - via les chemins ad+f et e+g
 - via les chemins ad+g et e+f

Les deux derniers étant équivallents, on en tire Q = B + 2T
Du premier (B) on peut éliminer la boucle du sommet 4 de deux façons :
en la parcourant dans un sens, ou dans l'autre.
Le sommet 4 lui même s'élimine "tout seul" et conduit au graphe L, et ainsi B = 2L
L'élimination du graphe T se fait de trois façons :
 - adf+i et j+eg conduisant au graphe C
 - adf+j et i+eg conduisant au graphe L
 - adf+eg et i+j conduisant aussi au graphe L
Soit T = C + 2L

Restent finalement les graphes à deux sommets seulement (C et L) dont on calcule directement le nombre de circuits.
Graphe L : partant d'un point sur une arête, on peut partir dans les deux direction, et enchainer les 3 autres arêtes de 3! = 6 façons possibles soit au total L = 2×3! = 12 circuits distincts.
Ceci est général pour tous les graphes sans boucles à deux sommets, et nombre pair d'arcs

Un graphe sans boucles formé de deux sommets reliés par 2n arêtes a 2×(2n-1)! circuits Eulériens

Le même raisonnement appliqué au graphe C donne en partant de la boucle de gauche :
le sens de cette boucle, le choix des deux chemins, le sens de l'autre boucle soit C = 2³ = 8
Ceci peut s'obtenir autrement par le "théorème des impasses" (selon E. Lucas), qui est la régle générale d'élimination des boucles.
Soit donc une boucle sur un sommet avec 2n arêtes par ailleurs.
A chaque parcours, on passe n fois par ce sommet, et chaque fois on peut y insérer la boucle, dans un sens ou dans l'autre.

S'il y a S circuits Eulériens dans le graphe réduit (sans la boucle), le nombre de circuits avec la boucle est 2n S

L'application de ce théorème à la boucle du sommet 4 du graphe B, où arrivent 2 arêtes par ailleurs, donne B = 2 × L
Pour le graphe C la suppression des deux boucles donne 2² × C', avec C' le même graphe sans les boucles, dont on a vu précédement (2 sommets avec 2 arêtes) qu'il comporte 2×1! = 2 circuits Eulériens, donc bien 8 circuits pour le graphe C.

On remonte alors les calculs pour obtenir successivement
T = C + 2L = 32
B = 2L = 24
Q = B + 2T = 88

et E₅ = 3Q = 264

On en déduit le nombre d'alignements des 15 dominos du 0-0 au 4-4

S₂ = 15 × 2⁵ × E₅ = 126720

Jeu normal de 28 dominos

On peut de même calculer le nombre de circuits Eulériens du graphe K₇ et ainsi le nombre d'alignements S₃ des 28 dominos du 0-0 au 6-6.

On élimine le sommet 0 (où arrivent 6 arêtes) de 5×3 = 15 façons différentes

De façon générale, un sommet où aboutissent 2n arêtes se supprime de (2n-1)(2n-3)(2n-5)... façons différentes soit

    (2n)! / (2ⁿn!)

Les 15 graphes obtenus sont tous identiques à H = K₆ où on a doublé 3 arêtes :

L'élimination du sommet 1 donne 15 graphes divers, et de plus certains avec des boucles.

La suppression de la boucle du premier graphe le multiplie par 4 (4 arêtes en plus de la boucle)
Les deux graphes suivant sont identiques, et la supression de la boucle multiplie par 4, soit en tout 8 fois ce graphe.
Le graphe (ae bc df) est identique à 7 autres graphes, et compte donc pour 8×
Le graphe (ab ce df) est répété 4 fois et finalement :

H = 4P₁ + 4P₂ + 8P₃ + 8P₄

 

L'élimination du sommet 2 sur le graphe P1 conduit aux 3 graphes suivants, les deux derniers étant identiques.

P₁ = Q₁ + 2Q₂

L'élimination du sommet 2 du graphe P2 donne 15 graphes divers, et avec des boucles.
(nommés selon le regroupement par paires des arètes 123456 aboutissant au sommet 2)

L'élimination des boucles fait compter le premier pour 4×4 = 16Q₃
Le second et le troisième chacun pour 4Q₄, de même que les deux derniers
Les autres sont équivallents soit au graphe Q₁, soit au graphe Q₂ vus précédemment.

P₂ = 2Q₁ + 8Q₂ + 16Q₃ + 16Q₄

L'élimination du sommet 2 du graphe P₃ donne :
(le graphe Q₂ déja rencontré et un nouveau graphe Q₅, le graphe complet K₄ avec ses arêtes doublées.)

P₃ = 2Q₂ + Q₅

L'élimination du sommet 2 de P₄ donne encore une fois 15 graphes, déja rencontrés à l'exception de Q₆

Soit P₄ = 6Q₂ + 16Q₄ + 4Q₅ + 16Q₆

On est ainsi ramené à 6 graphes de 4 sommets

Le même procédé (que nous ne détaillerons plus) conduit aux 5 graphes à trois sommets
et aux relations

Q1 = 24T1 + 48T3 Q2 = 48T2 + 24T3 + 6T5 Q3 = 2T1 + 2T3 Q4 = 4T3 + 2T5 Q5 = 24T3 + 64T4 + 8T5 Q6 = 4T2 + 2T3

Finalement on obtient les trois graphes à 2 sommets

et les relations

T1 = D1 T2 = 12D2 T3 = 2D1 + 16D2 T4 = 2D2 + 4D3 T5 = 6D1 + 144D2

Le nombre de circuits de ces graphes est (cas général)

D1 = 2×5! = 240 D2 = 2×3! = 12 D3 = 2

En remontant ces égalités, on obtient T₁ = D₁ = 240
T₂ = 12D₂ = 144
T₃ = 2D₁ + 16D₂ = 672
T₄ = 2D₂ + 4D₃ = 32
T₅ = 6D₁ + 144D₂ = 3168

Q₁ = 24T₁ + 48T₃ = 38016
Q₂ = 48T₂ + 24T₃ + 6T₅ = 42048
Q₃ = 2T₁ + 2T₃ = 1824
Q₄ = 4T₃ + 2T₅ = 9024
Q₅ = 24T₃ + 64T₄ + 8T₅ = 43520
Q₆ = 4T₂ + 2T₃ = 1920

P₁ = Q₁ + 2Q₂ = 122112
P₂ = 2Q₁ + 8Q₂ + 16Q₃ + 16Q₄ = 585984
P₃ = 2Q₂ + Q₅ = 127616
P₄ = 6Q₂ + 16Q₄ + 4Q₅ + 16Q₆ = 601472

H = 4P₁ + 4P₂ + 8P₃ + 8P₄ = 8665088
enfin E₇ = 15H = 129976320
et S₃ = 28 × 3⁷ × E₇ = 7959229931520
Il faudrait 250000 ans pour les essayer toutes, à raison d'une toutes les 10s...
Référence : Cette méthode est due à Tarry (1886), in E. Lucas "Récréations Mathématiques", en corrigeant les erreurs "typographiques" (chiffres mal recopiés, inversions de figures ...)

Et au dela

Le calcul de E_2n+1 est finalement assez pénible. On trouve le résultat tout cuit dans l'encyclopédie OEIS

E_2n+1 = A135388_n = A007082_n × (n-1)!²ⁿ⁺¹

La deuxième suite allant un peu plus loin puisque permettant d'aligner les dominos jusqu'au 20-20 (n=10, 231 dominos, K₂₁)
Ces suites ne donnent que le nombre de cycles Eulériens de K_2n+1, pour avoir les alignements de dominos il est encore nécessaire de multiplier par (n+1)(2n+1) × n²ⁿ⁺¹ comme indiqué ci-dessus.

Calcul direct

Il n'existe pas de formule connue donnant directement le nombre de circuits Eulériens de K_2n+1, ni de formule de récurrence simple.
Pour obtenir une méthode efficace, on peut exprimer E_2n+1 comme étant le terme constant d'une certaine fonction complexe (faisant intervenir les racines n^èmes de l'unité).
Ce coefficient est alors calculé modulo p, p premier, et le théorème des restes chinois permet d'en calculer sa valeur modulo le produit des nombres premiers utilisés.
Les détails sont dans ce document de McKay & Robinson.
Pour n encore plus grand (mais est-ce bien utile ?) on estime une valeur approchée asymptotique (même document)
D'autres tentatives de formule existent, malheureusement fausses (= approchées), comme une vérification soigneuse avec les premières valeurs exactes pour K₃ K₅ et K₇ le montre.
Par exemple la "fonction de Dwyer" conduit à E₇ = 126846000 au lieu de 129976320.
(Bon d'accord, le papier dit "1.3 E+8 ... so it is correct")