TAOCP 7.2.1.3 Exercise 107
Let $G$ be the multigraph whose vertices are ${0,1,2,3,4,5,6}$ and whose edges are the $28$ dominoes of the double-six set, namely one edge between $i$ and $j$ for each $0 \le i \le j \le 6$, includin...
Section 7.2.1.3: Generating All Combinations
Exercise 107. [22] [22] (O. Terquem, 1849.) Poinsot’s theorem implies that all 28 dominoes of a traditional “double-six” set can be arranged in a cycle so that the spots of adjacent dominoes match each other: < 0> 0< 0> 1< 1> 3< 3> 6< 6> 6< 6> 0< 0> 2< 2> 5< 5> 5< 5> 6< 6> 1< 1> 4< 4> 4^ 4 v 5 ^ 0 v 4< 4> 2< 2> 1< 1> 1< 1> 5< 5> 3< 3> 2< 2> 2< 2> 6< 6> 4< 4> 3< 3> 3< 3> 0< 0> 5 How many such cycles are possible?
Verified: no
Solve time: 10m47s
Solution
Let $G$ be the multigraph whose vertices are ${0,1,2,3,4,5,6}$ and whose edges are the $28$ dominoes of the double-six set, namely one edge between $i$ and $j$ for each $0 \le i \le j \le 6$, including one loop at each vertex.
A valid cycle of dominoes is a cyclic ordering of all edges such that consecutive dominoes share a common endpoint. This is exactly an Euler circuit of $G$, since each edge is used once and adjacency forces continuity at vertices, including the last edge connecting back to the first.
The graph is connected and Eulerian because each vertex $v$ has degree
$$ \deg(v) = 6 + 2 = 8, $$
since it is adjacent to the other $6$ vertices and has one loop contributing $2$ to the degree. Hence $\deg(v)$ is even for all $v$, so Euler circuits exist.
To count Euler circuits, we apply the standard formula for undirected Eulerian multigraphs obtained from the BEST theorem applied to the directed line graph formulation. For a connected Eulerian multigraph $G$, the number of Euler circuits is
$$ \tau(G),\prod_{v \in V} \left(\frac{\deg(v)}{2} - 1\right)!,2^{|E| - |V| + 1}, $$
where $\tau(G)$ is the number of spanning trees of the underlying simple graph (loops do not affect spanning trees).
The underlying simple graph is $K_7$, so by Cayley’s formula,
$$ \tau(G) = 7^{7-2} = 7^5. $$
For each vertex,
$$ \frac{\deg(v)}{2} - 1 = \frac{8}{2} - 1 = 3, $$
so each factor is $3! = 6$. With seven vertices,
$$ \prod_{v \in V} \left(\frac{\deg(v)}{2} - 1\right)! = 6^7. $$
The graph has $|E| = 28$ edges and $|V| = 7$ vertices, so
$$ 2^{|E| - |V| + 1} = 2^{28 - 7 + 1} = 2^{22}. $$
Multiplying these contributions gives the number of Euler circuits:
$$ 7^5 \cdot 6^7 \cdot 2^{22}. $$
Hence the number of domino cycles is
$$ \boxed{7^5 \cdot 6^7 \cdot 2^{22}}. $$
This completes the solution. ∎