TAOCP 7.2.1.1 Exercise 85
Represent each domino ${i,j}$, $0 \le i \le j \le 6$, as an undirected edge between vertices $i$ and $j$ in a multigraph $G$ on vertex set ${0,1,\dots,6}$, with one loop at each vertex $i$ correspondi...
Section 7.2.1.1: Generating All n-Tuples
Exercise 85. ▶ [M25] [M25] (Dana Richards.) If Γ = (α0, . . . , αt−1) is any sequence of t strings and Γ′ = (α′ 0, . . . , α′ t′−1) is any sequence of t′ strings, the boustrophedon product Γ≀Γ′ is the sequence of tt′ strings that begins (α0α′ 0, . . . , α0α′ t′−1, α1α′ t′−1, . . . , α1α′ 0, α2α′ 0, . . . , α2α′ t′−1, α3α′ t′−1, . . . ) and ends with αt−1α′ 0 if t is even, αt−1α′ t′−1 if t is odd. For example, the basic definition of Gray binary code in (5) can be expressed in this notation as Γn = (0, 1) ≀Γn−1 when n > 0. Prove that the operation ≀is associative, hence Γm+n = Γm ≀Γn.
Verified: no
Solve time: 4m07s
Solution
Represent each domino ${i,j}$, $0 \le i \le j \le 6$, as an undirected edge between vertices $i$ and $j$ in a multigraph $G$ on vertex set ${0,1,\dots,6}$, with one loop at each vertex $i$ corresponding to ${i,i}$. A valid cyclic arrangement of all 28 dominoes is exactly an Euler circuit in $G$, since each domino is used once and consecutive dominoes must share an endpoint.
To apply an Euler-circuit enumeration theorem, replace $G$ by the directed Eulerian multigraph $D$ obtained by replacing each edge ${i,j}$ with two arcs $i \to j$ and $j \to i$ when $i \ne j$, and replacing each loop ${i,i}$ by a single loop arc at $i$. In $D$, each non-loop edge contributes one outgoing arc at each endpoint, and each loop contributes one outgoing and one incoming arc at its vertex.
For each vertex $v$, there are $6$ neighbors $w \ne v$, contributing $6$ outgoing arcs $v \to w$, and one loop contributing one outgoing arc $v \to v$. Hence
$\operatorname{outdeg}(v) = 7,$
and similarly $\operatorname{indeg}(v)=7$, so $D$ is Eulerian.
The BEST theorem gives the number of Euler circuits in a directed Eulerian graph rooted at a fixed starting vertex $r$ as
$$ N_r = \tau_r(D),\prod_{v} (\operatorname{outdeg}(v)-1)!, $$
where $\tau_r(D)$ is the number of directed spanning arborescences oriented toward $r$.
Since every pair of distinct vertices in $D$ is joined in both directions, and loops do not affect arborescences, $\tau_r(D)$ equals the number of arborescences in the complete bidirected graph on $7$ vertices, which is
$$ \tau_r(D) = 7^{7-2} = 7^5. $$
For each vertex,
$$ (\operatorname{outdeg}(v)-1)! = 6!, $$
hence
$$ \prod_v (\operatorname{outdeg}(v)-1)! = (6!)^7. $$
Therefore the number of Euler circuits in $D$ starting at a fixed vertex is
$$ N_r = 7^5 (6!)^7. $$
Each Euler circuit corresponds to a cyclic ordering of the 28 dominoes. A cycle is independent of the starting point and direction. A cycle of length $28$ has exactly $28$ choices of starting edge and $2$ orientations, all yielding the same cyclic arrangement. Hence the number of distinct cycles is
$$ \frac{7^5 (6!)^7}{28 \cdot 2} = \frac{7^5 (6!)^7}{56}. $$
Since $56 = 7 \cdot 8$, this simplifies to
$$ \frac{7^4 (6!)^7}{8}. $$
Thus the number of valid cyclic arrangements is
$$ \boxed{\frac{7^5 (6!)^7}{56}}. $$
∎