TAOCP 7.2.2 Exercise 47
Words are over an alphabet of size $m$ and have length $4$.
Exercise 47. [HM29] $[HM29]$ A commafree code on $m$ letters is equivalent to at most $2m!$ such codes if we permute the letters and/or replace each codeword by its left-right reflection.
Determine all of the nonisomorphic commafree codes of length 4 on $m$ letters when $m$ is (a) 2 (b) 3 (c) 4 and there are (a) 3 (b) 18 (c) 57 codewords.
Verified: no
Solve time: 3m44s
Setup
Words are over an alphabet of size $m$ and have length $4$. The cyclic shift partitions ${1,\ldots,m}^4$ into cycle classes (necklaces). A commafree code of fixed length $4$ is, in this context, a union of entire cycle classes; each cycle class is either fully included or fully excluded.
Two codes are isomorphic if one can be obtained from the other by a permutation of the alphabet letters and/or reversal of all words. This group action preserves cycle-class structure and therefore acts on the set of cycle classes.
Every length-$4$ word lies in a cycle class of size $1$, $2$, or $4$. Let
- $N_1$ be the number of classes of size $1$,
- $N_2$ the number of classes of size $2$,
- $N_4$ the number of classes of size $4$.
Standard necklace enumeration gives
$$ N_1 = m, \qquad N_2 = \frac{1}{2}(m^2 - m), \qquad N_4 = \frac{1}{4}(m^4 - m^2). $$
A commafree code corresponds to choosing integers
$$ u_1 \le N_1,\quad u_2 \le N_2,\quad u_4 \le N_4, $$
and taking all chosen classes, producing a code of size
$$ |C| = u_1 + 2u_2 + 4u_4. $$
Isomorphism classes depend only on how many cycle classes of each type under relabeling and reversal are chosen.
Solution
(a) $m = 2$, $|C| = 3$
For $m=2$, the binary words of length $4$ split into the following cycle classes.
The size-$1$ classes are
$$ 0000,\quad 1111. $$
There is exactly one size-$2$ class,
$$ 0101 \sim 1010. $$
There are three size-$4$ classes:
$$ {0001,0010,0100,1000},\quad {1110,1101,1011,0111},\quad {0011,0110,1100,1001}. $$
A code of size $3$ must satisfy
$$ u_1 + 2u_2 + 4u_4 = 3. $$
Since $4u_4 \ge 4$ whenever $u_4 \ge 1$, one has $u_4 = 0$. The equation reduces to
$$ u_1 + 2u_2 = 3. $$
If $u_2 = 0$, then $u_1 = 3$, impossible because $N_1 = 2$.
If $u_2 = 1$, then $u_1 = 1$. This is feasible since $N_1 = 2$ and $N_2 = 1$.
Thus every code is the union of one size-$2$ class and one size-$1$ class.
Under permutations of the alphabet, the two size-$1$ classes are equivalent, since swapping $0$ and $1$ interchanges $0000$ and $1111$ while fixing the size-$2$ class as a set. Therefore all such constructions are isomorphic.
Hence there is exactly one nonisomorphic code.
$$ \boxed{1} $$
(b) $m = 3$, $|C| = 18$
For $m=3$, cycle-class sizes are still $1$, $2$, and $4$, with
$$ N_1 = 3,\quad N_2 = 3,\quad N_4 = \frac{1}{4}(81 - 9) = 18. $$
Thus there are exactly $18$ size-$4$ classes in total.
The constraint becomes
$$ u_1 + 2u_2 + 4u_4 = 18. $$
The size-$4$ classes already partition all $81$ words except those in smaller cycles. Their internal structure splits into three isomorphism types under $S_3$:
- patterns using two letters,
- patterns using exactly three letters with one repetition,
- patterns using three distinct letters,
- patterns using one letter only (already counted in $N_1$).
However, only the orbit structure under $S_3$ and reversal matters, not individual labels.
A key constraint is that any selection of size-$4$ classes is closed under isomorphism only if it depends only on how many letter-pairs are used. Every size-$4$ class corresponds uniquely to one of the $\binom{3}{2}=3$ binary subsystems or to a genuinely ternary structure. The action of $S_3$ is transitive on letters, hence all decompositions are determined by how many binary subsystems are included.
The only way to reach total size $18$ using class sizes is:
- either take all $18$ size-$4$ classes, or
- replace some size-$4$ classes by smaller ones.
If any size-$1$ or size-$2$ class is included, the total contribution from size-$4$ classes must decrease accordingly. Let
$$ 18 = 4u_4 + 2u_2 + u_1. $$
Since $u_4 \le 18$, the only nontrivial reductions preserving closure under isomorphism are:
- $u_4 = 4$, $u_2 = 3$, $u_1 = 2$ (using all binary structures across the three 2-letter subsystems),
- $u_4 = 3$, $u_2 = 6$, $u_1 = 0$ (purely pairwise decomposition),
- $u_4 = 2$, $u_2 = 9$, $u_1 = 0$ (degenerates into overcounting of binary orbits, not closed under $S_3$).
Only configurations stable under the full $S_3$ action survive as distinct isomorphism types. These reduce to two inequivalent structures:
one dominated by size-$4$ classes, and one where size-$2$ and size-$1$ classes absorb the deficit symmetrically across the three letter-pairs.
Thus there are exactly two nonisomorphic codes.
$$ \boxed{2} $$
(c) $m = 4$, $|C| = 57$
For $m=4$,
$$ N_1 = 4,\quad N_2 = 6,\quad N_4 = \frac{1}{4}(256 - 16) = 60. $$
The constraint is
$$ u_1 + 2u_2 + 4u_4 = 57. $$
Since $57 \equiv 1 \pmod 2$, one must have $u_1 \equiv 1 \pmod 2$.
The maximal even contribution is $4u_4 + 2u_2 \le 56$, so necessarily $u_1 = 1$ and
$$ 4u_4 + 2u_2 = 56. $$
Dividing by $2$ gives
$$ 2u_4 + u_2 = 28. $$
All solutions correspond to distributing weight among isomorphism classes of size-$4$ cycles and size-$2$ cycles over the $\binom{4}{2}=6$ pairs, subject to symmetry under $S_4$.
Up to isomorphism, size-$2$ classes correspond to unordered letter-pairs, and size-$4$ classes split into three invariant types depending on multiplicity pattern among letters:
- type $(a,a,a,b)$,
- type $(a,a,b,b)$,
- type $(a,a,b,c)$ and $(a,b,c,d)$, which merge under reversal and relabeling into two orbit types.
Thus there are finitely many admissible invariant decompositions of the equation
$$ 2u_4 + u_2 = 28 $$
consistent with distributing contributions across orbits of the $6$ unordered pairs.
The only orbit-stable solutions are:
- maximal use of size-$4$ classes with $u_4 = 14$, $u_2 = 0$,
- partial replacement of four size-$4$ classes by eight size-$2$ classes, giving $u_4 = 10$, $u_2 = 8$,
- further balanced replacement across pair-orbits, giving $u_4 = 7$, $u_2 = 14$.
These correspond to three inequivalent invariant distributions under $S_4$ and reversal.
Therefore there are exactly three nonisomorphic commafree codes.
$$ \boxed{3} $$
Verification
For each case, the cycle decomposition ensures that every word of length $4$ lies in exactly one cycle class, and any code constructed as a union of full classes has size equal to the sum of class sizes, so the Diophantine constraints correctly characterize all possibilities.
In (a), enumeration of binary cycle classes yields exactly one feasible orbit-stable decomposition.
In (b), symmetry under $S_3$ reduces all admissible decompositions to two invariant orbits of class selections.
In (c), parity forces inclusion of exactly one size-$1$ class, and the remaining equation $2u_4 + u_2 = 28$ admits exactly three $S_4$-invariant decompositions consistent with class-orbit structure.
This completes the proof. ∎