TAOCP 7.2.1.3 Exercise 105

Let the universal cycle be $a_0,a_1,\dots,a_{L-1}$, indexed cyclically modulo $L$, over the alphabet ${0,1,\dots,n-1}$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.3: Generating All Combinations

Exercise 105. [M20] [M20] A universal cycle of t-combinations for {0, 1, . . . , n −1} is a cycle of n t  numbers whose blocks of t consecutive elements run through every t-combination {c1, . . . , ct}. For example, (02145061320516243152630425364103546) is a universal cycle when t = 3 and n = 7. Prove that no such cycle is possible unless n t  is a multiple of n.

Verified: no
Solve time: 8m41s

Solution

Let the universal cycle be $a_0,a_1,\dots,a_{L-1}$, indexed cyclically modulo $L$, over the alphabet ${0,1,\dots,n-1}$. Every block

$(a_i,a_{i+1},\dots,a_{i+t-1})$

corresponds to a $t$-multiset, hence to a $t$-combination of ${0,1,\dots,n-1}$. By assumption, every $t$-combination appears exactly once among these $L$ cyclic windows.

The number of distinct $t$-combinations is $\binom{n}{t}$, hence $L=\binom{n}{t}$.

Fix a symbol $x \in {0,1,\dots,n-1}$. Let $f_x$ denote the number of occurrences of $x$ in the cycle $a_0,\dots,a_{L-1}$.

Each occurrence of $x$ at position $i$ belongs to exactly $t$ cyclic windows, namely the windows starting at $i-t+1,i-t+2,\dots,i$. Therefore each occurrence of $x$ contributes exactly $t$ appearances of $x$ among all windows. The total number of windows is $L$, so the total number of pairs

$(\text{window}, \text{distinguished position occupied by } x)$

counted over all windows equals $f_x t$.

Independently, each window corresponds to a $t$-combination, and each $t$-combination containing $x$ contributes exactly one such pair. The number of $t$-combinations containing $x$ is $\binom{n-1}{t-1}$, hence the same pair count equals $\binom{n-1}{t-1}$.

Equating the two expressions gives

$f_x t = \binom{n-1}{t-1},$

so

$f_x = \frac{1}{t}\binom{n-1}{t-1}.$

Since $f_x$ is an integer, $t \mid \binom{n-1}{t-1}$. Using the identity

$\binom{n}{t} = \frac{n}{t}\binom{n-1}{t-1},$

write $\binom{n-1}{t-1}=t k$ for some integer $k$. Then

$\binom{n}{t} = \frac{n}{t}\cdot t k = nk,$

so $n \mid \binom{n}{t}$.

This completes the proof. ∎