The Towers and Triangles of Professor Claus (or, Pascal Knows Hanoi)

NEW

Problem: Poole’s question is not a single formal conjecture. I reconstruct it as follows, supported by the paper context: variants 4 and 5 are the multi-disk and multi-peg Tower of Hanoi variants, and $H_n$ is the ordinary Hanoi state graph.

For integers $n\ge0$, $K\ge3$, and $m\ge1$, define $H_n^{K,m}$ as the finite simple graph whose vertices are arrays

Here $x_{i,a}$ is the number of disks of size $i$ on peg $a$, with $i=0$ smallest. Two vertices are adjacent if one disk of one size is legally moved: for some $i$ and distinct pegs $a,b$,

all other entries unchanged, $x_{i,a}>0$, and for every smaller size $j<i$,

Variant 4 is $K=3,m>1$; variant 5 is $K>3,m=1$. The ordinary graph is $H_n^{3,1}=H_n$.

Result: The required analogues exist, and they admit a Lucas-type correspondence.

The graph has

vertices. For $n\ge1$, fixing the largest-size distribution $c=(c_0,\dots,c_{K-1})$ gives an induced copy of $H_{n-1}^{K,m}$. If $c'=c-e_a+e_b$, then the edges between the two corresponding copies are indexed by smaller-disk states supported only on the $K-2$ pegs different from $a,b$, hence there are

such edges; otherwise there are none. This is the recursive Hanoi-graph analogue.

Now choose a prime $p>m$ and put

Let

For $U\in\Delta_{K,N}$, consider the multinomial coefficient

Define

By the multinomial Lucas theorem,

iff, in base $p$, the $i$-th digits $U_{0,i},\dots,U_{K-1,i}$ satisfy

for every $i<n$, and all higher digits vanish. Thus $\Phi$ is a bijection between states of $H_n^{K,m}$ and the nonzero entries modulo $p$ in the $K$-nomial Pascal simplex row $N$.

Moreover, a legal move of a disk of size $i$ from peg $a$ to peg $b$ corresponds exactly to replacing

with lower base-$p$ digits on pegs $a,b$ equal to zero. Hence legal edges are precisely the visible Lucas adjacencies among nonzero Pascal-simplex entries along root directions $e_b-e_a$.

For $K=3,m=1,p=2$, this recovers Poole’s usual Lucas correspondence with odd binomial coefficients: writing

identifies the nonzero trinomial row with the odd entries $\binom r s$ in Pascal’s triangle. Thus this is a genuine extension of the classical correspondence.

The degenerate case $n=0$ gives one empty state and the single coefficient $\binom00$. Variant 4 is obtained by setting $K=3$, and variant 5 by setting $m=1$. No extra assumptions beyond finite $n,K,m$ and a prime $p>m$ are used.

Citation: The original Lucas correspondence is from David G. Poole, “The Towers and Triangles of Professor Claus (or, Pascal Knows Hanoi),” Mathematics Magazine 67 (1994), 323–344. The proof above uses the standard multinomial form of Lucas’ theorem; the unified construction is given here.