Bulgarian Solitaire: Number of root loops and which numbers have multiple root loops

Question

For an explanation of what Bulgarian Solitaire is, look here.

I have worked out the full graphs for $1 \leq \text{number of cards} \leq 13$ in the past, and all of them had just one root loop...except for $8$ cards. In that case, there are two root loops, one of which is $(4,2,2) \to (3,3,1,1)$ (which is also the entire subgraph for that loop). So, here we have a loop of size $2$ and a loop of size $4$. Unlike my previous question, I have no good intuition as to why this is the case.

Which numbers have multiple root loops? How many do they have?

Answer 1

In Jyrki’s notation that’s the cycle from $(4,3^*,2,1^*) = (4,2,2)$ to $(4^*,3,2^*,1) = (3,3,1,1)$ and back. Here $n = 8 = T_4 - 2$, and the decrement $2$ divides $4$. In general, suppose that $n = T_k - m$, where $0<m<k$, and suppose that $m|k$. If $p=k/m$, you’ll have a cycle of length $p$ starting with $$\left(k^*,k-1,k-2,\dots,((m-1)p)^*,(m-1)p-1,\dots,p^*,p-1,\dots,2,1\right),$$ the position in which each of the $m$ multiples of $p$ is starred. The next two values of $n$ for which you’ll get a second cycle are $18 = T_6 - 3$ and $19 = T_6 - 2$; the ‘extra’ cycles for these $n$ are $$(6^*,5,4^*,3,2^*,1) = (5,5,3,3,1,1)$$ $$(6,5^*,4,3^*,2,1^*) = (6,4,4,2,2)$$ and $$(6^*,5,4,3^*,2,1) = (5,5,4,2,2,1)$$ $$(6,5^*,4,3,2^*,1) = (6,4,4,3,1,1)$$ $$(6,5,4^*,3,2,1^*) = (6,5,3,3,2)$$ respectively.

Answer 2

The Bulgarian Solitaire state diagram for $S$ has a single cycle (or fixed point) if and only if $S$ is within 1 of a triangular number. In addition to 18 & 19 mentioned before, the diagram for 17 has two components.

The number of components was given by Brandt in 1982, the first English language publication on the topic (although it does not mention the name, which was popularized by Martin Gardner). Using his notation, write $S = \binom{n+1}{2} - a$ with $0 \leq a \leq n-1$. The number of cycles for Bulgarian Solitaire on $S$ is

$$ \frac{1}{n} \sum_{d|(n,a)} \varphi(d) \binom{n/d}{a/d}$$

where $(n,a)$ denotes the greatest common divisor and $\varphi(d)$ is the Euler totient function. The length of the cycle for each $d$ is $(n+1)/d$.

Some articles on this are freely available, for instance in the Electronic Journal of Combinatorics. If you have access to the College Mathematics Journal (perhaps through JSTOR), there was a survey article in March 2012.