# Limiting behavior in growth of Bulgarian solitaire orbits

Nhung Pham111Email<EMAIL_ADDRESS>
School of Mathematics, University of Minnesota - Twin Cities
Minneapolis, MN 55455

###### Abstract

The Bulgarian Solitaire rule induces a finite dynamical system on the set of
integer partitions of $n$. Brandt [2] characterized and counted all cycles in
its recurrent set for any given $n$, with orbits parametrized by necklaces of
black and white beads. However, the transient behavior within each orbit has
been almost completely unknown. The only known case is when $n=\binom{k}{2}$
is a triangular number, in which case there is only one orbit. Eriksson and
Jonsson [3] gave an analysis for convergence of the structure as $k$ grows,
and to what extent the limit applied to the finite case.

In this article, we generalize the convergent structure for orbits of
Bulgarian Solitaire system for any $n$. For necklaces of the form
$(BW)^{k}=BWBW\cdots$, we give the precise limit of the generating functions
as $k$ grows. For other necklaces, we prove that the generating functions are
rational and provide a bound for their denominator and numerator degrees.

###### Contents

  1. 1 Introduction and Notation
    1. 1.1 The Bulgarian Solitaire system
    2. 1.2 The reversed Bulgarian Solitaire digraphs
  2. 2 The rules for producing the forest $\mathcal{F}_{P}$
  3. 3 Limiting level sizes of $\mathcal{O}^{op}_{(BW)^{k}}$ as $k$ grows
    1. 3.1 The quasi-infinite forest $\mathcal{F}_{BW}$
    2. 3.2 Proof of Theorem 1.1
  4. 4 Explanations for the rules of the general forest for primitive necklaces $\absolutevalue{P}\geq 3$
  5. 5 The limiting generating function for general $\mathcal{O}^{op}_{P^{k}}$ by level sizes
  6. 6 Further discussion and conjectures on the finite BS systems

##  1 Introduction and Notation

###  1.1 The Bulgarian Solitaire system

The game of Bulgarian Solitaire (BS) was introduced by Martin Gardner in 1983.
The original game starts with $45$ cards divided into a number of piles. Now
keep repeating the _Bulgarian Solitaire moves_ : in each turn, take one card
from each pile and form a new pile. The game ends when the sizes of the piles
are not changed by performing the moves. Surprisingly, it turns out that
regardless of initial state of the game, it must end in a finite number of
moves at the state with one pile of one card, one pile of two cards, …, and
one pile of nine cards. The rule was then generalized for any $n$ as the
Bulgarian Solitaire operation $\beta$ on the set of partition
$\mathcal{P}(n)\coloneqq\\{\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{m}):\text{length
}l(\lambda)=m,\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{m}>0\text{ are
integers},\lambda_{1}+\ldots+\lambda_{m}=n\\}$. The operation
$\lambda\rightarrow\beta(\lambda)$ is described as: in each step, take one
from each part, form a new part and put the parts in weakly decreasing order.
In addition, the game can be described in terms of Young diagrams: in each
turn, remove the longest column and reinsert it as a new row into the diagram.
An example is shown in Figure 1.

centertableaux ,, * 5,2,2 * [*(lightgray)]1,1,1$\beta$centertableaux ,, *
4,3,1,1 * [*(lightgray)]0,3  Figure 1: Bulgarian Solitaire on Young diagram
$\beta((5,2,2))=(4,3,1,1)$

The _game graph_ of Bulgarian Solitaire system is a directed graph whose
vertices are partitions of $n$ with directed edges connecting
$\lambda\rightarrow\beta(\lambda)$. Some examples of BS _game graph_ are given
in Figure 2 and Figure 3.

$({3,2,1})$$({4,2})$$({3,1,1,1})$$({2,2,2})$$({3,3})$$({4,1,1})$$({2,2,1,1})$$({5,1})$$({2,1,1,1,1})$$({6})$$({1,1,1,1,1,1})$
Figure 2: Bulgarian Solitaire game graph for $n=6.$
$({3,3,1,1})$$({4,2,2})$$({5,3})$$({4,1,1,1,1})$$({2,2,2,2})$$({6,1,1})$$({2,2,1,1,1,1})$$(3,2,2,1)$$({4,2,1,1})$$({4,3,1})$$({3,3,2})$$({4,4})$$({5,1,1,1})$$({2,2,2,1,1})$$({5,2,1})$$({3,2,1,1,1})$$({6,2})$$({3,1,1,1,1,1})$$({7,1})$$({2,1,1,1,1,1,1})$$({8})$$({1,1,1,1,1,1,1,1})$
Figure 3: Bulgarian Solitaire game graph for $n=8.$

As in any finite dynamical system, that is, any self-map $\beta:X\rightarrow
X$ on a finite set $X$, the elements in any orbit $\mathcal{O}$ under repeated
application of $\beta$ eventually lead to a recurrent cycle
$\bm{C}\subset\mathcal{O}$, consisting of the elements $\lambda$ in
$\mathcal{O}$ having $\lambda=\beta^{m}(\lambda)$ for some $m\geq 1$. When
$\beta$ is the Bulgarian solitaire map, these recurrent cycles were analyzed
by Brandt [2] in terms of objects called necklaces. A _necklace_ $N$ of black
and white beads is an equivalence class of sequences of letters $\\{B,W\\}$
under cyclic rotation. We call $N$ a _primitive necklace_ if it cannot be
written as a concatenation $N=P^{k}=PP\cdots P$ of copies of another necklace
$P$. We will reserve $P$ for _primitive necklaces_. We also say a binary
sequence _encodes_ a necklace class $N$ if the sequence represents an element
of the class $N$ when we assign $1$ for $B$ and $0$ for $W$. Brandt [2] showed
there is a bijection

$\displaystyle\mathcal{O}:\text{ necklaces }$
$\displaystyle\longrightarrow\text{ BS orbits }$ (1) $\displaystyle N$
$\displaystyle\longmapsto\mathcal{O}_{N}$

that maps a necklace to the orbit of Bulgarian Solitaire system which has the
unique recurrent cycle $\bm{C}_{N}$ represented by the necklace. Specifically,
if the necklace $N$ is of length $m$, a partition $\lambda$ is in the
corresponding recurrent cycle $\bm{C}_{N}$ if its _difference labelling_ from
the staircase $\Delta_{m-1}=(m-1,\ldots,1,0)$, defined as

$\lambda^{-}=\lambda-\Delta_{m-1},$ (2)

encodes the necklace class $N$. Figure 4 and Figure 5 visualize the bijection.

$\bm{C}_{WWW}=\left\\{\,\ytableausetup{centertableaux}\ytableaushort{\none,\none,\none}*{2,1}\,\right\\}$$\bm{C}_{BWW}=\left\\{\,\ydiagram[*(lightgray)]{2+1,1+0}*[*(white)]{2,1}\quad,\quad\ydiagram[*(lightgray)]{2+0,1+1}*[*(white)]{2,1},\quad\ydiagram[*(lightgray)]{2+0,1+0,0+1}*[*(white)]{2,1}\right\\}$$\bm{C}_{BBW}=\left\\{\,\ydiagram[*(lightgray)]{2+1,1+1}*[*(white)]{2,1}\quad,\quad\ydiagram[*(lightgray)]{2+0,1+1,0+1}*[*(white)]{2,1},\quad\ydiagram[*(lightgray)]{2+1,1+0,0+1}*[*(white)]{2,1}\right\\}$
Figure 4: The map $\mathcal{O}$ for necklaces of length $3$, which are $WWW$
(non-primitive) and $BWW,BBW$ (primitive).

$\mathcal{C}_{(BW)^{2}}=\left\\{\,\ydiagram[*(lightgray)]{3+1,2+0,1+1}*[*(white)]{3,2,1}\quad,\quad\ydiagram[*(lightgray)]{3+0,2+1,1+0,0+1}*[*(white)]{3,2,1}\right\\}$

Figure 5: The map $\mathcal{O}$ for non-primitive necklaces of length $4$. The
recurrent set in $\mathcal{O}_{(BW)^{2}}$

has only $2$ elements, shown above.

We will also be interested in the non-recurrent elements $\lambda$ in
$\mathcal{O}_{N}$, and the distribution of the following level statistic on
the orbit:

$\mathrm{level}(\lambda):=\min\\{m\in\\{0,1,2,\ldots\\}:\beta^{m}(\lambda)\in\bm{C}_{N}\\}.$

Our main results concern its generating function, which is defined as the
following polynomial in $\mathbb{Z}[x]$:

$\mathcal{D}_{N}(x):=\sum_{\lambda\in\mathcal{O}_{N}}x^{\mathrm{level}(\lambda)}.$

Note that Brandt’s bijection implies that the Bulgarian solitaire system on
$\mathcal{P}(n)$ for $n=\binom{k+1}{2}$ has only one orbit
$\mathcal{O}_{W^{k+1}}$ with the recurrent set
$\bm{C}_{W^{k+1}}=\\{\Delta_{k}\\}$. Thus the game graph
$\mathcal{O}_{W^{k+1}}$ turns out to be a tree, rooted at the vertex
$\Delta_{k}$, and for any partition $\lambda\in\mathcal{O}_{W^{k+1}}$, the
statistic $\mathrm{level}(\lambda)$ is the distance in the tree from $\lambda$
to the staircase $\Delta_{k}$. Eriksson and Jonsson prove [3] that, in the
limit as $k$ grows, the sequence of level sizes of $\mathcal{O}_{W^{k}}$
converges to the subsequence of evenly-indexed Fibonacci numbers
$(F_{2d})_{d=0}^{\infty}$, with the generating function

$\lim_{k\rightarrow\infty}\mathcal{D}_{W^{k}}(x)=\dfrac{(1-x)^{2}}{1-3x+x^{2}}=:H_{W}(x).$
(3)

Eriksson and Jonsson also showed that for $\mathcal{O}_{W^{k+1}}$, the sizes
of levels $0,1,\ldots,\lfloor\frac{k}{2}\rfloor$ in the Bulgarian solitaire
game tree coincide with those of an object that they called the quasi-infinite
game tree after pruning an appropriate branch (described later in this
section).

We generalize this, describing the limit of the level sizes for arbitrary $n$,
with these two main results:

######  Theorem 1.1.

There is a power series $H_{BW}(x)$ in $\mathbb{Z}[[x]]$ such that

$\lim_{k\rightarrow\infty}\mathcal{D}_{(BW)^{k}}=H_{BW}(x).$

Moreover, $H_{BW}(x)$ is a rational function, given by

$\displaystyle H_{BW}(x)$
$\displaystyle=\dfrac{(x-1)^{2}(3x+2)}{x^{3}-3x^{2}-x+1}$
$\displaystyle=2+x+3x^{2}+7x^{3}+15x^{4}+33x^{5}+71x^{6}+155x^{7}+335x^{8}+\ldots$

######  Theorem 1.2.

For primitive necklaces $P$ with $\absolutevalue{P}\geq 3$, there is a power
series $H_{P}(x)$ in $\mathbb{Z}[[x]]$ such that the sequence of generating
functions $(\mathcal{D}_{P^{k}})_{k=0}^{\infty}$ converges to $H_{P}(x)$
coefficient-wise. Moreover, $H_{P}(x)$ is a rational function having
denominator polynomial of degree at most $\absolutevalue{P}$ and numerator
degree at most $2\absolutevalue{P}$.

###  1.2 The reversed Bulgarian Solitaire digraphs

######  Definition 1.1 (reversed BS rule).

The forward Bulgarian solitaire map $\lambda\mapsto\beta(\lambda)$ has
(partially defined) reverse maps, which we will denote
$\lambda\xrightarrow{j}R_{j}(\lambda)$, for which
$\beta(R_{j}(\lambda))=\lambda$. They are described as follows:

  * •

For Young diagrams: take out the $j{th}$ row if it is no shorter than the
number of rows minus $1$ and insert it again as the leftmost column.

  * •

For a partition $\lambda$: take a part $\lambda_{j}\geq l(\lambda)-1$, then
distribute it into other parts, one for each.

For example $(4,2,2)\xrightarrow{1}(3,3,1,1)$ and
$(4,2,2)\xrightarrow{2}(5,3)$. Figure 6 illustrates the reverse rule.

centertableaux ,, * 4,2,2 * [*(lightgray)]4 * [*(gray)]0,2$1$$2$centertableaux
,, * 3,3,1,1 * [*(lightgray)]1,1,1,1centertableaux ,, * 5,3 * [*(gray)]1,1
Figure 6: Reverse BS on a Young diagram

We also use $\mathbf{0}$ as a result of an invalid move, that is, the removed
row is too short to be the leftmost (longest) column. Obviously, if $\lambda$
is a partition, $R_{j}(\lambda)$ is valid (or legal) if and only if
$\lambda_{j}\geq l(\lambda)-1$ and we display $\lambda_{j}$ in brackets, as
$\langle\lambda_{j}\rangle$. If $\lambda\in\mathcal{O}_{N}$ where $N$ is a
necklace of length $m$, then its _difference labelling_ $\lambda^{-}$ is
defined the same as in (2). Also, if $\lambda_{j}$ is bracketed, so is
$(\lambda^{-})_{j}$.

######  Example 1 (bracketing rule).

In $\mathcal{O}_{W^{4}}$ in Figure 2 we have

$\left(\small\begin{matrix}\langle{3}\rangle\\\ \langle{2}\rangle\\\
1\end{matrix}\right)^{-}=\small\begin{matrix}\langle{0}\rangle\\\
\langle{0}\rangle\\\ 0\\\ 0\end{matrix}\text{ and
}\left(\small\begin{matrix}\langle{5}\rangle\\\
\langle{1}\rangle\end{matrix}\right)^{-}=\small\begin{matrix}\langle{2}\rangle\\\
\langle{-1}\rangle\\\ -1\\\ 0\end{matrix}.$

In the left orbit $\mathcal{O}_{(BW)^{2}}$ of Figure 3 we have

$\left(\small\begin{matrix}\langle{4}\rangle\\\ \langle{2}\rangle\\\
\langle{2}\rangle\end{matrix}\right)^{-}=\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\ \langle{1}\rangle\\\ 0\end{matrix}\text{ and
}\left(\small\begin{matrix}\langle{4}\rangle\\\ 1\\\ 1\\\
1\end{matrix}\right)^{-}=\small\begin{matrix}\langle{1}\rangle\\\ -1\\\ 0\\\
1\end{matrix}.$

Note that a staircase has its last part to be $0$ while a partition requires
all parts to be positive. Also, a _difference labelling_ does not necessarily
have positive parts. The inverse is denoted

$\mu^{+}=\mu+\Delta_{m-1},$

where $\mu$ is a difference labelling in the orbit $\mathcal{O}_{N}$ and
$\mu^{+}$ must be an ordinary partition. For example, the inverses for
difference labelings in Example 1 are

$\left(\small\begin{matrix}\langle{0}\rangle\\\ \langle{0}\rangle\\\ 0\\\
0\end{matrix}\right)^{+}=\small\begin{matrix}\langle{3}\rangle\\\
\langle{2}\rangle\\\ 1\end{matrix}\,\text{ and
}\left(\small\begin{matrix}\langle{2}\rangle\\\ \langle{-1}\rangle\\\ -1\\\
0\end{matrix}\right)^{+}=\small\begin{matrix}\langle{5}\rangle\\\
\langle{1}\rangle\end{matrix}.$

The reversed BS rule reverses all the arrows in $\mathcal{O}_{N}$ for some
necklace $N$ to get the digraph $\mathcal{O}_{N}^{\mathrm{op}}$. A _(reverse
BS) playing sequence_ $\sigma$ from $\lambda$ is a sequence of parts that are
consecutively played legally starting from $\lambda$. We use
$R_{\sigma}(\lambda)$ to represent the result of performing $\sigma$ from
$\lambda$.

######  Example 2 ((reverse BS) playing sequence).

When reversing all the arrows in Figure 2 and Figure 3, we get
$\mathcal{O}^{op}_{W^{4}}$, $\mathcal{O}^{op}_{(BW)^{2}}$ and
$\mathcal{O}^{op}_{BBWW}$, respectively. A playing sequence from $(3,2,1)$ in
$\mathcal{O}^{op}_{W^{4}}$ is $[121]$ and $R_{[121]}((3,2,1))=(2,1,1,1,1)$. A
playing sequence from $(3,3,1,1)$ in $\mathcal{O}^{op}_{(BW)^{2}}$ can be
$[1111\ldots]$, where $R_{[1^{2t}]}((3,3,1,1))=(3,3,1,1)$ and
$R_{[1^{2t+1}]}((3,3,1,1))=(4,2,2)$ for integer $t$.

For any primitive necklace $P$ of length $p$, there are $p$ elements in the
recurrent set $\bm{C}_{P^{k}}$ for any $k$. We consider the difference
labellings of the elements in the recurrent set $\bm{C}_{P}$, which are
$\\{0,1\\}$-vectors of length $p$ that encode necklace class $P$. Their
playable parts are bracketed following specific rules given in Section 4. Let
that set be

$\mathcal{C}_{P}=\\{\gamma^{(t)}\in\bm{C}_{P}:R_{1}(\gamma^{(t)})=\gamma^{(t+1)},1\leq
t\leq p\text{ and }\gamma^{(p+1)}\equiv\gamma^{(1)}\\}.$

######  Example 3.

$\mathcal{C}_{BWW}=\\{BWW,WWB,WBW\\}=\Bigg{\\{}\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\ 0\end{matrix},\small\begin{matrix}\langle{0}\rangle\\\
0\\\ 1\end{matrix},\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\\\ 0\end{matrix}\Bigg{\\}}.$

For some vector $\alpha$, we will use $\alpha^{k}$ for the concatenation
$\small\begin{matrix}\alpha\\\ \vdots\\\ \alpha\end{matrix}$ of $k$ blocks
$\alpha$. Brandt’s bijection [2] maps necklace $P^{k}$ to the orbit whose
recurrent cycle
$\mathcal{C}_{P^{k}}=\\{(\gamma^{(t)})^{k}:\gamma^{(t)}\in\mathcal{C}_{P}\\}$.
We also use

$\mathcal{C}_{P^{k}}^{+}:=\\{\alpha^{+}:\alpha\in\mathcal{C}_{P^{k}}\\}$

for the ordinary recurrent set (whose elements are the same as those of
$\bm{C}_{P^{k}}$ but their playable parts are bracketed). The bracketing rule
for this set will be discussed in Section 4.

With the definition of the reversed rule in hand, we now discuss Eriksson and
Jonsson’s _quasi-infinite game tree_ $\mathcal{F}_{W}$ for orbits
$\mathcal{O}^{op}_{W^{k}}$. Figure 7 display some initial difference reversed
BS game graphs up to some levels and Figure 8 is the _quasi-infinite game
tree_ $\mathcal{F}_{W}$. After pruning the branch formed by playing sequences
$[1\ldots]$ and adding a self-cycle to the root, we can see the coincidence
between the _quasi-infinite tree_ and the finite trees up to some levels.

$\langle{0}\rangle$$1$$\small\begin{matrix}\langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$\small\begin{matrix}\langle{1}\rangle\\\
-1\end{matrix}$$\small\begin{matrix}-1\\\ 0\\\
1\end{matrix}$$2$$1$$1$$\small\begin{matrix}\langle{0}\rangle\\\
\langle{0}\rangle\\\ 0\end{matrix}$$\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\ -1\end{matrix}$$\small\begin{matrix}\langle{0}\rangle\\\
-1\\\ 0\\\ 1\end{matrix}$$\small\begin{matrix}\langle{-1}\rangle\\\ 0\\\
1\end{matrix}$$\ldots$$\small\begin{matrix}\langle{2}\rangle\\\ -1\\\
-1\end{matrix}$$\small\begin{matrix}-1\\\ -1\\\
\vdots\end{matrix}$$\small\begin{matrix}\langle{3}\rangle\\\ -2\\\
-1\end{matrix}$$\ldots$$2$$1$$1$$2$$1$$2$$1$$\small\begin{matrix}\langle{0}\rangle\\\
\langle{0}\rangle\\\ 0\\\
0\end{matrix}$$\small\begin{matrix}\langle{1}\rangle\\\ \langle{0}\rangle\\\
0\\\ -1\end{matrix}$$\small\begin{matrix}\langle{0}\rangle\\\ 0\\\ -1\\\ 0\\\
1\end{matrix}$$\small\begin{matrix}\langle{0}\rangle\\\ -1\\\ 0\\\
1\end{matrix}$$\ldots$$\small\begin{matrix}\langle{2}\rangle\\\
\langle{0}\rangle\\\ -1\\\
-1\end{matrix}$$\small\begin{matrix}\langle{0}\rangle\\\ -1\\\ -1\\\ 0\\\
\vdots\end{matrix}$$\small\begin{matrix}\langle{3}\rangle\\\ -1\\\ -1\\\
-1\end{matrix}$$\ldots$$\small\begin{matrix}\langle{2}\rangle\\\
\langle{1}\rangle\\\ -2\\\
-1\end{matrix}$$\small\begin{matrix}\langle{1}\rangle\\\ -2\\\ -1\\\
\vdots\end{matrix}$$\small\begin{matrix}\langle{3}\rangle\\\ -2\\\ -1\\\
0\end{matrix}$$\ldots$$2$$1$$1$$2$$1$$2$$3$$1$$2$$1$ Figure 7: Difference
reversed BS game graph for $n=\binom{k+1}{2}$ with $k=1,2,3,4$ up to level
$\lfloor\frac{k+1}{2}\rfloor+1$. $\small\begin{matrix}\langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$1$$\small\begin{matrix}\langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$\ldots$$2$$\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$1$$\small\begin{matrix}\langle{0}\rangle\\\
0\end{matrix}$$\small\begin{matrix}\langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$\ldots$$2$$\small\begin{matrix}\langle{2}\rangle\\\
\langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$1$$\small\begin{matrix}0\\\
0\end{matrix}$$2$$\small\begin{matrix}\langle{3}\rangle\\\
\langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$\ldots$$3$$\small\begin{matrix}\langle{3}\rangle\\\
\langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$\ldots$$3$$\small\begin{matrix}\langle{2}\rangle\\\
\langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$1$$\small\begin{matrix}\langle{1}\rangle\\\
0\\\ 0\end{matrix}$$\ldots$$2$$\small\begin{matrix}\langle{3}\rangle\\\
\langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$\ldots$$3$$\small\begin{matrix}\langle{3}\rangle\\\
\langle{2}\rangle\\\ \langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$\ldots$$4$$\small\begin{matrix}\langle{3}\rangle\\\
\langle{2}\rangle\\\ \langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{0}\rangle\end{matrix}$$\ldots$ Figure 8: The _quasi-infinite game
tree_ $\mathcal{F}_{W}$.

Recall that $\mathcal{C}_{W^{k}}=\\{(0)^{k}\\}$. $\mathcal{F}_{W}$ starts at
$\small\begin{matrix}\langle{0}\rangle\\\ \langle{0}\rangle\end{matrix}$ which
represents all bracketed parts in the roots of any trees
$\mathcal{O}^{op}_{W^{k}}$ for $k\geq 2$. The rules for $\xrightarrow{i}$ in
the _quasi-infinite game tree_ [3, §3] are described below:

  1. 1.

Delete the bracketed $i$th part.

  2. 2.

Increase all parts above it by $1$ and make them bracketed.

  3. 3.

Bracket the new $i$th part (if there is one) if it differs at most $1$ from
the old one.

  4. 4.

If a zero was played, add zeros at the end so that there are two, and make
them bracketed.

Eriksson and Jonsson [3] showed

$\mathcal{O}^{\mathrm{op}}_{W^{\infty}}=\lim_{m\rightarrow\infty}\mathcal{O}^{\mathrm{op}}_{W^{m}}.$

Generalizing that idea, we will build a _P-quasi-infinite forest_
$\mathcal{F}_{P}$ consists of $t$ trees denoted $G_{1},\ldots,G_{p}$, with
$G_{t}$ rooted at $\gamma^{(t)}\in\mathcal{C}_{P}$. The remaining vertices of
$G_{t}$ are generated from $\gamma^{(t)}$ by applying the reverse BS
operations $R_{i}$ in all possible ways, and modifying the parts according to
rules described in the next section. An example is the $BWWW$-quasi-infinite
forest in Figure 9.

$G_{1}$$\boldsymbol{\small\begin{matrix}\langle{0}\rangle\\\ 0\\\ 0\\\
1\end{matrix}}$$\boldsymbol{\small\begin{matrix}\langle{0}\rangle\\\
\langle{0}\rangle\\\ \langle{1}\rangle\\\
0\end{matrix}}$$1$$\ldots$$G_{2}$$\boldsymbol{\small\begin{matrix}\langle{0}\rangle\\\
\langle{0}\rangle\\\ \langle{1}\rangle\\\
0\end{matrix}}$$\boldsymbol{\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\\\ 0\\\
0\end{matrix}}$$1$$\ldots$$\small\begin{matrix}\langle{1}\rangle\\\
\bm{\langle{1}\rangle}\\\ \bm{\langle{0}\rangle}\\\ \bm{0}\\\
\bm{0}\end{matrix}$$2/3$$\small\begin{matrix}\langle{1}\rangle\\\ 0\\\ 0\\\
0\end{matrix}$$1$$\boldsymbol{\small\begin{matrix}\langle{0}\rangle\\\ 0\\\
0\\\ 1\end{matrix}}$$1$$\small\begin{matrix}\langle{2}\rangle\\\
\bm{\langle{0}\rangle}\\\ \bm{0}\\\ \bm{0}\\\
\bm{1}\end{matrix}$$2$$\ldots$$\small\begin{matrix}\langle{2}\rangle\\\
\langle{2}\rangle\\\ \bm{\langle{0}\rangle}\\\ \bm{\langle{0}\rangle}\\\
\bm{\langle{1}\rangle}\\\
\bm{0}\end{matrix}$$3$$\ldots$$G_{3}$$\boldsymbol{\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\\\ 0\\\
0\end{matrix}}$$\boldsymbol{\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\ 0\\\
0\end{matrix}}$$1/2$$\ldots$$G_{4}$$\boldsymbol{\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\ 0\\\
0\end{matrix}}$$\boldsymbol{\small\begin{matrix}\langle{0}\rangle\\\ 0\\\ 0\\\
1\end{matrix}}$$1$$\ldots$$\small\begin{matrix}\langle{2}\rangle\\\
\bm{\langle{0}\rangle}\\\ \bm{\langle{0}\rangle}\\\ \bm{\langle{1}\rangle}\\\
\bm{0}\end{matrix}$$2$$\small\begin{matrix}0\\\ 0\\\ 1\\\
0\end{matrix}$$1$$\small\begin{matrix}\langle{3}\rangle\\\
\bm{\langle{0}\rangle}\\\ \bm{\langle{1}\rangle}\\\ \bm{0}\\\
\bm{0}\end{matrix}$$2$$\ldots$$\small\begin{matrix}\langle{3}\rangle\\\
\langle{1}\rangle\\\ \bm{\langle{1}\rangle}\\\ \bm{\langle{0}\rangle}\\\
\bm{0}\\\ \bm{0}\end{matrix}$$3$$\ldots$ Figure 9: BWWW quasi-infinite forest.
The bold entries are $\gamma^{(t)}$ for some $t$.

Let $d(\lambda,\gamma^{(t)})$ be the length of the reversed playing sequence
from $\gamma^{(t)}$ to $\lambda$. Let $g_{t}(x)$ be the generating functions
by level sizes (the growth function) of $G_{t}$, that is,

$g_{t}(x):=\sum_{\lambda\in G_{t}}x^{d(\lambda,\gamma^{(t)})}.$

We will show later that

$\mathcal{O}^{op}_{P^{\infty}}$ $=\lim_{k\rightarrow\infty}$
$\mathcal{O}^{op}_{P^{k}}$

is the quasi-infinite forest $\mathcal{F}_{P}$ after pruning the branches
formed by playing sequences $[1\ldots]$ and adding arrows
$\gamma^{(t)}\xrightarrow{1}\gamma^{(t+1)}$ to make the roots a recurrent
cycle. In fact, up to level $k$, the finite digraph $\mathcal{O}^{op}_{P^{k}}$
coincides with the limit digraph $\mathcal{O}^{op}_{P^{\infty}}$.

##  2 The rules for producing the forest $\mathcal{F}_{P}$

The idea for the _P-quasi-infinite forest_ is that each root $\gamma^{(t)}$ is
actually an infinite periodic binary vector whose consecutive segments
$(\gamma^{(t)}_{mp+1},\ldots,\gamma^{(t)}_{(m+1)p})$ of length $p$ each forms
a copy of $\gamma^{(t)}$. The reason for this beginning will be explained in
the next section. This infinite vector guarantees that we will not encounter
negative parts in difference labellings when performing the $R_{j}$ operations
as in the finite cases. However, we cannot write out infinite-length vectors
for the elements in the forest. Instead, we start with only one block and add
more blocks as one goes further down the tree $G_{t}$ and applies the
operators $R_{j}$. In fact, each segment
$(\gamma^{(t)}_{mp+s},\ldots,\gamma^{(t)}_{(m+1)p+s-1})$ is a copy of the root
$\gamma^{(t+s)}$ for any nonegative integers $m,s$.

In this section, for a vector $\lambda=(\lambda_{1},\ldots,\lambda_{m})$ and
$j\leq k$, we write $\lambda[j:k]=(\lambda_{j},\ldots,\lambda_{k})$. Also
denote $\lambda_{j}=\lambda[1:j]$ and
$\lambda[j:]=(\lambda_{j},\ldots,\lambda_{m})$.

As part of the rules, we will want to maintain the property that every
$\lambda$ in the forest $\mathcal{F}_{P}$ has a _tail_ (= final segment of
length $p$) exactly matching one of the roots $\gamma^{(t)}$, although the
subscript $t$ may not match the subscript $t^{\prime}$ of the tree
$G_{t^{\prime}}$ which contains $\lambda$. Assume in the rules below that
$\lambda$’s tail matches the root $\gamma^{(t)}$. Rules for
$\lambda\xrightarrow{i}R_{i}(\lambda)$ in the tree $G_{t}$ in general quasi-
infinite forest - that is, $\lambda_{i}$ is bracketed and $R_{i}$ is played:

  1. 1.

If $\lambda_{i}$ is in the tail (among the lowest $p$ parts), append to
$\lambda$ so that $\lambda[i:]=\gamma^{(s)}$ for some (unique) $s$. Replace
$\lambda[i:]$ by $\gamma^{(s+1)}$ and bracket the tail as in the root
$\gamma^{(s+1)}$.

  2. 2.

Otherwise, delete $\lambda_{i}$. If $\small\begin{matrix}\lambda_{i}\\\
\lambda_{i+1}\end{matrix}=\small\begin{matrix}s\\\ s+1\end{matrix}$, playing
either $R_{i}$ or $R_{i+1}$ has the same result, so we label the play by
$\xrightarrow{i/i+1}$ and apply $R_{i+1}$. Bracket the new $i^{th}$ part (if
there is one) if it differs at most $1$ from $\lambda_{i}$. If there are two
consecutive entries $\small\begin{matrix}s\\\ s+1\end{matrix}$ and $s$ is
bracketed, so is $s+1$.

  3. 3.

Increase all entries $\lambda[:(i-1)]$ by $1$ each, and bracket them.

Here is an example of these rules in the $BWWW$ quasi-infinite forest from
Figure 9.

######  Example 4.

Let $\lambda=\small\begin{matrix}\langle{2}\rangle\\\
\bm{\langle{0}\rangle}\\\ \bm{\langle{0}\rangle}\\\ \bm{\langle{1}\rangle}\\\
\bm{0}\end{matrix}$. The bold parts are $\gamma^{(2)}$.

  * •

Play $\lambda\xrightarrow{3}R_{3}(\lambda)$:

    1. Step 1:

Note that $\lambda_{3}$ is among the last $4$ parts, we append to
$\;\lambda\longrightarrow\small\begin{matrix}\langle{2}\rangle\\\
\langle{0}\rangle\\\ \bm{\langle{0}\rangle}\\\ \bm{\langle{1}\rangle}\\\
\bm{0}\\\ \bm{0}\end{matrix}\,,\,$ so that $\lambda[3:]=\gamma^{(3)}$.

    2. Step 2:

Replace the tail $\gamma^{(3)}$ by $\gamma^{(4)}$ and bracket as in
$\gamma^{(4)}$: $\;\small\begin{matrix}\langle{2}\rangle\\\
\langle{0}\rangle\\\ \bm{\langle{0}\rangle}\\\ \bm{\langle{1}\rangle}\\\
\bm{0}\\\
\bm{0}\end{matrix}\longrightarrow\small\begin{matrix}\langle{2}\rangle\\\
\langle{0}\rangle\\\ \bm{\langle{1}\rangle}\\\ \bm{\langle{0}\rangle}\\\
\bm{0}\\\ \bm{0}\end{matrix}.$

    3. Step 3:

Add $1$ to each parts in $\lambda[:2]$ to get
$R_{3}(\lambda)=\small\begin{matrix}\langle{3}\rangle\\\ \langle{1}\rangle\\\
\bm{\langle{1}\rangle}\\\ \bm{\langle{0}\rangle}\\\ \bm{0}\\\
\bm{0}\end{matrix}.$

  * •

Play $\lambda\xrightarrow{1}R_{1}(\lambda)$. Note that $\lambda_{1}$ is not
among the last $4$ parts, so rule $2$ applies to obtain
$R_{1}(\lambda)=\small\begin{matrix}0\\\ 0\\\ 1\\\ 0\end{matrix}\;,$ because
the new first part, $0$, differs from $\lambda_{1}$ by $2$.

##  3 Limiting level sizes of $\mathcal{O}^{op}_{(BW)^{k}}$ as $k$ grows

###  3.1 The quasi-infinite forest $\mathcal{F}_{BW}$

We first analyze $P=BW$. The exception in this case is that the root
$\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\end{matrix}\in\mathcal{C}_{BW}$ we defined in Section 1 does
not reflect all the playable parts in $\mathcal{C}_{(BW)^{k}}^{+}$ for $k\geq
2$ (e.g $\small\begin{matrix}\langle{3}\rangle\\\ \langle{2}\rangle\\\
\langle{1}\rangle\\\ 0\end{matrix}$). However,
$\small\begin{matrix}\langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$ does, by the same argument as in Proposition
4.1 in Section 4. Thus, we build the forest $\mathcal{F}_{BW}$ as in Figure 10
following the rules given in the Section 2, except that the roots are
$\gamma^{(1)}=\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$ and
$\gamma^{(2)}=\small\begin{matrix}\langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$.

$\bm{G_{1}}$$\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$$1/2$$\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$$\ldots$$\ldots$$\bm{G_{2}}$$\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$$1$$\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$$\ldots$$2/3$$\small\begin{matrix}\langle{2}\rangle\\\
\langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$$1$$\small\begin{matrix}\langle{1}\rangle\\\
0\\\ 1\end{matrix}$$1$$\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$$\ldots$$2$$\small\begin{matrix}\langle{3}\rangle\\\
\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$$1$$\small\begin{matrix}0\\\
1\end{matrix}$$2/3$$\small\begin{matrix}\langle{4}\rangle\\\
\langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$$\ldots$$3/4$$\small\begin{matrix}\langle{3}\rangle\\\
\langle{2}\rangle\\\ \langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$$1$$\small\begin{matrix}\langle{2}\rangle\\\
1\\\ 0\\\ 1\end{matrix}$$\ldots$$2$$\small\begin{matrix}\langle{4}\rangle\\\
\langle{1}\rangle\\\ 0\\\
1\end{matrix}$$\ldots$$3$$\small\begin{matrix}\langle{4}\rangle\\\
\langle{3}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$$\ldots$$4/5$$\small\begin{matrix}\langle{4}\rangle\\\
\langle{3}\rangle\\\ \langle{2}\rangle\\\ \langle{1}\rangle\\\
\langle{0}\rangle\\\ \langle{1}\rangle\end{matrix}$$\ldots$ Figure 10:
$BW$-quasi-infinite $\mathcal{F}_{BW}$.

###  3.2 Proof of Theorem 1.1

Let $g(x)$ be the generating function for the level sizes of
$\mathcal{F}_{BW}$, then $g(x)=g_{1}(x)+g_{2}(x).$ Starting from
$\gamma^{(1)}$, we play $R_{1/2}$ (the only playable part) and get back to the
root $\gamma^{(2)}$. Thus the level generating functions of the two trees
satisfy

$g_{1}(x)=1+xg_{2}(x).$ (4)

As a reminder, if we have $\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$ in a difference $\lambda$, adding a staircase
makes their values the same. Thus playing either of them results in the same
element. To represent this move in a playing sequence, we will use the vertex
with $\langle{0}\rangle$ on it. Moreover, we use the notation $R_{\sigma}$ for
playing sequences in the quasi-infinite game graph similarly to the normal BS
game graph. e.g. $R_{[222]}\left(\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}\right)=\small\begin{matrix}\langle{4}\rangle\\\
\langle{1}\rangle\\\ \langle{0}\rangle\\\ \langle{1}\rangle\end{matrix}$.

Similarly to Jonsson and Eriksson’s paper [3, Proposition 3.1, p. 4], we have
the following proposition:

######  Proposition 3.1.

The tree $G_{2}$ rooted at
$\gamma^{(2)}=\small\begin{matrix}\langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$ has the following properties:

  1. i.

Once $R_{1}$ is played, only $R_{1}$ can be played (until
$\gamma^{(1)}=\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$ or a leaf is reached).

  2. ii.

For $r\geq 2$, the playing sequence $[234\ldots r1^{r}]$ leads to
$\gamma^{(1)}$.

###### Proof.

  * i.

When we play $R_{1}$, if the second part differs from the first part by at
least $2$, nothing is bracketed in the next state, thus we reach the leaf.
Otherwise, according to the rule $3$, either we reach the root
$\small\begin{matrix}\langle{0}\rangle\\\ \langle{1}\rangle\end{matrix}$ if
the second and third parts are $\small\begin{matrix}0\\\ 1\end{matrix}$ or the
only bracketed part in the next state is the first part.

  * ii.

It is easy to see that

$R_{[23\ldots r]}\left({\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}}\right)={\small\begin{matrix}\langle{r}\rangle\\\
\langle{r-1}\rangle\\\ \vdots\\\ \langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}}$

and thus playing $[1^{r}]$ consecutively deletes the first $r$ rows and
reaches $\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$. From property $i$, we see that this is the
only way to get back to the roots.

∎

Now we give the proof of Theorem 1.1:

We begin by using Proposition 3.1 to construct the _growth function_ , or the
generating function of $g_{2}$ by its level sizes. Table 1 shows various
playing sequences and their contributions to the generating function
$g_{2}(x)$, explained below. We use $[\geq t]$ to denote the set of playing
sequence with entries no less than $t$, including the empty sequence.

Sequence | Contribution | Sequence | Contribution
---|---|---|---
$[1\ldots]$ | $xg_{1}$ | $[2[\geq 2]]$ | $xg_{2}$
$[21^{2}\ldots]$ | $x^{3}g_{1}$ | $[2[\geq 2]1]$ | $x^{2}g_{2}$
$[231^{3}\ldots]$ | $x^{5}g_{1}$ | $[23[\geq 3]1^{2}]$ | $x^{4}g_{2}$
$[2341^{4}\ldots]$ | $x^{7}g_{1}$ | $[234[\geq 4]1^{3}]$ | $x^{6}g_{2}$
Table 1: Growth function for tree $G_{2}$.

By Proposition 3.1.ii., the sequences $[23\ldots r1^{r}]$ lead to the root of
$G_{1}$, so each of them contribute the whole $G_{1}$ tree at level $2r-1$,
that is, $x^{2r-1}g_{1}(x)$. This is also true for playing sequence $[1]$,
since $R_{1}\left(\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}\right)=\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$.

Next, if we play $R_{2}$, we reach $\small\begin{matrix}\langle{2}\rangle\\\
\langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}=\small\begin{matrix}\langle{2}\rangle\\\
\gamma_{2}\end{matrix}$. Thus if we leave the top part untouched, which means
we only play parts of indices greater or equal than $2$, then we have a
subtree that is isomorphic to $G_{2}$. The isomorphism is defined by excluding
the top part. Thus sequences $[2[\geq 2]]$ contribute $xg_{2}$. Similarly with
$[23\ldots r[\geq r]1^{r-1}]$, each contributes $x^{2r-2}g_{2}$, since

$R_{[23\ldots
r]}\left(\gamma_{2}\right)=\small\begin{matrix}\langle{r}\rangle\\\
\langle{r-1}\rangle\\\ \vdots\\\ \langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}=\small\begin{matrix}\langle{r}\rangle\\\
\langle{r-1}\rangle\\\ \vdots\\\ \gamma_{2}\end{matrix}.$

If we play $[23\ldots r[\geq r]]$, the top $r-1$ rows above
$\small\begin{matrix}\langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$ are always playable due to rule $2$. Thus the
playing sequences $[23\ldots r[\geq r]1^{s}]$ with any $s\leq r-1$ are legal.
For each $r\geq 2$, we only count for $[23\ldots r[\geq r]1^{r}]$, since if
$s<r$, $[23\ldots r[\geq r]1^{s}]$ are counted as $[23\ldots s[\geq s]1^{s}]$.
Hence, the type $[23\ldots r[\geq r]1^{r-1}]$ contributes $x^{2r-2}g_{2}$.

Therefore, we obtain

$\displaystyle g_{2}(x)$
$\displaystyle=1+(x+x^{3}+\ldots)g_{1}(x)+(x+x^{2}+x^{4}+\ldots)g_{2}(x)$
$\displaystyle=1+(x+x^{3}+\ldots)+(x+2x^{2}+2x^{4}+\ldots)g_{2}(x)\qquad\text{(substituting
for }g_{1}(x)\text{ using \eqref{relating-the-two-trees}})$
$\displaystyle=\left(1+\dfrac{x}{1-x^{2}}\right)+xg_{2}(x)+\dfrac{2x^{2}}{1-x^{2}}g_{2}(x)$

Bring all occurrences of $g_{2}(x)$ to the left side gives

$\dfrac{x^{3}-3x^{2}-x+1}{1-x^{2}}g_{2}(x)=\dfrac{-x^{2}+x+1}{1-x^{2}}$

and therefore

$g_{2}(x)=\dfrac{-x^{2}+x+1}{x^{3}-3x^{2}-x+1}.$

From this one concludes, again using (4), that

$\displaystyle g(x)$
$\displaystyle=g_{1}(x)+g_{2}(x)=(1+xg_{2}(x))+g_{2}(x)=1+(1+x)g_{2}(x)$
$\displaystyle=\dfrac{-3x^{2}+x+2}{x^{3}-3x^{2}-x+1}=\dfrac{(1-x)(3x+2)}{x^{3}-3x^{2}-x+1}.$

However, we desire the generating function for the level sizes of
$\mathcal{O}^{op}_{(BW)^{k}}$ in the limit as $k\rightarrow\infty$. As
constructed, our quasi-infinite forest has an entire copy of itself after
playing $R_{1}$, giving rise to the left branch $[1\ldots]$, which we wish to
disregard. Letting $H_{BW}(x)$ denote the height generating function for the
rest of the quasi-infinite forest, that is, the two roots and the elements in
the branch $[2\ldots]$, one then has

$g(x)=xg(x)+H_{BW}(x)$

and therefore

$H_{BW}(x)=(1-x)g(x)=\dfrac{(1-x)^{2}(3x+2)}{x^{3}-3x^{2}-x+1}.$

Thus to complete the proof of Theorem 1.1, it only remains to show that the
level sizes of $\mathcal{O}^{op}_{(BW)^{k}}$ actually converge to the
coefficients given by $H_{BW}(x)$. This is a consequence of a somewhat more
precise theorem.

######  Theorem 3.1.

The finite reverse Bulgarian solitaire graph $\mathcal{O}^{op}_{(BW)^{k+1}}$
coincides at least up to level $k$ with the BW quasi-infinite forest after
removing its branch $[1\ldots]$.

###### Proof.

For each $k$, to get to level $k$ in the quasi-infinite forest, there are at
most $k$ times that we change the tail
$\small\begin{matrix}\langle{0}\rangle\\\ \langle{1}\rangle\end{matrix}$ to
$\small\begin{matrix}\langle{1}\rangle\\\ \langle{0}\rangle\\\
\langle{1}\rangle\end{matrix}$, that means we add at most $k$ blocks
$\small\begin{matrix}\langle{0}\rangle\\\ \langle{1}\rangle\end{matrix}$. Thus
if we start with the root $\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\ \langle{1}\rangle\\\
{\quad\,\left(\small\begin{matrix}0\\\ 1\end{matrix}\right)^{k-1}}\\\
0\end{matrix}\;$, we don’t need to add new parts until using up those $k$
blocks of $\small\begin{matrix}0\\\ 1\end{matrix}$. Moreover, it is easy to
confirm that the rule of bracketing makes sense if $k$ is large enough. This
implies the coincidence of the quasi-infinite forest with the finite graph. ∎

Next, some kind of similar arguments apply to primitive necklaces of length at
least $3$.

##  4 Explanations for the rules of the general forest for primitive necklaces
$\absolutevalue{P}\geq 3$

We wish to explain why the rules in Section 2 for constructing the (quasi-
infinite) forest $\mathcal{F}_{P}$ from the recurrent set $\mathcal{C}_{P}$
actually produce a forest which is the limiting digraph
$\lim_{k\rightarrow\infty}\mathcal{O}^{\mathrm{op}}_{P^{k}}$ (after pruning
the branches whose playing sequences are $[1\ldots]$ and adding arrows
$\gamma^{(t)}\xrightarrow{1}\gamma^{(t+1)}$ to form the recurrent cycle
$\mathcal{C}_{P}$). To this end, we answer some below questions about the
construction. In this section, if no further information is given, the
statements relates to the forest. Also, the
$\lambda=\small\begin{matrix}\mu\\\ \nu\end{matrix}$ is used to mean the
concatenation of either two partitions or two difference labelings $\mu$ and
$\nu$. For a partition or a difference labeling $\lambda$ and an integer $h$,
we write $\lambda+h=(\lambda_{1}+h,\ldots,\lambda_{m}+h)$. Obviously, if
$\lambda$ is a difference labeling then $(\lambda+h)^{+}=\lambda^{+}+h$.

######  Question 4.1.

How do we bracket the roots $\gamma^{(t)}$ of the tree $G_{t}$, even though
they are infinite vectors?

######  Answer 4.1.

We bracket them as in the recurrent set of the orbit $\mathcal{O}_{P}$. The
following proposition clarifies that bracketing rule:

######  Proposition 4.1.

For any primitive necklace $P$ of length at least $3$ and any $k$, elements in
the recurrent set $\mathcal{C}_{P^{k}}$ restricted to the first $p$ parts are
identical (with brackets). Moreover, only the first $3$ parts can be
bracketed.

###### Proof.

Recall that for a partition $\lambda$ in the reverse BS system, $\lambda_{j}$
is playable if and only if $\lambda_{j}\geq l(\lambda)-1$. If
$\lambda\in\mathcal{C}_{P^{k}}^{+}$, it must have the form
$\lambda=\Delta_{kp-1}+(\gamma^{(t)})^{k}$ for some $t$. Then $l(\lambda)\geq
kp-1$, and thus $\lambda_{j}$ is playable if and only if
$\lambda_{j}=kp-j+(\gamma^{(t)})^{k}_{j}\geq kp-2$, or
$1\geq(\gamma^{(t)})^{k}_{j}\geq j-2$. Hence $j\leq 3$. Therefore, the
bracketed parts in elements of the recurrent set $\mathcal{C}_{P^{k}}$ are all
among the first $3\leq p$ parts, and our proposition is verified. ∎

######  Example 5.

The recurrent sets in the finite reverse BS graphs
$\mathcal{O}^{\mathrm{op}}_{BWW}$ and $\mathcal{O}^{\mathrm{op}}_{(BWW)^{2}}$
are

$\displaystyle\mathcal{C}_{BWW}^{+}$
$\displaystyle=\Bigg{\\{}\small\begin{matrix}\langle{3}\rangle\\\
\langle{1}\rangle\end{matrix},\small\begin{matrix}\langle{2}\rangle\\\ 1\\\
1\end{matrix},\small\begin{matrix}\langle{2}\rangle\\\
\langle{2}\rangle\end{matrix}\Bigg{\\}}\text{ and
}\mathcal{C}_{BWW}=\Bigg{\\{}\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\ 0\end{matrix},\small\begin{matrix}\langle{0}\rangle\\\
0\\\ 1\end{matrix},\small\begin{matrix}\langle{0}\rangle\\\
\langle{1}\rangle\\\ 0\end{matrix}\Bigg{\\}}$
$\displaystyle\mathcal{C}_{(BWW)^{2}}^{+}$
$\displaystyle=\left\\{\small\begin{matrix}\langle{6}\rangle\\\
\langle{4}\rangle\\\ 3\\\ 3\\\
1\end{matrix},\small\begin{matrix}\langle{5}\rangle\\\ 4\\\ 4\\\ 2\\\ 1\\\
1\end{matrix},\small\begin{matrix}\langle{5}\rangle\\\ \langle{5}\rangle\\\
3\\\ 2\\\ 2\end{matrix}\right\\}\text{ and
}\mathcal{C}_{(BWW)^{2}}=\left\\{\small\begin{matrix}\langle{1}\rangle\\\
\langle{0}\rangle\\\ 0\\\ 1\\\ 0\\\
0\end{matrix},\small\begin{matrix}\langle{0}\rangle\\\ 0\\\ 1\\\ 0\\\ 0\\\
1\end{matrix},\small\begin{matrix}\langle{0}\rangle\\\ \langle{1}\rangle\\\
0\\\ 0\\\ 1\\\ 0\end{matrix}\right\\}.$

Their difference labellings, including their brackets, are identical if we
restrict them to the first $3$ parts.

######  Remark 4.1.

Moreover, as we restrict the roots to their first $p$ parts, we only need to
know how to bracket the recurrent cycle $\mathcal{C}_{P}$. For a partition
$\lambda\in\mathcal{C}_{P}$, that is, $\lambda^{-}$ is one of the roots, we
have:

  * •

$\lambda_{1}$ is always bracketed, because $\lambda_{1}\geq p-1\geq
l(\lambda)-1$.

  * •

$\lambda_{2}$:

    * –

If $\lambda^{-}_{2}=1$ then it is bracketed, because then
$\lambda_{2}=(p-2)+1=p-1\geq l(\lambda)-1$.

    * –

If $\lambda^{-}_{2}=0$ then it is bracketed only if $\lambda^{-}_{p}=0$, since
then $\lambda_{2}=p-2=l(\lambda)-1$.

  * •

$\lambda_{3}$ can only be bracketed if $\lambda^{-}_{3}=1$ and
$\lambda^{-}_{p}=0$, since then $\lambda_{3}=(p-3)+1=p-2=l(\lambda)-1$.

######  Question 4.2.

In the forest, how do we decide which parts should be bracketed after playing
a part?

######  Answer 4.2.

Recall that due to the rules of the forest, each element has its length $p$
tail matching $\gamma^{(t)}$ for some $t$. There are two cases for what we
play:

  * (1)

Play a part in the tail $\gamma^{(t)}$

  * (2)

Play a part above the tail $\gamma^{(t)}$.

Before discussing the bracketings, we prove a general property:

######  Claim 4.1.

In a difference labelling $\lambda$, there are no triples $j_{1}<j_{2}<j_{3}$
such that $\lambda_{j_{1}}<\lambda_{j_{2}}<\lambda_{j_{3}}$. This assertion is
still true for any finite $\mathcal{O}^{op}_{P^{k}}$ where $k\geq j_{3}$.

###### Proof.

Suppose there is such triple, then $\lambda_{j_{3}}\geq 2$, which means some
part lower than $\lambda_{j_{3}}$ has already been played. But during any
play, the amounts added to $\lambda_{j_{1}}$ and $\lambda_{j_{2}}$ are at
least the amount added to $\lambda_{j_{3}}$. Since $\lambda_{j_{3}}$ was
either $0$ or $1$ in the root of the tree containing $\lambda$,
$\lambda_{j_{1}}$ was negative at the start. We obtain a contradiction. ∎

######  Corollary 4.1.1.

A similar argument to the proof above shows that if
$\lambda_{j}<\lambda_{j+1}$ then $\lambda_{j+1}-\lambda_{j}=1$.

Now we explain how to change the bracketing in $\lambda$ in the forest in
situation (2), that is, after we play a part above the tail $\gamma^{(t)}$.

######  Proposition 4.2.

Let $\lambda$ be a difference labelling in $\mathcal{O}^{op}_{N}$. If a part
$\lambda_{j}$ is playable, let $\psi=R_{j}(\lambda)$. Then $\psi_{j}$ is
playable if and only if $\absolutevalue{\lambda_{j}-\lambda_{j+1}}\leq 1$.
Moreover, if $\lambda_{j}\geq\lambda_{j+1}$, any parts $\psi_{s}$ where $s\geq
j+3$ are not playable. Otherwise $\lambda_{j}+1=\lambda_{j+1}$ and any parts
$\psi_{s}$ where $s\geq j+4$ are not playable.

###### Proof.

For the first statement, we consider $\Lambda=\lambda^{+}$. Since playing
parts other than $\Lambda_{j}$ and $\Lambda_{j+1}$ does not affect the gap
between them, we only consider the moment when performing $R_{j}$. The result
is a partition $\overline{\Lambda}$ with $\Lambda_{j}$ parts. Thus, a part is
playable in the state $R_{j}(\lambda)$ if and only if its size is at least
$\Lambda_{j}-1$. Because $R_{j}$ adds one to every other part, and the
difference labeling is obtained by subtracting a staircase, which yields
$\lambda_{j}-\lambda_{j+1}=(\Lambda_{j}-\Lambda_{j+1})-1$, we obtain the first
statement.

Now if $\lambda_{j}\geq\lambda_{j+1}$, let $\absolutevalue{N}=m$ where we
subtract $\Delta_{m-1}$ to get the difference labellings. Then
$\psi=R_{j}(\lambda)$ has $m-j+\lambda_{j}$ parts. Note that
$\psi_{j+3}=\lambda_{j+4}$. By Claim 4.1, we see that
$\lambda_{j+4}\leq\max\\{\lambda_{s}:j\leq s\leq j+3\\}$. By Corollary 4.1.1,
that maximum is at most $\lambda_{j}+1$. Thus

$\psi^{+}_{j+3}=m-j-3+\lambda_{j+4}\leq m-2-j+\lambda_{j}=l(\psi)-2.$

Thus $\psi_{j+3}$ is not playable and neither are the later parts. Moreover,
$\psi^{+}_{j+1}=m-j-1+\lambda_{j+2}\geq m-j+\lambda_{j}-1$ if and only if
$\lambda_{j+2}\geq\lambda_{j}$. Similarly, $\psi_{j+2}$ is playable if and
only if $\lambda_{j+3}\geq\lambda_{j}+1$. Hence,
$\lambda_{j+3}=\lambda_{j}+1$.

Otherwise $\lambda_{j+1}-\lambda_{j}=1$, adding a staircase we get
$\lambda^{+}_{j}=\lambda^{+}_{j+1}$ and thus we can play $R_{j+1}$ instead of
$R_{j}$. ∎

Proposition 4.2 explains the rule $2$ of the forest. Moving on, we explain how
a part in the “tail” $\gamma^{t}$ is played, provided that the multiple $k$
(in the necklace $N=P^{k}$) is large enough.

######  Proposition 4.3.

Assume that $\lambda=\small\begin{matrix}\alpha\\\ \gamma^{(t)}\\\
\gamma^{(t)}\\\ \beta\end{matrix}$ is a difference labelling in
$\mathcal{O}^{op}_{P^{k}}$, where $\alpha,\beta$ are some difference
labellings, that $l(\alpha)=a$ and that $\lambda_{a+1}$ is playable. Then

$R_{a+1}(\lambda)=\small\begin{matrix}\alpha+1\\\ \gamma^{(t+1)}\\\
\gamma^{(t)}[2:]\\\ \beta^{\prime}\end{matrix}$ (5)

and the $\gamma^{(t+1)}$ segment is bracketed similarly to the root.

###### Proof.

We have $l(\gamma^{(t)})=p$ and note that $\beta$ is not necessarily non-
negative. Let $n=pk-1$. The partition corresponding to $\lambda$ is

$\Lambda=\lambda^{+}=\lambda+\Delta_{n}$

of length $l\geq a+2p$. So $\lambda_{a+1}$ is playable if and only
if$\Lambda_{a+1}=\gamma^{(t)}_{1}+n-a\geq l-1$, then
$1\geq\gamma^{(t)}_{1}\geq l-n+a-1$. Playing $\lambda_{a+1}$ adds $1$ to each
of the entries of both $\alpha^{+}$ and $\alpha$, erases $\lambda_{a+1}$ and
keeps the rest of $\lambda$, thus we obtain (5). Let $\Psi=R_{a+1}(\Lambda)$
and $\psi=R_{a+1}(\lambda)$, so $l(\Psi)=\gamma^{(t)}_{1}+n-a$. Now in the
root $\gamma^{(t+1)}$, the part $\gamma^{(t+1)}_{j}$ is bracketed if and only
if

$\gamma^{(t+1)}_{j}+(p-j)\geq\begin{cases}p-1\qquad\text{ if
}\gamma^{(t)}_{1}=1\\\ p-2\qquad\text{ if }\gamma^{(t)}_{1}=0\end{cases},$

thus $\gamma^{(t+1)}_{j}\geq j-2+\gamma^{(t)}_{1}$. We show the same $j^{th}$
part of the $\gamma^{(t+1)}$ segment is bracketed in $\psi$. Actually, that
part is $\psi_{a+j}$, and

$\Psi_{a+j}=\gamma^{(t+1)}_{j}+n-a-j+1\geq\gamma^{(t)}_{1}+n-a-1=l(\Psi)-1.$

This concludes the proof. ∎

######  Proposition 4.4.

Let $\lambda=R_{\sigma}((\gamma^{(t)})^{k})$, for some $(\gamma^{(t)})^{k}$ in
$\mathcal{C}_{P^{k}}$ and some arbitrary playing sequence $\sigma$ of length
$l$. If $k$ is large enough, then $\lambda$ is of the form
$\lambda=\small\begin{matrix}\alpha\\\ \gamma^{(s)}\\\ \gamma^{(s)}\\\
\beta\end{matrix}$ for some $1\leq s\leq p$ and $l(\alpha)+1\geq\sigma_{l}$.
Moreover, $\alpha$ is determined uniquely for all large $k$ including the
brackets, and if rule $1$ applies to $R_{\sigma_{l}}$ then the first
$\gamma^{(s)}$ is bracketed similarly to the root $\gamma^{(s)}$ as in Remark
4.1.

###### Proof.

Take $k\geq l+2$, and we start with
$(\gamma^{(t)})^{k}=\small\begin{matrix}\gamma^{(t)}\\\ \gamma^{(t)}\\\
\beta\end{matrix}=\small\begin{matrix}\gamma^{(t)}_{1}\\\ \gamma^{(t+1)}\\\
\gamma^{(t+1)}\\\
\beta^{\prime}\end{matrix}=\small\begin{matrix}\gamma^{(t)}_{1}\\\
\gamma^{(t)}_{2}\\\ \gamma^{(t+2)}\\\ \gamma^{(t+2)}\\\
\beta^{\prime\prime}\end{matrix}$, in which at most $3$ first parts are
playable by Proposition 4.1. In each play, if rule $1$ applies, then
Proposition 4.3 guarantees the next state has the same form as in the
proposition because in each play we only lose at most $1$ block of
$\gamma^{(s)}$ for some $s$. Otherwise, rule $2$ applies which does not change
the tail (consisting of blocks of $\gamma^{(s)}$). Proposition 4.2 shows that
rule $2$ also determines the playable parts in the next state. The conclusion
follows for all trees rooted at $(\gamma^{(t)})^{h}$ for $h\geq k$, since
$\sigma$ only takes place in the first $k$ blocks. ∎

######  Question 4.3.

Why can we restrict the infinite vector to some finite prefix without losing
any playable parts?

######  Answer 4.3.

We defined earlier that $\mathcal{O}^{op}_{P^{\infty}}$ $=\lim_{k\to\infty}$
$\mathcal{O}^{op}_{P^{k}}$. Because of Proposition 4.4, we see that for a
playing sequence $\sigma$ and $k$ large enough, the elements
$\lambda_{h}=R_{\sigma}((\gamma^{(t)})^{h})$ for $h\geq k$ share the same
prefix $\lambda=\small\begin{matrix}\alpha\\\ \gamma^{(s)}\end{matrix}$ as in
the statement of the proposition. Thus we can represent all those
$\lambda_{h}$’s by that prefix $\lambda$ in $\mathcal{O}^{op}_{P^{\infty}}$.
Actually, $\lambda$ is in the form $\small\begin{matrix}\alpha\\\
\gamma^{(s)}\\\ \gamma^{(s)}\\\ \vdots\end{matrix}$ so that rule $1$ works for
playing a part in the ”tail” of $\lambda$. Rule $2$ also works since each
element $\lambda$ has a tail of length $p\geq 3$ and by Proposition 4.2, the
number of new bracketed parts is at most $3$, thus the lower parts are not
affected.

The conclusion of this section is that, the finite reverse BS forest
$\mathcal{O}^{op}_{P^{k}}$ coincides with the infinite digraph
$\mathcal{O}^{op}_{P^{\infty}}$ obtained from the forest $\mathcal{F}_{P}$ (by
modifying any branch of $\mathcal{F}_{P}$ as in Section 1) up to at least
level $k$. Therefore, we confirm that $\mathcal{O}^{op}_{P^{\infty}}$
$=\lim_{k\to\infty}$ $\mathcal{O}^{op}_{P^{k}}$.

##  5 The limiting generating function for general $\mathcal{O}^{op}_{P^{k}}$
by level sizes

We recall our second main theorem from the Introduction.

######  Theorem 1.2.

For primitive necklaces $P$ with $\absolutevalue{P}\geq 3$, there is a power
series $H_{P}$ in $\mathbb{Z}[[x]]$ such that the sequence of generating
functions $(\mathcal{D}_{P^{k}})_{k=0}^{\infty}$ converges to $H_{P}$
coefficient-wise. Moreover, $H_{P}$ is a rational function having denominator
polynomial of degree at most $\absolutevalue{P}$ and numerator degree at most
$2\absolutevalue{P}$.

We also recall a property that was mentioned in Section 4:

######  Claim 5.1.

Each $\gamma^{(t)}\in\mathcal{C}_{P}$ has at most $3$ playable parts.
Moreover, if $\gamma^{(t)}_{p}=1$, then $\gamma^{(t)}_{2}$ is playable if and
only if$\gamma^{(t)}_{2}=1$.

The next claim points out a “special” element in the recurrent set.

######  Claim 5.2.

For any primitive necklace $P$ of length at least $3$, there is at least one
$\gamma^{(t)}\in\mathcal{C}_{P}$ (and possibly more than one) of the form
$\small\begin{matrix}\langle{\sigma}\rangle\\\ 0\\\ \vdots\end{matrix},$ where
$\sigma\in\\{0,1\\}$.

###### Proof.

There are two cases:

  1. 1.

$P$ has two consecutive black beads, that means any
$\gamma^{(t)}\in\mathcal{C}_{P}$ has either two consecutive $1^{\prime}s$ or a
$1$ at the top and a $1$ at the bottom. Let $\gamma^{(t)}$ be of the form
$\,\small\begin{matrix}1\\\ 0\\\ \vdots\\\ 1\end{matrix}\,$, exists or else
$P=B^{p}$ not primitive. Thus $\gamma^{(t)}_{1}+p-1=p>p-1=l(\gamma^{(t)})-1$,
so it is playable. Also, Claim 5.1 admits that $\gamma^{(t)}_{2}$ is not
playable.

  2. 2.

$P$ has two consecutive white beads, consider
$\gamma^{(t)}=\small\begin{matrix}0\\\ 0\\\ \vdots\\\ 1\end{matrix}$. Thus
$\gamma^{(t)}_{1}$ is playable and Claim 5.1 admits that $\gamma^{(t)}_{2}$ is
not playable.

∎

The third claim regards a special situation that separates types of playing
sequences:

######  Claim 5.3.

Let $S$ be the subtree $S$ of the forest $\mathcal{F}_{P}$ which is rooted at
the element

$\lambda=\small\begin{matrix}\lambda[:j]\\\ \langle{\lambda_{j+1}}\rangle\\\
0\\\ \vdots\end{matrix}=\small\begin{matrix}\alpha\\\
\gamma^{(t)}\end{matrix}=\small\begin{matrix}\alpha\\\
\langle{\sigma}\rangle\\\ 0\\\ \vdots\\\ 1\end{matrix}$

where $\alpha=\lambda[:j]$ has $\alpha_{j}\geq 1$, with $\sigma\in\\{0,1\\}$
and $\small\begin{matrix}\langle{\sigma}\rangle\\\ 0\\\ \vdots\\\
1\end{matrix}=\gamma^{(t)}$ chosen as in Claim 5.2. Then $S$ has growth
function

$h(x)=A(x)+B(x)g_{t}(x)$

where $A,B\in\mathbb{Z}[x]$ of degree at most $j$.

###### Proof.

If $\langle{\sigma}\rangle$ is bracketed, any parts of $\alpha$ are bracketed,
due to rule $3$. Since $\lambda_{j}=\alpha_{j}\geq 1>=0=\lambda_{j+2}$ and
$\sigma$ is the only playable part in the segment $\gamma^{(t)}$, by the proof
of Proposition 4.2 and rule $1$, the part $\lambda_{j+2}=\gamma^{(t)}_{2}=0$
cannot be playable any time before $\sigma$ is played, and the same for any
entries below it. Let $\delta$ be a playing sequence starting at $\lambda$.
Let $ind_{\sigma}^{\delta}(t)$ be the index of $\sigma$ in
$R_{\delta[:(t-1)]}(\lambda)$. We have two cases:

  * 1.

Play $\lambda\xrightarrow{\delta}R_{\delta}(\lambda)$ where $\delta_{i}\leq
ind_{\sigma}^{\delta}(i)$ for all $i$. Clearly, $l(\delta)\leq j$ because we
delete the played entry in each operation, by rule $2$. Let $A(x)$ be the
growth function for this set of elements obtained from performing such playing
sequences.

  * 2.

Part $\sigma$ is played at some time; assume
$\lambda\xrightarrow{\delta}R_{\delta}(\lambda)$ where
$\delta_{i}=ind_{\sigma}^{\delta}(i)$. Because $\alpha_{j}\geq 1$, the rule
$3$ confirms that in any states before playing $R_{\delta_{i}}$, the immediate
part above the tail segment $\gamma^{(t)}$ is at least $1$. Hence
$R_{\delta[:i]}(\lambda)$ results in $\small\begin{matrix}\beta\\\
\gamma^{(t+1)}\end{matrix}$, in which the lowest part of $\beta$ is at least
$2$ and we claim that $\beta$ has $j-i+1$ parts. The reason for this claim is
because we erase one part of $\alpha$ each time we play $\delta[:(i-1)]$. Thus
playing any parts of $\beta$ cannot make the $0$ at top of $\gamma^{(t+1)}$
playable due to rule $2$. From then, if any $\delta_{i+s}<\delta_{i}$ for some
$s>0$, that is, a part of the segment $\beta$ is played, then any parts below
$\beta$ are not playable, then the rest of $\delta$ only plays parts of
$\beta$ and leads to a leaf.

The playing sequences $\delta$ in this case take $i-1$ levels to reach
$\gamma^{(t)}$. From then, playing $[\geq\delta_{i}]$ forms a copy of
$\gamma^{(t)}$, while playing entries of $\beta$ at any time reaches a leaf in
at most $j-i+1$ plays. Finally, these playing sequences contribute
$B(x)g_{t}(x)$ for $B\in\mathbb{Z}[x]$ of degree $j$.

∎

###### Proof of Theorem 1.2.

We only need to connect the dots by proving that every branch of the tree
$G_{s}$ rooted at $\gamma^{(s)}$ will eventually hit the element of the form
$\lambda$ as in Claim 5.3. In $\mathcal{C}_{P}$, one cycles the positions of
the $1$’s to obtain the successive elements $\gamma^{(s)}$, so in any $G_{s}$
with $s\neq t$, the first part $\gamma^{(t)}_{1}$ is at some position
$\gamma^{(s)}_{j+1}$ ($1\leq j\leq p-1$). We can append some entries at the
end of $\gamma^{(s)}$ so that the tail is $\gamma^{(t)}$. Hence the Claim 5.3
applies, with $j$ at most $p-1$.

Furthermore, $g_{t}(x)=1+xg_{t+1}(x)$ because $\gamma^{(t)}_{1}$ is the only
playable part in $\gamma^{(t)}$. Now there are polynomials $K,L$ of degree at
most $p-1$ satisfying

$g_{t+1}(x)=K(x)+L(x)g_{t}(x)=K(x)+L(x)(1+xg_{t+1}(x))=K(x)+L(x)+xL(x)g_{t+1}$

implying there are polynomials $P,Q$ of degree at most $p$ such that

$g_{t+1}(x)=\dfrac{M(x)}{N(x)}.$

Then $g_{t}(x)$ is rational with denominator of degree at most $p$ and
numerator of degree at most $p+1$. Specifically,

$g_{t}(x)=\dfrac{N(x)+xM(x)}{N(x)}.$

Any other $g_{s}(x)$ where $s\not\in\\{t,t+1\\}$ is of the form

$g_{s}(x)=A(x)+B(x)g_{t}(x)=\dfrac{AN+BN+xBM}{N},$

where $A,B$ are polynomials of integer coefficients of degree at most $p-2$.
Thus any such $g_{s}$ is rational with denominator of degree at most $p$ and
numerator of degree at most $2p-1$. Let $g$ be the growth function of the $P$
quasi-infinite forest, then $g=\sum_{s=1}^{p}g_{s}$ is rational with
denominator $Q(x)$ and numerator of degree at most $2p-1$.

Now we want to discard a copy of the forest coming from the branches
$[1\ldots]$ in each tree $G_{s}$ to get the limit generating function $H_{P}$
of $\mathcal{O}^{op}_{P^{\infty}}$. Thus

$g(x)=H_{P}(x)+xg(x)$

and then

$H_{P}(x)=(1-x)g(x)$

a rational function with denominator of degree at most $p$ and numerator of
degree at most $2p$.

∎

##  6 Further discussion and conjectures on the finite BS systems

The precise limiting generating functions $H_{BWW}$ and $H_{BBW}$ were
computed in detail the author’s bachelor thesis [5, §5]. The limiting
generating functions for primitive necklaces of greater length can be easily
computed in that fashion. Below are some of them that were computed by hand:

$\displaystyle H_{BWW}(x)=H_{BBW}(x)$
$\displaystyle=(1-x)\dfrac{x^{3}-3x^{2}-4x-3}{2x^{3}+x^{2}-1},$ $\displaystyle
H_{BWWW}(x)$
$\displaystyle=(1-x)\dfrac{x^{5}+8x^{4}-3x^{3}-8x^{2}-6x-4}{6x^{4}+4x^{3}+x^{2}-1},$
$\displaystyle H_{BBBW}(x)$
$\displaystyle=(1-x)\dfrac{2x^{5}+8x^{4}-5x^{3}-10x^{2}-7x-4}{6x^{4}+4x^{3}+x^{2}-1},$
$\displaystyle H_{BBWW}(x)$
$\displaystyle=(1-x)\dfrac{x^{3}+x^{2}+x+1}{3x^{4}+2x^{3}+x^{2}-1},$
$\displaystyle H_{BWWWW}(x)$
$\displaystyle=(1-x)\dfrac{2x^{6}+16x^{5}-12x^{4}-23x^{3}-16x^{2}-8x-5}{12x^{5}+8x^{4}+2x^{3}-1}.$

They led us to conjecture in addition to Theorem 1.2 that the denominator
degree of $H_{P}$ is exactly $\absolutevalue{P}$.

Another interesting question about the Bulgarian Solitaire dynamical system is
the sizes of the orbits, which are parametrized by necklaces as discussed in
Section 1. Recall that if $N=P^{k}$ for some primitive necklaces $P$ of length
$p$, an element $\lambda$ in the recurrent set $\bm{C}_{P^{k}}$ is of the form
$\lambda=(\gamma^{(t)})^{k}+\Delta_{pk-1}$ for some
$\gamma^{(t)}\in\mathcal{C}_{P}$. Since the number of $1$’s in $\gamma^{(t)}$
is equal to the number of black beads in $N$, we have that the size of the
partition $n$ that the Bulgarian Solitaire operation acts on is

$n=\binom{pk}{2}+k\cdot\\#\text{black beads of }P$

As we know, when $N=W^{k}$, the orbit $\mathcal{O}_{W^{k}}$ is actually the
whole Bulgarian Solitaire system on the partition set
$\mathcal{P}\left(\binom{k}{2}\right)$. The author’s bachelor thesis [5]
computed the sizes of orbits parametrized by necklaces of the form
$(BW)^{k},(BBW)^{k}$ and $(BWW)^{k}$. One of the results involve the sequence
of _Chebyshev polynomials of the first kind_ $\\{T_{k}(x)\\}_{k=0}^{\infty}$
evaluated at $x=2$, which satisfies the recurrent formula

$\displaystyle T_{0}(2)$ $\displaystyle=1$ $\displaystyle T_{1}(2)$
$\displaystyle=2$ $\displaystyle T_{k}(2)$
$\displaystyle=4T_{k-1}(2)-T_{k-2}(2)\qquad\text{for }k\geq 2.$

The results are the theorem below:

######  Theorem 6.1 (Pham [5]).

For each $k=1,2,\ldots$, one has

$\displaystyle\absolutevalue{\mathcal{O}_{(BW)^{k}}}$ $\displaystyle=T_{k}(2)$
$\displaystyle\absolutevalue{\mathcal{O}_{(BWW)^{k}}}$ $\displaystyle=5^{k}$
$\displaystyle\absolutevalue{\mathcal{O}_{(BBW)^{k}}}$ $\displaystyle=7\cdot
5^{k-1}$

We also conjectured that orbits parametrized by $P^{k}$ for primitive
necklaces $P$ of length greater than $3$ grow geometrically as well. Some data
for primitive necklaces of length $4$ and $5$ are given in [5, Section 3.1].

######  Conjecture 6.2.

For any primitive necklace $P$ with $|P|\geq 3$, there is an integer $c_{P}$
such that for $k\geq 2$,

$\absolutevalue{\mathcal{O}_{P^{k}}}=(c_{P})^{k-1}\absolutevalue{\mathcal{O}_{P}}$

Moreover, when $P$ and $P^{\prime}$ are related by swapping black beads to
white beads, then $c_{P}=c_{P^{\prime}}.$

## References

  * [1] E. Akin and M. Davis.  Bulgarian solitaire.  The American Mathematical Monthly, 92(4):237–250, 1985.
  * [2] J. Brandt.  Cycles of partitions.  Proceedings of the American Mathematical Society, pages 483–486, 1982.
  * [3] H. Eriksson and M. Jonsson.  Level sizes of the Bulgarian solitaire game tree.  The Fibonacci quarterly, 55(3):243–251, 2017.
  * [4] M. Jonsson.  Processes on Integer Partitions and Their Limit Shapes.  PhD thesis, Mälardalen University, 2017.
  * [5] N. Pham.  Combinatorics of Bulgarian Solitaire.  Bachelor thesis, University of Minnesota - Twin Cities, 2022.