centertableaux

# Bulgarian Solitaire: A new representation for depth generating functions

A.J. Harris, Son Nguyen

###### Abstract

Bulgarian Solitaire is an interesting self-map on the set of integer
partitions of a fixed number $n$. As a finite dynamical system, its long-term
behavior is well-understood, having recurrent orbits parametrized by necklaces
of beads with two colors black $B$ and white $W$. However, the behavior of the
transient elements within each orbit is much less understood.

Recent work of Pham considered the orbits corresponding to a family of
necklaces $P^{\ell}$ that are concatenations of $\ell$ copies of a fixed
primitive necklace $P$. She proved striking limiting behavior as $\ell$ goes
to infinity: the level statistic for the orbit, counting how many steps it
takes a partition to reach the recurrent cycle, has a limiting distribution,
whose generating function $H_{p}(x)$ is rational. Pham also conjectured that
$H_{P}(x),H_{P^{*}}(x)$ share the same denominator whenever $P^{*}$ is
obtained from $P$ by reading it backwards and swapping $B$ for $W$.

Here we introduce a new representation of Bulgarian Solitaire that is
convenient for the study of these generating functions. We then use it to
prove two instances of Pham’s conjecture, showing that

$H_{BWBWB\cdots WB}(x)=H_{WBWBW\cdots BW}(x)$

and that $H_{BWWW\cdots W}(x),H_{WBBB\cdots B}(x)$ share the same denominator.

###### Contents

  1. 1 Introduction
  2. 2 Set up
    1. 2.1 Reversed Bulgarian Solitaire
    2. 2.2 New representation
    3. 2.3 The system in the limit
    4. 2.4 Quasi-infinite forests $\mathcal{F}_{P}$
  3. 3 Fuses and pre-fuses
    1. 3.1 $k$-fuses
    2. 3.2 Combinatorial formula for $u_{k}(x)$
    3. 3.3 $k$-pre-fuses
  4. 4 $B(WB)^{k}$ and $W(BW)^{k}$
  5. 5 $BW^{k}$ and $WB^{k}$
    1. 5.1 $BW^{k}$
    2. 5.2 $WB^{k}$
    3. 5.3 Proof of Theorem 1.3
  6. 6 Discussion

##  1 Introduction

The game of Bulgarian Solitaire (BS) was introduced sometime in the late 20th
century, and popularized by Martin Gardner in 1983. The game itself is very
simple. A player starts with $n$ cards divided into a number of piles in
weakly descending order. Now keep repeating the Bulgarian Solitaire move
$\beta$ defined as follows: take one card from each pile, form a new pile and
put the piles in weakly descending order. The game ends when a configuration
of cards is repeated.

The game can naturally be represented by partitions and Young diagrams, where
in each move, we remove the first column and reinsert it as a new row as shown
in Figure 1.

Figure 1: Bulgarian Solitaire move

The BS move $\beta$ forms a dynamical system on the set $X$ of all partitions,
and repeated application of $\beta$ leads to a recurrent cycle $\mathcal{C}$
consisting of partitions $\lambda$ such that $\lambda=\beta^{m}(\lambda)$ for
some $m$. Figure 2 shows an example of the Bulgarian Solitaire moves on
partitions of $8$ in which the directed edges connect $\lambda$ to
$\beta(\lambda)$. As can be seen in the example, we have two recurrent cycles
$\\{(3,2,2,1),(4,2,1,1),(4,3,1),(3,3,2)\\}$ and $\\{(3,3,1,1),(4,2,2)\\}$.

Brandt proved in [Bra82] that there is a bijection between the set of
recurrent cycles $\mathcal{C}$ and the set of objects called (black-white)
necklaces. A necklace $N$ is an equivalence class of sequences of letters
$\\{B,W\\}$ under cyclic rotation. Suppose $\binom{m}{2}\leq
n<\binom{m+1}{2}$, then the bijection from the set of necklaces of length $m$
with $n-\binom{m}{2}$ $B$’s to the set of elements in the recurrent cycles for
the BS system with $n$ cards is defined by

$(b_{1},b_{2},\ldots,b_{m})\rightarrow(m-1,m-2,\ldots,0)+(s_{1},s_{2},\ldots,s_{m})$

where

$\displaystyle s_{i}=\begin{cases}1~{}~{}&\text{if }b_{i}=B\\\
0~{}~{}&\text{if }b_{i}=W\end{cases}.$

Figure 2: Example for $n=8$

Figure 3 gives a visualization of the bijection from necklaces of length $4$
with $2$ $B$’s to the recurrent elements of the system for $n=8$.

Figure 3: Necklaces and recurrent elements

We call $P$ a primitive necklace if it cannot be written as a concatenation
$P=N^{k}=NN\ldots N$ with $k\geq 2$. For example, $BBWW$ is a primitive
necklace while $BWBW=(BW)^{2}$ is not. For each necklace $N$, let
$\mathcal{C}_{N}$ be the recurrent elements corresponding to necklaces in the
equivalence class of $N$, and let the orbit $\mathcal{O}_{N}$ be the set of
elements $\lambda$ such that $\beta^{k}(\lambda)\in\mathcal{C}_{N}$ for some
$k\in\mathbb{Z}_{>0}$. For each element $\lambda$ in $\mathcal{O}_{N}$, let

$\text{level}(\lambda)=\min\\{k:\beta^{k}(\lambda)\in\mathcal{C}_{N}\\}$

and define the level size generating function of $N$ to be

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

Our main results concern the limit of the generating function of $P^{k}$ as
$k\rightarrow\infty$ for primitive necklaces $P$, that is

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

Eriksson and Jonsson proved in [EJ17, Section 4] that such a limit exists when
$P=W$, and

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

Pham then proved in [Pha22, Theorem 1.1, 1.2] that for all primitive necklaces
$P$ with $|P|\geq 2$, such a limit $H_{P}(x)$ exists. Furthermore, for
$|P|\geq 3$, $H_{P}(x)$ is a rational function having denominator polynomial
of degree at most $|P|$ and numerator degree at most $2|P|$. For example, she
showed that

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

and

$H_{BWB}(x)=H_{WBW}(x)=\dfrac{(1-x)(x^{3}-3x^{2}-4x-3)}{2x^{3}+x^{2}-1}.$

Further computations led Pham to an interesting conjecture. For a primitive
necklace $P$, the dual necklace $P^{*}$ is constructed as follows: first
reverse the order of the letters in $P$, then replace all letters $B$ by $W$
and vice versa. She made the following conjecture.

######  Conjecture 1.1.

For all primitive necklaces $P$, the rational functions $H_{P}(x)$ and
$H_{P^{*}}(x)$ can be written with the same denominator of degree
$|P|=|P^{*}|$.

In this paper, we introduce a new representation of Bulgarian Solitaire and
then use it to prove the following special cases of Conjecture 1.1.

######  Theorem 1.2.

For $k\geq 1$, one has $H_{B(WB)^{k}}(x)=H_{W(BW)^{k}}(x)$ .

######  Theorem 1.3.

For $k\geq 1$, the functions $H_{BW^{k}}(x)$ and $H_{WB^{k}}(x)$ can both be
written over the same denominator which is a polynomial of degree $k+1$.

The paper is outlined as follows. In Section 2, we review some basic
definitions and introduce our new representation. In Section 3, we introduce
fuses and pre-fuses, which will be important to our proof. Finally, we prove
Theorem 1.2 in Section 4 and Theorem 1.3 in Section 5.

##  2 Set up

###  2.1 Reversed Bulgarian Solitaire

It is actually more convenient to study the reversed Bulgarian Solitaire move
rather than the (forward) Bulgarian Solitaire move. We give two analogous
definition of the reversed BS move below.

######  Definition 2.1 (Reversed Bulgarian Solitaire move).

For an element $\lambda$, a reversed Bulgarian Solitaire move $R_{j}$ maps
$\lambda$ to $R_{j}(\lambda)$ as follows

  * •

For Young diagrams: take out the $j$th row and insert it as the leftmost
column.

  * •

For a partition: take out the $j$th part and distribute it into the other
parts, one for each.

For our move to make sense, the $j$th part needs to be as least
$\ell(\lambda)-1$. Thus, the reversed BS moves are only defined for such
parts. If $R_{j}$ is defined, we say the $j$th part is playable. Figure 4
shows an example of $\lambda=(5,3,3,2)$, $R_{1}(\lambda)$ and
$R_{3}(\lambda)$. Note that in the example, $R_{2}(\lambda)$ is also defined;
however, since $\lambda_{2}=\lambda_{3}$, $R_{2}(\lambda)$ and
$R_{3}(\lambda)$ are the same. In general, for our convenience in later
sections, if $\lambda_{i}=\lambda_{i+1}=\ldots=\lambda_{j}$, we will only
consider $R_{j}(\lambda)$. Finally, in the example, $R_{4}(\lambda)$ is not
defined since $\lambda_{4}=2<3=\ell(\lambda)-1$.

Figure 4: Reversed BS moves

###  2.2 New representation

Now we define our new representation of Bulgarian Solitaire.

######  Definition 2.2.

Given a partition
$\lambda=(\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{\ell})$, we will
instead view it as an infinite sequence
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell},0,0,\ldots)$ of
nonnegative integers that is eventually zero. For such a partition $\lambda$,
define $\mu_{\lambda}=(\mu_{1},\mu_{2},\ldots)$ by

$\mu_{i}=\lambda_{i}-\lambda_{i+1}.$

In addition, if the $j$th part is playable and $\mu_{j}\neq 0$, we put a bar
above $\mu_{j}$. Note that $\mu$ is also an infinite sequence of nonnegative
integers which is eventually zero. Call this set of sequences
${\mathcal{BS}_{\mathrm{fin}}}$.

For example, for $\lambda=(5,3,3,2,0,0,\ldots)$, we have
$\mu_{\lambda}=(\overline{2},0,\overline{1},2,0,0,\ldots)$. When the context
is clear, we may omit the subscript $\lambda$. Observe that we can easily
recover $\lambda$ from $\mu_{\lambda}$ by the following formula:

$\lambda_{i}=\sum_{k=i}^{\infty}\mu_{i}.$

It is also not difficult to determine which part of $\mu$ is playable.

######  Lemma 2.3.

Consider a sequence $\mu\in{\mathcal{BS}_{\mathrm{fin}}}$, let $\ell$ be the
largest index such that $\mu_{\ell}>0$. There is a bar above $\mu_{i}$ if and
only if $\sum_{k=i}^{\ell}\mu_{i}\geq\ell-1$.

###### Proof.

This follows directly from the fact that the $j$th part of a partition
$\lambda$ is playable if and only if its size is at least $\ell(\lambda)-1$. ∎

From now on, we will refer to the elements in ${\mathcal{BS}_{\mathrm{fin}}}$
by their new representation $\mu:=\mu_{\lambda}$ instead of the standard
partition representation $\lambda$. Furthermore, when we refer to an element
$\mu$ in ${\mathcal{BS}_{\mathrm{fin}}}$, we assume that the bars in $\mu$
satisfy the conditions in Lemma 2.3.

The following lemma shows that this new representation behaves nicely under
the reversed BS moves.

######  Lemma 2.4.

For any $\lambda$ such that the $j$th part is playable, let
$\lambda^{\prime}=R_{j}(\lambda)$, $\mu=\mu_{\lambda}$ and
$\mu^{\prime}=\mu_{\lambda^{\prime}}$. Then the parts $\mu_{i}^{\prime}$ are
determined by the parts of $\mu$ in these three cases:

  * (1)

If $j=1$ then

$\displaystyle\mu^{\prime}_{i}=\begin{cases}\mu_{i+1}~{}~{}&\text{if
}i\neq\lambda_{1}\\\ \mu_{i+1}+1~{}~{}&\text{if }i=\lambda_{1}\end{cases}$

  * (2)

If $j\geq 2$ and $\lambda_{j}\neq j-1$

$\displaystyle\mu^{\prime}_{i}=\begin{cases}\mu_{i}~{}~{}&\text{if }i<j-1\\\
\mu_{i-1}+\mu_{i}~{}~{}&\text{if }i=j-1\\\ \mu_{i+1}~{}~{}&\text{if }i\geq
j~{}\text{and}~{}i\neq\lambda_{j}\\\ \mu_{i+1}+1~{}~{}&\text{if }i\geq
j~{}\text{and}~{}i=\lambda_{j}\end{cases}$

  * (3)

If $j\geq 2$ and $\lambda_{j}=j-1$

$\displaystyle\mu^{\prime}_{i}=\begin{cases}\mu_{i}~{}~{}&\text{if }i<j-1\\\
\mu_{i-1}+\mu_{i}+1~{}~{}&\text{if }i=j-1\\\ \mu_{i+1}~{}~{}&\text{if }i\geq
j\end{cases}$

The bars on the parts of $\mu^{\prime}$ are determined as follows. For $i\leq
j-1$, put a bar above $\mu^{\prime}_{i}$ if $\mu^{\prime}_{i}\neq 0$. For
$i\geq j$, put a bar above $\mu^{\prime}_{i}$ if $\mu^{\prime}_{i}\neq 0$ and
$\sum_{k=j}^{i}\mu_{k}<3$.

When the context is clear, we will denote $\mu^{\prime}=R_{j}(\mu)$.

###### Proof.

The three cases follow the same reasoning: we distribute 1 to each part, so
the difference between 2 consecutive parts stay the same except between
$\lambda^{\prime}_{j-1}$ and $\lambda^{\prime}_{j}$. Since
$\lambda^{\prime}_{j}=\lambda_{j+1}+1$, we have
$\lambda^{\prime}_{j-1}-\lambda^{\prime}_{j}=\lambda_{j-1}-\lambda_{j+1}=\mu_{j-1}+\mu_{j}$.
However, observe that we add $1$ to part $\lambda_{j}$ but none to part
$\lambda_{j}+1$, so the difference is increased by $1$. Finally, to determine
the bars, observe that $\lambda_{j}$ is the length of $\lambda^{\prime}$.
Thus, for the $i$th part of $\lambda^{\prime}$ to be playable,
$\lambda^{\prime}_{i}\geq\lambda_{j}-1$, which means
$\lambda_{i}\geq\lambda_{j}-2$. This is obviously true for $i<j$, and is
equivalent to the condition $\sum_{k=j}^{i}\mu_{i}<3$ for $i\geq j$. ∎

For example, in Figure 4, $\mu=(\overline{2},0,\overline{1},2,0,0,\ldots)$, so
$R_{1}(\mu)=(0,\overline{1},2,0,1,0,0,\ldots)$ and
$R_{3}(\mu)=(\overline{2},\overline{1},\overline{3},0,0,\ldots)$.

###  2.3 The system in the limit

Let us now shift to our main concern of the paper, the limiting version of the
Bulgarian Solitaire system. We will start with an example with the primitive
necklace $P=BWW$ and its powers $P^{1},P^{2},P^{3},\cdots$.

Figure 5: Digraph $\mathcal{O}_{(BWW)^{1}}$

Figure 6: Part of the digraph $\mathcal{O}_{(BWW)^{2}}$

Figure 7: Part of the digraph $\mathcal{O}_{(BWW)^{3}}$

Figures 6, 6, and 7 show the digraphs for reverse BS orbits
$\mathcal{O}_{(BWW)^{1}},\mathcal{O}_{(BWW)^{2}},\mathcal{O}_{(BWW)^{3}}$.
Observe that their recurrent sets

$\displaystyle\\{C^{(1)}_{1},C^{(1)}_{2},C^{(1)}_{3}\\}$
$\displaystyle\leftrightarrow\\{BWW,\quad WBW,\quad WWB\\},$
$\displaystyle\\{C^{(2)}_{1},C^{(2)}_{2},C^{(2)}_{3}\\}$
$\displaystyle\leftrightarrow\\{BWWBWW,\quad WBWWBW,\quad WWBWWB\\}$
$\displaystyle\\{C^{(3)}_{1},C^{(3)}_{2},C^{(3)}_{3}\\}$
$\displaystyle\leftrightarrow\\{BWWBWWBWW,\quad WBWWBWWBW,\quad WWBWWBWWB\\}$
$\displaystyle\vdots$

are in bijection, corresponding to the words within a cyclic equivalence class
of necklaces of the form $P^{\ell}$ for $\ell=1,2,3$. However, note that these
bijections appear to extend to natural inclusions of digraphs

$\mathcal{O}_{(BWW)^{1}}\hookrightarrow\mathcal{O}_{(BWW)^{2}}\hookrightarrow\mathcal{O}_{(BWW)^{3}}\hookrightarrow\cdots.$

Furthermore, the first three levels of $\mathcal{O}_{(BWW)^{2}}$ and
$\mathcal{O}_{(BWW)^{3}}$ are isomorphic.

Indeed, Pham [Pha22] showed that for any $m$, one can find $L(m)$ large enough
such that the first $m$ levels of $\mathcal{O}_{(BWW)^{\ell}}$ are isomorphic
for all $\ell>L(m)$. In other words, $\mathcal{O}_{(BWW)^{\ell}}$ converges to
a digraph
$\mathcal{O}_{(BWW)^{\infty}}=\lim_{\ell\rightarrow\infty}\mathcal{O}_{(BWW)^{\ell}}$.
The recurrent set $\\{C_{1},C_{2},C_{3}\\}$ of $\mathcal{O}_{(BWW)^{\infty}}$
is $\\{(BWW)^{\infty},(WBW)^{\infty},(WWB)^{\infty}\\}$, which is still in
bijection with $\\{BWW,WBW,BWB\\}$. Observe that $C_{1}$, $C_{2}$, and $C_{3}$
are infinite sequences with period $3$.

Pham generalized this idea to every primitive necklace $P$ of length $|P|=n$.
She showed in [Pha22] that for the game digraphs $\mathcal{O}_{P^{\ell}}$, the
bijections of their recurrent sets
$\\{C^{(\ell)}_{1},C^{(\ell)}_{2},\ldots,C^{(\ell)}_{n}\\}$ extend to digraph
inclusions

$\mathcal{O}_{P}\hookrightarrow\mathcal{O}_{P^{2}}\hookrightarrow\mathcal{O}_{P^{3}}\hookrightarrow\cdots$

which converge to a digraph $\mathcal{O}_{P^{\infty}}$, with recurrent set
$\\{C_{1},C_{2},\ldots,C_{n}\\}$. Each $C_{i}$ in the recurrent set is an
infinite sequence with period $n$.

Furthermore, one can write out the $C_{i}$’s in the recurrent set
$\\{C_{1},C_{2},\ldots,C_{n}\\}$ in terms of the new representation as
follows. Let $(b_{1},b_{2},\ldots,b_{n})$ be a word in the cyclic equivalence
class of the necklace $P$ (where $|P|=n$), then the corresponding $C_{i}$ in
the recurrent set of $\mathcal{O}_{P^{\infty}}$ is $(\mu_{1},\mu_{2},\ldots)$
where

$\displaystyle\mu_{i}=\begin{cases}2~{}~{}&\text{if }b_{i}b_{i+1}=BW\\\
1~{}~{}&\text{if }b_{i}b_{i+1}=BB~{}\text{or}~{}WW\\\ 0~{}~{}&\text{if
}b_{i}b_{i+1}=WB\end{cases}.$ (1)

Here the indices are taken mod $n$. For example, the recurrent set of
$\mathcal{O}_{(BWW)^{\infty}}$ is

$\\{(\overline{2},\overline{1},0,2,1,0,\ldots),\quad(0,\overline{2},1,0,2,1,\ldots),\quad(\overline{1},0,2,1,0,2,\ldots)\\}.$

The following properties are straightforward from (1).

######  Lemma 2.5.

Let $\mu$ be an element in the recurrent set of $\mathcal{O}_{P^{\infty}}$
where $|P|=n$, then we have

  * •

$\mu_{i}\in\\{0,1,2\\}$ for all $i\geq 1$; furthermore, the $0$’s and $2$’s
alternate;

  * •

$\mu_{i}=\mu_{i+n}$ for all $i\geq 1$; and

  * •

$\mu_{i}+\mu_{i+1}+\ldots+\mu_{i+n-1}=n$ for all $i\geq 1$.

We also say that this sequence has period $n$.

###### Proof.

We get $\mu_{i}=\mu_{i+n}$ for all $i\geq 1$ from (1). Now, we prove that the
$0$’s and $2$’s alternate. A $2$ only appears in the sequence if in the
necklace we go from $B$ to $W$. Then the next entries will all be $1$ until in
the necklace we go back from $W$ to $B$. When we go from $W$ to $B$, the
corresponding is $0$, so we cannot have two consecutive $2$’s. The same
argument shows that we cannot have two consecutive $0$’s. This also implies
the third condition. Since $\mu_{i}\in\\{0,1,2\\}$ for all $i\geq 1$, and the
$0$’s and $2$’s alternate, among every $n$ consecutive entries, there are as
many $0$’s as $2$’s, so the sum is $n$. ∎

######  Definition 2.6.

We call a (possibly finite) sequence of integers $(a_{1},a_{2},\ldots)$ a
proper tail of period $n$ if it satisfies the conditions in Lemma 2.5 with
period $n$. If the sequence is finite, we require the $0$’s and $2$’s to
alternate when the sequence is read cyclically.

For example, the sequence $(2,1,0,2,1,0,\ldots)$ is a proper tail of period
$3$. However, the sequence $(2,1,0,2)$ is not a proper tail because if we read
the sequence cyclically, we obtain the sequence $(2,1,0,2,2,1,0,2,\ldots)$ in
which the $0$’s and $2$’s do not alternate. On the other hand, the sequence
$(2,1,0,2,1,0)$ is a proper tail.

######  Lemma 2.7.

The set of necklaces of length $n$ bijects with the set of proper tails of
period $n$ with length $n$.

###### Proof.

The bijection is the map defined by (1). Clearly, the map is injective.
Constructing the inverse is also simple. For a proper tail
$(a_{1},\ldots,a_{n})$, let $i$ be the smallest index such that $a_{i}=2$. We
construct the necklace $(b_{1},\ldots,b_{n})$ by first setting $b_{i}=B$ and
$b_{i+1}=W$. Next, we iterate from $j:=i+1$ to $n$; then, we iterate from
$j:=1$ to $i-1$. In each iteration, if $a_{j}=0$ then set $b_{j}=B$, and if
$a_{j}=2$ then set $b_{j}=W$. If $a_{j}=1$ then set $b_{j}=b_{j-1}$ if $j\neq
1$ and $b_{j}=b_{n}$ is $j=1$. The condition that the $0$’s and $2$’s
alternate when the sequence is read cyclically assures that we get the correct
inverse. ∎

Therefore, from now, we can associate proper tails with necklaces.

######  Definition 2.8.

Let $a=(a_{1},a_{2},\ldots)$ be a proper tail of period $n$. We say $a$ is a
proper tail of $P$, where $P$ is a primitive necklace of length $n$, if the
bijection defined by (1) maps $(a_{1},\ldots,a_{n})$ to a necklace in the
cyclic equivalence class of $P$.

Now, we characterize the sequences of nonnegative integers
$\mu=(\mu_{1},\mu_{2},\ldots)$ that can occur in the limit of the Bulgarian
digraphs $\mathcal{O}_{P^{\infty}}$, along with the possible positions of bars
$\overline{\mu}_{j}$ indicating that a reversed BS move $R_{j}$ in position
$j$ is applicable.

######  Definition 2.9.

For a primitive necklace $P$ with $|P|=n$, we define
$\mathcal{O}^{\prime}_{P}$ to be the set of all $\nu$ that can be constructed
as follows.

  1. 1.

Pick $\mu\in\mathcal{O}_{P^{\ell}}$ for some $\ell$ such that there is an
index $i$ satisfying

     * •

$(\mu_{i},\mu_{i+1},\ldots,\mu_{i+n-1})$ is a proper tail of $P$, and

     * •

none of the entries $\mu_{i},\mu_{i+1},\ldots,\mu_{i+n-1}$ are barred, i.e.
none of the positions $i,i+1,\ldots,i+n-1$ are playable.

  2. 2.

Replace $(\mu_{i+n},\mu_{i+n+1},\ldots)$ with infinitely many copies of
$(\mu_{i},\mu_{i+1},\ldots,\mu_{i+n-1})$.

######  Proposition 2.10.

For any primitive necklace $P$, the elements $\nu\in\mathcal{O}^{\prime}_{P}$
are exactly the limits $\nu=\lim_{j\rightarrow\infty}\mu^{(\ell+j)}$ of
convergent sequences $(\mu^{(\ell+1)},\mu^{(\ell+2)},\ldots)$ with
$\mu^{(\ell+j)}\in\mathcal{O}_{P^{\ell+j}}$ for all $j$. In other words,
$\mathcal{O}^{\prime}_{P}=\mathcal{O}_{P^{\infty}}$.

###### Proof.

Let $\mu^{(\ell)}\in\mathcal{O}_{P^{\ell}}$ for some $\ell$, and $i$ is an
index such that $(\mu_{i},\mu_{i+1},\ldots,\mu_{i+n-1})$ is a proper tail of
$P$. Moreover, none of the entries $\mu_{i},\mu_{i+1},\ldots,\mu_{i+n-1}$ are
barred. Then $\mu^{(\ell+j)}$ can be obtained from $\mu^{(\ell)}$ by adding
$j$ copies of $(\mu_{i},\mu_{i+1},\ldots,\mu_{i+n-1})$ between $\mu_{i+n-1}$
and $\mu_{i+n}$. Furthermore, we claim that the bars of $\mu^{(\ell+j)}$ are
in the exact same places as the bars in $\mu^{(\ell)}$. This is because the
bars in $\mu^{(\ell)}$ can only possibly be on the first $i-1$ entries
$\mu_{1},\ldots,\mu_{i-1}$. By adding $j$ copies of
$(\mu_{i},\mu_{i+1},\ldots,\mu_{i+n-1})$ between $\mu_{i+n-1}$ and
$\mu_{i+n}$, in $\mu^{(\ell+j)}$, there are $nj$ more parts than in
$\mu^{(\ell)}$. In addition, since $\mu_{i}+\ldots+\mu_{i+n-1}=n$, for any
$1\leq k\leq i-1$,
$\sum_{r=k}^{\infty}\mu_{r}^{(\ell+j)}=\sum_{r=k}^{\infty}\mu_{r}^{(\ell)}+nj$.
That is, for any $1\leq k\leq i-1$, the sum
$\sum_{r=k}^{\infty}\mu_{r}^{(\ell+j)}$ is also exactly $nj$ more than
$\sum_{r=k}^{\infty}\mu_{r}^{(\ell)}$. Thus, the $k$th part ($1\leq k\leq
i-1$) is playable in $\mu^{(\ell+j)}$ if and only if it is playable in
$\mu^{(\ell)}$.

From this, $\lim_{j\rightarrow\infty}\mu^{(\ell+j)}$ can be obtained from
$\mu^{(\ell)}$ by replace $(\mu_{i+n},\mu_{i+n+1},\ldots)$ with infinitely
many copies of $(\mu_{i},\mu_{i+1},\ldots,\mu_{i+n-1})$. This gives the
corresponding element in $\mathcal{O}^{\prime}_{P}$. ∎

This allows us to define the limit version of the Bulgarian Solitaire system.

######  Definition 2.11.

We define ${\mathcal{BS}_{\mathrm{\infty}}}$ to be the set of all elements
obtained by the construction in Definition 2.9 for all primitive necklaces
$P$.

We can define the reversed BS moves on ${\mathcal{BS}_{\mathrm{\infty}}}$
similar to Lemma 2.4.

######  Lemma 2.12.

If the $j$th part of $\mu$ is playable, i.e. there is a bar above $\mu_{j}$,
we define $\mu^{\prime}:=R_{j}(\mu)$ as follows.

  * (1)

If $j=1$ then

$\displaystyle\mu^{\prime}_{i}=\mu_{i+1}$

  * (2)

If $j\geq 2$ then

$\displaystyle\mu^{\prime}_{i}=\begin{cases}\mu_{i}~{}~{}&\text{if }i<j-1\\\
\mu_{i-1}+\mu_{i}~{}~{}&\text{if }i=j-1\\\ \mu_{i+1}~{}~{}&\text{if }i\geq
j\end{cases}$

The bars on the parts of $\mu^{\prime}$ are determined as follows. For $i\leq
j-1$, put a bar above $\mu^{\prime}_{i}$ if $\mu^{\prime}_{i}\neq 0$. For
$i\geq j$, put a bar above $\mu^{\prime}_{i}$ if $\mu^{\prime}_{i}\neq 0$ and
$\sum_{k=j}^{i}\mu_{k}<3$.

###### Proof.

This construction is consistent with the one in Lemma 2.4. The only difference
is that we exclude any case that includes $\lambda_{j}$. Recall that in Lemma
2.4, we need these cases because when playing $R_{j}$, we add $1$ to
$\lambda_{j}$ but none to $\lambda_{j+1}$. In
${\mathcal{BS}_{\mathrm{\infty}}}$, $\lambda_{j}$ is $\infty$, so this
situation does not arise, and we can exclude these cases. ∎

From now on, unless stated otherwise, when we refer to “an element $\mu$”, we
mean that $\mu$ is in ${\mathcal{BS}_{\mathrm{\infty}}}$. Finally, recall that
we can write out the recurrent cycle elements in $\mathcal{O}_{P^{\infty}}$
(in ${\mathcal{BS}_{\mathrm{\infty}}}$). It is a bit trickier to decide which
part is playable, i.e. where to put the bars. One strategy is to play the
first nonzero part of one element to see which part of the next element is
playable. For example, the recurrent set of $\mathcal{O}_{(BWW)^{\infty}}$ is

$\\{(\overline{2},\overline{1},0,2,1,0,\ldots),\quad(0,\overline{2},1,0,2,1,\ldots),\quad(\overline{1},0,2,1,0,2,\ldots)\\}.$

To see where to put the bars, playing $R_{1}(2,1,0,2,1,0,\ldots)$, we have the
next element is $(\overline{1},0,2,1,0,2,\ldots)$. Playing
$R_{1}(\overline{1},0,2,1,0,2,\ldots)$, we get
$(0,\overline{2},1,0,2,1,\ldots)$. Finally, playing
$R_{2}(0,\overline{2},1,0,2,1,\ldots)$, which is the first playable part of
$(0,\overline{2},1,0,2,1,\ldots)$, gives
$(\overline{2},\overline{1},0,2,1,0,\ldots)$. Thus, the recurrent set of
$\mathcal{O}_{(BWW)^{\infty}}$, with the bars, is

$\\{(\overline{2},\overline{1},0,2,1,0,\ldots),\quad(0,\overline{2},1,0,2,1,\ldots),\quad(\overline{1},0,2,1,0,2,\ldots)\\}.$

One can check that these bars are consistent with the bars in the finite
version in Figures 6, 6, and 7.

###  2.4 Quasi-infinite forests $\mathcal{F}_{P}$

Now we introduce the quasi-infinite forest for certain directed graphs
(digraphs), such as the opposites of the functional digraphs for Bulgarian
solitaire orbits. Recall that a functional digraph for a function
$f:V\rightarrow V$ on a set $V$ has arcs $v\rightarrow f(v)$ for each $v$ in
$V$. Functional digraphs are the same as digraphs in which every vertex $v$
has outdegree one; this allows self-loops and directed $2$-cycles, but
parallel arcs would violate the outdegree one condition.

######  Definition 2.13.

Let $D=(V,A)$ be the opposite digraph of a functional digraph, that is a
digraph in which every vertex has in-degree one. Let $C$ be the largest subset
of $V$ such that the induced digraph $D|_{C}$ is a permutation. Let us call
$C$ the recurrent set of $D$.

Define the quasi-infinite forest $\mathcal{F}_{D}$ to be the digraph in which
the vertices are directed paths $p=(v_{0}\rightarrow
v_{1}\rightarrow\ldots\rightarrow v_{i})$ in $D$ such that $v_{0}\in C$, and
there is an arc $p\rightarrow p^{\prime}$ in $\mathcal{F}_{D}$ whenever
$p,p^{\prime}$ are related as follows:

$\displaystyle p$ $\displaystyle=(v_{0}\rightarrow
v_{1}\rightarrow\ldots\rightarrow v_{i}),$ (2) $\displaystyle p^{\prime}$
$\displaystyle=(v_{0}\rightarrow v_{1}\rightarrow\ldots\rightarrow
v_{i}\rightarrow v_{i+1}).$

Figure 8 shows an example of a digraph $D$ and the corresponding forest
$\mathcal{F}_{D}$. It is easy to see that $\mathcal{F}_{D}$ consists of $|C|$
trees rooted at the vertices in $C$.

Figure 8: Digraph $D$ (left) and the corresponding quasi-infinite forest
$\mathcal{F}_{D}$ (right)

We wish to relate two generating functions, one for the digraph $D$ and one
for its quasi-infinite forest $\mathcal{F}_{D}$. The level generating function
for $D$ is defined by

$h(x):=\sum_{v\in V}x^{\text{level}(v)}$

where $\text{level}(v)=\min\\{k:f^{k}(v)\in C\\}$ for the function
$f:V\rightarrow V$ whose functional digraph is opposite to $D$. Letting
$\ell(p):=i$ for $p=(v_{0}\rightarrow v_{1}\rightarrow\cdots\rightarrow
v_{i})$ The path-length generating function for $\mathcal{F}_{D}$ is defined
by

$g(x):=\sum_{p}x^{\ell(p)}.$

######  Lemma 2.14.

For any digraph $D$ opposite to a functional digraph, one has

$h(x)=(1-x)g(x).$

###### Proof.

It is equivalent to show that

$\displaystyle g(x)$ $\displaystyle=(1+x+x^{2}+x^{3}+\cdots)h(x)$
$\displaystyle=h(x)+xh(x)+x^{2}h(x)+x^{3}h(x)\cdots$

One can interpret each term $x^{k}h(x)$ on the last line as follows. Call an
arc $v\rightarrow v^{\prime}$ in $D$ permutational if both $v,v^{\prime}$ lie
in $C$ and $f(v^{\prime})=v$, and non-permutational otherwise. It is not hard
see that every path $p=(v_{0}\rightarrow v_{1}\rightarrow\cdots\rightarrow
v_{i})$ indexing a vertex in $\mathcal{F}_{D}$ starts with a (possibly empty)
sequence of all permutational steps $v_{0}\rightarrow
v_{1}\rightarrow\cdots\rightarrow v_{k}$, followed by a (possibly empty)
sequence of steps $v_{k}\rightarrow v_{k+1}\rightarrow\cdots\rightarrow v_{i}$
which are all non-permutational; the index $k$ is therefore uniquely
determined. This lets one decompose $\mathcal{F}_{D}$ into vertex subsets

$\mathcal{F}_{D}=\mathcal{F}_{0}\sqcup\mathcal{F}_{1}\sqcup\mathcal{F}_{2}\sqcup\mathcal{F}_{3}\sqcup\cdots$

where $\mathcal{F}_{k}$ are the vertices whose corresponding path starts with
$k$ permutational steps. In Figure 8, the sets $\mathcal{F}_{k}$ for
$k=0,1,2,3$ are colored black, red, blue, green, respectively. One then checks
that, for each $k=0,1,2,\ldots$, the map sending $p=(v_{0}\rightarrow
v_{1}\rightarrow\cdots\rightarrow v_{i})$ to $v_{i}$ restricts to a bijection
$\phi_{k}:\mathcal{F}_{k}\longrightarrow V$ satisfying
$\ell(p)=k+\text{level}(v_{i})$. Consequently,

$\sum_{p\in\mathcal{F}_{k}}x^{\ell(p)}=x^{k}h(x).\qed$

Let us recall the example at the beginning of Section 2.3 with the primitive
necklace $P=BWW$ and its powers $P^{1},P^{2},P^{3},\cdots$. Figures 6, 6, and
7 show the digraphs for
$\mathcal{O}_{(BWW)^{1}},\mathcal{O}_{(BWW)^{2}},\mathcal{O}_{(BWW)^{3}}$.
Recall that each orbit $\mathcal{O}_{(BWW)^{\ell}}$ has a recurrent set
$\\{(BWW)^{\ell},(WBW)^{\ell},(WWB)^{\ell}\\}$. Hence, each orbit
$\mathcal{O}_{(BWW)^{\ell}}$ corresponds to a quasi-infinite forest
$\mathcal{F}_{(BWW)^{\ell}}$, which is a disjoint union of three trees
$\mathcal{T}_{(BWW)^{\ell}}$, $\mathcal{T}_{(WBW)^{\ell}}$,
$\mathcal{T}_{(WWB)^{\ell}}$ rooted at $(BWW)^{\ell}$, $(WBW)^{\ell}$,
$(WWB)^{\ell}$, respectively. Since $\mathcal{O}_{(BWW)^{\ell}}$ converges to
a digraph
$\mathcal{O}_{(BWW)^{\infty}}=\lim_{\ell\rightarrow\infty}\mathcal{O}_{(BWW)^{\ell}}$,
the corresponding quasi-infinite forests $\mathcal{F}_{(BWW)^{\ell}}$ also
converge to a quasi-infinite forest
$\mathcal{F}_{BWW}=\lim_{\ell\rightarrow\infty}\mathcal{F}_{(BWW)^{\ell}}$.
The recurrent set of $\\{C_{1},C_{2},C_{3}\\}$ of
$\mathcal{O}_{(BWW)^{\infty}}$ is still in bijection with $\\{BWW,WBW,BWB\\}$,
and hence $\mathcal{F}_{BWW}$ is a disjoint union of three trees
$\mathcal{T}_{C_{1}},\mathcal{T}_{C_{2}},\mathcal{T}_{C_{3}}$ rooted at
$C_{1},C_{2},C_{3}$ as shown in Figure 9.

Figure 9: Part of the quasi-infinite forest $\mathcal{F}_{BWW}$

Also, recall that Pham generalized this idea to every primitive necklace $P$
of length $|P|=n$. She showed in [Pha22] that for the game digraphs
$\mathcal{O}_{P^{\ell}}$, the bijections of their recurrent sets
$\\{C^{(\ell)}_{1},C^{(\ell)}_{2},\ldots,C^{(\ell)}_{n}\\}$ extend to digraph
inclusions

$\mathcal{O}_{P}\hookrightarrow\mathcal{O}_{P^{2}}\hookrightarrow\mathcal{O}_{P^{3}}\hookrightarrow\cdots$

which converge to a digraph $\mathcal{O}_{P^{\infty}}$ with recurrent set
$\\{C_{1},C_{2},\ldots,C_{n}\\}$. Hence, the corresponding quasi-infinite
forests $\mathcal{F}_{P^{\ell}}$ also converge to a quasi-infinite forest
$\mathcal{F}_{P}$, having $n$ trees
$\mathcal{T}_{C_{1}},\mathcal{T}_{C_{2}},\ldots,\mathcal{T}_{C_{1}}$ rooted at
$C_{1},C_{2},\ldots,C_{n}$. In other words,

$\mathcal{F}_{P}=\bigsqcup_{i=1}^{n}\mathcal{T}_{C_{i}}.$ (3)

We can also generalize the concept of quasi-infinite trees
$\mathcal{T}_{C_{i}}$ to trees $\mathcal{T}_{\mu}$ rooted at any element $\mu$
in ${\mathcal{BS}_{\mathrm{\infty}}}$. Observe that we can pick any element
$\mu$, not necessarily a recurrent cycle element, and start playing reversed
BS from $\mu$. Let $\mathcal{O}_{\mu}$ be the set of elements reachable from
$\mu$ after a sequence of reversed BS moves. When $\mu$ is not a recurrent
cycle element, then for every element $\nu$ in $\mathcal{O}_{\mu}$, there is a
unique sequence of $i$ moves $R_{j_{1}},\ldots,R_{j_{i}}$ such that
$\nu=R_{j_{i}}\circ\ldots\circ R_{j_{1}}(\mu)$. Thus, we can associate each
element $\nu$ in $\mathcal{O}_{\mu}$ with a “level” $i$. Hence, we can define
the tree rooted at $\mu$ and the level generating function of this tree as
follows.

######  Definition 2.15.

For any element $\mu$ in ${\mathcal{BS}_{\mathrm{\infty}}}$, denote by
$\mathcal{T}_{\mu}$ the tree rooted at $\mu$ whose vertices are indexed by
elements in $\mathcal{O}_{\mu}$, and there is a direct edge
$\nu\rightarrow\nu^{\prime}$ if $\nu^{\prime}=R_{j}(\nu)$ for some $j$. In
this case, for each $\nu$ in $\mathcal{O}_{\mu}$, we let $\ell(\mu,\nu)$
denote the number of steps in the path from $\mu$ to $\nu$, and define the
level generating function for $\mathcal{T}_{\mu}$ to be

$g_{\mu}=g_{\mu}(x):=\sum_{\nu}x^{\ell(\mu,\nu)}$

where the sum runs over all such vertices $\nu$ of $\mathcal{T}_{\mu}$.

For example, Figure 10 shows the tree $\mathcal{T}_{\mu}$ rooted at the
element $\mu=(\overline{1},\overline{2},1,1,\ldots)$. The level generating
function of $\mathcal{T}_{\mu}$ is $g_{\mu}(x)=1+2x+3x^{2}+\ldots$.

Figure 10: $\mathcal{T}_{(\overline{1},\overline{2},1,1,\ldots)}$

An important idea is comparing subtrees rooted at different vertices of the
forest $\mathcal{F}_{P}$. In the special case where $\mu=C_{i}$ is one of the
roots of the forest $\mathcal{F}_{P}$, so that
$\mathcal{T}_{\mu}=\mathcal{T}_{C_{i}}$ is one of the trees in the forest,
denote $g_{\mu}(x)$ by $g_{i}=g_{i}(x)=g_{C_{i}}(x)$. Thus, (3) shows that

$g(x)=\sum_{i=1}^{n}g_{i}(x)=g_{1}(x)+\cdots+g_{n}(x)$

and the work of [Pha22] (or Lemma 2.14 above) shows that

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

Thus, the key step in studying $H_{P}(x)$ is to understand the generating
functions $\\{g_{i}(x)\\}_{i=1}^{n}$. Our strategy to prove Theorem 1.3 is to
relate the $\\{g_{i}(x)\\}_{i=1}^{n}$ via a linear system of equations. Our
strategy to prove Theorem 1.2 uses the following notion.

######  Definition 2.16.

Say that two quasi-infinite trees $\mathcal{T}_{\mu}$ and $\mathcal{T}_{\nu}$
are isomorphic if there is a bijection $f$ between their vertices that
respects the reverse BS moves, i.e., one has $\rho^{\prime}=R_{i}(\rho)$ in
$\mathcal{T}_{\mu}$ if and only if $f(\rho^{\prime})=R_{i}(f(\rho))$ in
$\mathcal{T}_{\nu}$.

##  3 Fuses and pre-fuses

###  3.1 $k$-fuses

In this section, we introduce the concept of $k$-fuse that shows up in almost
every quasi-infinite forest. In general, we say an element
$\mu=(\mu_{1},\ldots,\mu_{k},\mu_{k+1},\ldots)$ in
${\mathcal{BS}_{\mathrm{\infty}}}$ contains a $k$-fuse if its first $k$ parts
$\mu_{1},\ldots,\mu_{k}$ satisfy the conditions in Definition 3.1 below. We
then view $\mu$ as $(\mu_{1},\ldots,\mu_{k},\nu)$ where $\nu$ is some other
element of ${\mathcal{BS}_{\mathrm{\infty}}}$, i.e. $\mu$ is $\nu$ following a
prefix $(\mu_{1},\ldots,\mu_{k})$. We will eventually show that regardless of
the exact values of $\mu_{1},\ldots,\mu_{k}$, as long as they satisfy the
conditions in Definition 3.1, we have

$g_{\mu}(x)=u_{k}(x)\cdot g_{\nu}(x),$ (4)

where $u_{k}(x)$ only depends on $k$ and does not depend on $\mu$ or $\nu$ or
the exact values of $\mu_{1},\ldots,\mu_{k}$. Then we will combinatorially
interpret the coefficients of $u_{k}(x)$.

######  Definition 3.1.

We say $(\mu_{1},\ldots,\mu_{k})$ is a $k$-fuse if

  1. 1.

$\mu_{1},\mu_{2},\ldots,\mu_{k-1}$ are either $1$ or $2$, but $\mu_{k}\geq 3$,

  2. 2.

all parts $\mu_{1},\mu_{2},\ldots,\mu_{k}$ are playable, and

  3. 3.

for $1\leq j\leq k-1$, if $\mu_{j}=1$ then $\mu_{j+1}\neq 1$, i.e. there is no
two consecutive ones.

If $\mu=(\mu_{1},\ldots,\mu_{k},\ldots)$, that is, the first $k$ parts of
$\mu$ are $\mu_{1},\ldots,\mu_{k}$, and $(\mu_{1},\ldots,\mu_{k})$ is a
$k$-fuse, we say that $\mu$ contains a $k$-fuse.

######  Example 3.2.

Both $\mu=(\bar{2},\bar{1},\bar{3},\bar{1},\bar{2},\ldots)$ and
$\nu=(\bar{1},\bar{2},\bar{3},\bar{2},\bar{2},\ldots)$ contain $3$-fuses.

######  Remark 3.3.

We explain here why we call $(\mu_{1},\ldots,\mu_{k})$ a “$k$-fuse”. First of
all, once we play any of the first $k$ parts, all parts after $\mu_{k}$, i.e.
$\mu_{k+1},\mu_{k+2},\ldots$, are no longer playable because $\mu_{k}\geq 3$.
This is because Lemma 2.12 says that if we let $\mu^{\prime}=R_{j}(\mu)$, then
for $i\geq j$, $\mu^{\prime}_{i}$ is playable only if
$\sum_{s=j}^{i}\mu_{i}<3$. Having $\mu_{k}\geq 3$ immediately violates this
condition. As a result, once we play any of the first $k$ parts, only the
first $k$ parts are playable. In addition, Proposition 3.7 will show that the
reversed BS game will terminate after at most $k$ moves. For example, figure
11 shows two different elements of ${\mathcal{BS}_{\mathrm{\infty}}}$ that
both contain a $3$-fuse. Although the $3$-fuses are different, the branches
after playing $R_{1}$, $R_{2}$, or $R_{3}$ are isomorphic. Furthermore, for
every element in these branches, the playable parts are only those initially
in the $3$-fuses, and after at most $3$ steps, there is no more playable
parts. We can think of a $k$-fuse as a fuse of a “bomb”. Once we “trigger” the
fuse by playing one of the first $k$ parts, there is nothing we can do except
continue “burning” the fuse. Eventually, after at most $k$ moves, the bomb
“explodes” and there is no more possible move.

Figure 11: 3-fuses

Let us now make some of the earlier comments about (4) more precise. Given a
subset $A\subseteq\\{1,2,3,\ldots\\}$, define

$R_{A}(\mu):=\\{\rho=(R_{j_{1}}\circ R_{j_{2}}\circ\cdots
R_{j_{k}})(\mu)\text{ for some }j_{1},j_{2},\ldots,j_{k}\in A\\}.$

Given $\mu=(\mu_{1},\ldots,\mu_{k},\nu)$ starting with a $k$-fuse, let
$V:=R_{\\{k+1,k+2,\ldots\\}}(\mu)$. Corollary 3.5 below will show that every
element in $V$ also has a $k$-fuse. By Remark 3.3 and Proposition 3.7, the
tree $\mathcal{T}_{\mu}$ has a disjoint decomposition

$\mathcal{T}_{\mu}=\bigsqcup_{\rho\in V}R_{\\{1,2,\ldots,k\\}}(\rho).$

Figure 12(b) shows the disjoint decomposition of the tree rooted at
$\mu=(\overline{1},\overline{3},\overline{1},\overline{2},1,1,\ldots)$ with a
$2$-fuse. Each component $R_{\\{1,2,\ldots,k\\}}(\rho)$ is illustrated via the
color-coding.

(a)

(b)

Figure 12:

Because of the disjoint decomposition, one can write

$g_{\mu}(x)=\sum_{\rho\in V}x^{\ell(\mu,\rho)}u_{\rho}(x)$

where

$u_{\rho}(x)=\sum_{\sigma\in
R_{\\{1,2,\ldots,k\\}(\rho)}}x^{\ell(\rho,\sigma)}.$

Proposition 3.6 below shows that all of the subtrees
$R_{\\{1,2,\ldots,k\\}}(\rho)$ are isomorphic. Hence one can define a single
(polynomial) generating function $u_{k}(x):=u_{\rho}(x)$ for all $\rho\in V$,
to be studied further in Section 3.2 below. Consequently,

$g_{\mu}(x)=u_{k}(x)\cdot\sum_{\rho\in V}x^{\ell(\mu,\rho)}.$

Our next proposition shows $\mathcal{T}_{\mu}|_{V}$ is isomorphic to
$\mathcal{T}_{\nu}$, which will eventually imply (4).

######  Proposition 3.4.

Let $\mu=(\overline{\mu_{1}},\ldots,\overline{\mu_{k}},\nu)$ where
$(\overline{\mu_{1}},\ldots,\overline{\mu_{k}})$ is a $k$-fuse. Then the
vertex set $V:=R_{\\{k+1,k+2,\ldots\\}]}(\mu)$ has $\mathcal{T}_{\mu}|_{V}$
isomorphic to $\mathcal{T}_{\nu}$.

###### Proof.

We will show that a sequence of moves $R_{i_{1}},R_{i_{2}},\ldots,R_{i_{j}}$
is possible from $\nu$ if and only if the sequence of moves
$R_{k+i_{1}},R_{k+i_{2}},\ldots,R_{k+i_{j}}$ is possible from $\mu$. In fact,
we will prove a slightly stronger statement: $\rho:=R_{i_{j}}\circ\ldots\circ
R_{i_{1}}(\nu)$ exists if and only if $R_{k+i_{j}}\circ\ldots\circ
R_{k+i_{1}}(\mu)$ also exists, and $R_{k+i_{j}}\circ\ldots\circ
R_{k+i_{1}}(\mu)=(\overline{\mu_{1}},\ldots,\overline{\mu_{k-1}},\overline{\mu_{k}^{\prime}},\rho)$
where
$(\overline{\mu_{1}},\ldots,\overline{\mu_{k-1}},\overline{\mu_{k}^{\prime}})$
is a $k$-fuse. We will prove this by induction on $j$. The base case where
$j=0$ is obvious.

Suppose $\rho:=R_{i_{j}}\circ\ldots\circ R_{i_{1}}(\nu)$ exists and
$\sigma:=R_{k+i_{j}}\circ\ldots\circ
R_{k+i_{1}}(\mu)=(\overline{\mu_{1}},\ldots,\overline{\mu_{k-1}},\overline{\mu_{k}^{\prime}},\rho)$.
Suppose $\rho^{\prime}=R_{i_{j+1}}(\rho)$ exists for some $i_{j+1}>1$, then
since $i_{j+1}>1$, this move only affects and depends on parts
$i_{j+1}-1,i_{j+1},i_{j+1}+1\ldots$ in $\rho$. These parts are identical to
parts $k+i_{j+1}-1,k+i_{j+1},k+i_{j+1}+1\ldots$ in $\sigma$. Thus,
$\sigma^{\prime}=R_{k+i_{j+1}}(\sigma)$ exists, and
$\sigma^{\prime}=(\overline{\mu_{1}},\ldots,\overline{\mu_{k-1}},\overline{\mu_{k}^{\prime}},\rho^{\prime})$.

Finally, suppose $\rho^{\prime}=R_{1}(\rho)$ exists. By Lemma 2.4,
$\rho^{\prime}$ is obtained by removing the first part of $\rho$ and putting
the bars on the remaining parts following the rules in Lemma 2.4. On the other
hand, $\sigma^{\prime}=R_{k+1}(\sigma)$ is obtained from $\sigma$ by adding
$\rho_{1}$ to $\mu_{k}^{\prime}$ and putting the bars on the remaining parts
also following the rules in Lemma 2.4. Again, parts $1,2,\ldots$ of $\rho$ are
the same as parts $k+1,k+2,\ldots$ of $\sigma$, so the extra bars are put on
respective parts. Thus,
$\sigma^{\prime}=(\overline{\mu_{1}},\ldots,\overline{\mu_{k-1}},\overline{\mu_{k}^{\prime\prime}},\rho^{\prime})$
where $\mu_{k}^{\prime\prime}=\mu_{k}^{\prime}+\rho_{1}$. Note that this does
not violate the conditions of $k$-fuses, i.e.
$(\overline{\mu_{1}},\ldots,\overline{\mu_{k-1}},\overline{\mu_{k}^{\prime\prime}})$
is still a $k$-fuse.

The argument for the converse is exactly the same. ∎

The following corollary is immediate from the proof of Proposition 3.4.

######  Corollary 3.5.

There is an isomorphism from $\mathcal{T}_{\nu}$ to $\mathcal{T}_{\mu}|_{V}$
that maps every element $\rho\in\mathcal{T}_{\nu}$ to an element
$(\overline{\mu_{1}},\ldots,\overline{\mu_{k-1}},\overline{\mu_{k}^{\prime}},\rho)\in\mathcal{T}_{\mu}|_{V}$
where
$(\overline{\mu_{1}},\ldots,\overline{\mu_{k-1}},\overline{\mu_{k}^{\prime}})$
is a $k$-fuse. In particular, every element in $\mathcal{T}_{\mu}|_{V}$ has a
$k$-fuse.

Now we prove that $u_{\rho}(x)$ are the same for all $\rho\in V$.

######  Proposition 3.6.

Let $\rho=(\overline{\rho_{1}},\ldots,\overline{\rho_{k}},\nu)$ where
$(\rho_{1},\ldots,\rho_{k})$ is a $k$-fuse. Then for all values of
$\rho_{1},\ldots,\rho_{k}$ (satisfying the conditions of $k$-fuses) and for
all $\nu$, the subtrees $R_{\\{1,2,\ldots,k\\}}(\rho)$ are isomorphic.

###### Proof.

We will prove this by induction on $k$. The base case where $k=1$ is obvious.
Suppose the statement is true for $k=1,\ldots,j-1$, consider any two elements
$\rho=(\overline{\rho_{1}},\ldots,\overline{\rho_{j}},\nu)$ and
$\rho^{\prime}=(\overline{\rho^{\prime}_{1}},\ldots,\overline{\rho^{\prime}_{j}},\nu^{\prime})$
where $(\overline{\rho_{1}},\ldots,\overline{\rho_{j}})$ and
$(\overline{\rho^{\prime}_{1}},\ldots,\overline{\rho^{\prime}_{j}})$ are
$j$-fuses. Let $\sigma=R_{i}(\rho)$ and $\sigma^{\prime}=R_{i}(\rho^{\prime})$
for some $i\leq j$, we will prove that $\mathcal{T}_{\sigma}$ and
$\mathcal{T}_{\sigma^{\prime}}$ are isomorphic.

First, let $V=R_{\\{i,\ldots\\}}(\sigma)$ and
$V^{\prime}=R_{\\{i,\ldots\\}}(\sigma^{\prime})$, we claim that
$\mathcal{T}_{\sigma}|_{V}$ and $\mathcal{T}_{\sigma}^{\prime}|_{V^{\prime}}$
are isomorphic. In fact, we claim that
$V=\\{\pi~{}|~{}\pi=R_{i}^{m}(\sigma),0\leq m\leq k-i\\}$. This is because in
$\sigma$, $\sigma_{i}$ is playable since $\rho_{i}<3$, but $\sigma_{r}$ is not
playable for all $r>i$ since
$\sum_{s=i}^{r}\rho_{s}\geq\rho_{i}+\rho_{i+1}\geq 3$ by condition 3 in
Definition 3.1. For the same reason, in $R_{i}^{m}(\sigma)$ for $0\leq m<k-i$,
the $i$th part is playable but any part after that is not. However, in
$R_{i}^{k-i-1}(\sigma)$, the $i$th part is $\rho_{j}$, which is at least $3$.
Thus, in the $R_{i}^{k-i}(\sigma$, the $i$th part is also not playable. Thus,
$V=\\{\pi~{}|~{}\pi=R_{i}^{m}(\sigma),0\leq m\leq k-i\\}$. Similarly,
$V^{\prime}=\\{\pi~{}|~{}\pi=R_{i}^{m}(\sigma^{\prime}),0\leq m\leq k-i\\}$.
Hence, $\mathcal{T}_{\sigma}|_{V}$ and
$\mathcal{T}_{\sigma}^{\prime}|_{V^{\prime}}$ are isomorphic.

Finally, every element $\pi$ in $\mathcal{T}_{\sigma}|_{V}$ and
$\mathcal{T}_{\sigma}^{\prime}|_{V^{\prime}}$ contains an $(i-1)$-fuse. Since
$i-1\leq j-1$, by the inductive hypothesis, $R_{\\{1,\ldots,i-1\\}}(\pi)$ are
isomorphic for all $\pi$ in $\mathcal{T}_{\sigma}|_{V}$ and
$\mathcal{T}_{\sigma}^{\prime}|_{V^{\prime}}$. This completes the proof.

∎

The proof of Proposition 3.6 also suggests the following result.

######  Proposition 3.7.

Let $\rho=(\overline{\rho_{1}},\ldots,\overline{\rho_{k}},\nu)$ where
$(\rho_{1},\ldots,\rho_{k})$ is a $k$-fuse. Let $\alpha_{i}$ be $R_{i}(\rho)$
for $1\leq i\leq k$. Let $\mathcal{T}_{[k],\rho}:=\bigcup_{1\leq i\leq
k}\mathcal{T}_{\alpha_{i}}$. Let $V$ be the set of elements in
$\mathcal{T}_{[k],\rho}$, then

$V=\\{\pi~{}|~{}\pi=(R_{i_{j}}\circ\ldots\circ R_{i_{1}})(\rho)\\}$

where $j\leq k$ and $k\geq i_{1}\geq i_{2}\geq\ldots\geq i_{j}$. Specifically,
$V=R_{\\{1,\ldots,k\\}}(\rho)$, and $\mathcal{T}_{\rho}|_{V}$ has depth $k$.

###### Proof.

We will prove this by induction on $k$. If $k=1$, then
$\rho=(\overline{\rho_{1}},\nu)$ where $\rho_{1}\geq 3$. Since $\rho_{1}\geq
3$, in $R_{1}{\rho}$, no part is playable. Thus,
$\mathcal{T}_{[1],\rho}=\mathcal{T}_{\alpha_{1}}$ only contains one element:
$R_{1}(\rho)$, so the statement is true for $k=1$.

If $k>1$, consider any $\mathcal{T}_{\alpha_{i}}$ with $1\leq i\leq k$. The
proof of Proposition 3.6 shows that

$R_{\\{i,\ldots\\}}(\alpha_{i})=\\{\pi~{}|~{}\pi=R_{i}^{m}(\alpha_{i}),0\leq
m\leq k-i\\}=\\{\pi~{}|~{}\pi=R_{i}^{m}(\rho),1\leq m\leq k-i+1\\}.$

Furthermore, every element $\sigma$ in $R_{\\{i,\ldots\\}}(\alpha_{i})$ has an
$(i-1)$-fuse, by induction, the elements in $\mathcal{T}_{[i-1],\sigma}$ have
the form

$(R_{i_{j}}\circ\ldots\circ R_{i_{1}})(\sigma)$

where $j\leq i-1$ and $i-1\geq i_{1}\geq i_{2}\geq\ldots\geq i_{j}$. Hence,
every element in $\mathcal{T}_{\alpha_{i}}$ has the form

$(R_{i_{j}}\circ\ldots\circ R_{i_{1}}\circ R_{i}^{m})$

where $j\leq i-1$, $i-1\geq i_{1}\geq i_{2}\geq\ldots\geq i_{j}$, and $0\leq
m\leq k-i+1$. Thus, the statement is true.

This proves that $V\subseteq R_{\\{1,\ldots,k\\}}(\rho)$. Clearly, we also
have $R_{\\{1,\ldots,k\\}}(\rho)\subseteq V$, so
$V=R_{\\{1,\ldots,k\\}}(\rho)$. Finally, to show that
$\mathcal{T}_{\rho}|_{V}$ has depth $k$, it suffices to check that
$R_{1}^{k}(\rho)$ exists, which is not difficult. ∎

For example, in Figure 11, we have two elements
$\rho=(\overline{2},\overline{1},\overline{3},\overline{1},\overline{2},\ldots)$
and
$\rho^{\prime}=(\overline{1},\overline{2},\overline{3},\overline{2},\overline{2},\ldots)$,
both containing 3-fuses. Even though the exact values of the two 3-fuses are
different, and the remaining parts are also different
($(\overline{1},\overline{2},\ldots)$ and
$(\overline{2},\overline{2},\ldots)$), still $R_{\\{1,2,3\\}}(\rho)$ and
$R_{\\{1,2,3\\}}(\rho^{\prime})$ are isomorphic and both have depth $3$.

Proposition 3.6 means that $R_{\\{1,2,\ldots,k\\}}(\rho)$ only depends on $k$,
and hence the level generating function of this subtree, denote $u_{k}(x)$,
also depends only on $k$. Proposition 3.7 shows that $u_{k}(x)$ has degree
$k$. For instance, Figure 11 shows that $u_{3}(x)=1+3x+5x^{2}+4x^{3}$.
Furthermore, if $\rho$ is an element at level $i$ of some tree
$\mathcal{T}_{\mu}$, then the elements in this subtree contribute exactly
$u_{k}(x)x^{i}$ to the level generating function $g_{\mu}$. Thus, we say that
$\rho$ has a coefficient $u_{k}(x)$. Combining Propositions 3.4 and 3.6 we
achieve the desired equation (4).

######  Corollary 3.8.

If $\mu=(\overline{\mu_{1}},\ldots,\overline{\mu_{k}},\nu)$ where
$(\overline{\mu_{1}},\ldots,\overline{\mu_{k}})$ is a $k$-fuse then the
generating functions $g_{\mu}(x)$ and $g_{\nu}(x)$ of $\mathcal{T}_{\mu}$ and
$\mathcal{T}_{\nu}$ are related by

$g_{\mu}(x)=u_{k}(x)\cdot g_{\nu}(x)$

where $u_{k}(x)$ only depends on $k$.

Figure 12 shows an example of Corollary 3.8. Figure 12(a) shows the tree of an
element $\nu=(\overline{1},\overline{2},1,1,\ldots)$, and figure 12(b) shows
the tree of an element $\mu$ that consists of a $2$-fuse followed by $\nu$. In
$\mathcal{T}_{\mu}$, if $R_{1}$ and $R_{2}$ are not played, the elements are
exactly the elements in $\mathcal{T}_{\nu}$. However, at each element $\rho$,
one can play $R_{1}$ or $R_{2}$ and get to $R_{\\{1,2\\}}(\rho)$. Thus, each
element has a coefficient $u_{2}(x)$.

###  3.2 Combinatorial formula for $u_{k}(x)$

In later sections, we will see that these coefficients $u_{k}(x)$ are very
crucial, especially for computing the generating function $H_{P}(x)$.
Fortunately, these coefficients can be described combinatorially through weak
compositions. Recall that a weak composition
$\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{r})$ of $k$ is a sequence of
nonnegative integers $\alpha_{i}$ with $\alpha_{1}+\cdots+\alpha_{r}=k$.

######  Proposition 3.9.

For all $k$,

$u_{k}(x)=\sum_{i=0}^{k}c_{i,k-i}x^{i}$

where $c_{n,i}$ is the number of weak compositions of $n$ with exactly $i$
zeros.

###### Proof.

Let $\mu=(\overline{\mu_{1}},\ldots,\overline{\mu_{k}})$ be an arbitrary
$k$-fuse, we will construct a bijection between weak compositions of $i$ with
$k-i$ zeros and elements at level $i$ in $\mathcal{T}_{\mu}$ recursively.
Given a weak composition $(\nu_{1},\ldots\nu_{\ell})$ of $i$ with $k-i$ zeros,
we obtain the corresponding element as follows:

  1. 1.

If $\nu_{1}=\ldots=\nu_{\ell}=0$, do nothing and stop. Note that this
corresponds to $\mu$, the only element at level $0$, and also corresponds to
the only composition of $0$ with $k$ zeros.

  2. 2.

Else, there is a largest index $\ell-m$ such that $\nu_{\ell-m}\neq 0$. Then
let $p=k-m-\nu_{\ell-m}+1$, and play $R_{p}$ repeatedly $\nu_{\ell-m}$ times.
Note that after this, we have a $(p-1)$-fuse and the weak composition
$(\nu_{1},\ldots,\nu_{\ell-m-1})$; repeat the process.

First, observe that after step (2), the remaining weak composition
$(\nu_{1},\ldots,\mu_{\ell-m-1})$ is a weak composition of $i-\nu_{\ell-m}$
with $n-i-m$ zeros, and the remaining fuse is a $(k-m-\nu_{\ell-m})$-fuse.
Since $(i-\nu_{\ell-m})+(k-i-m)=k-m-\nu_{\ell-m}$, the recursion is well-
defined.

It is easy to see that two different weak compositions define two different
playing sequences, and injectivity follows since no two playing sequences lead
to the same element by nature of Bulgarian Solitaire.

Finally, in order to prove surjectivity, we define the inverse function. For
each element $\mu$ in the tree, there is a unique sequence of play
$(i_{1},i_{2},\ldots,i_{t})$ that yields $\mu$ from the $k$-fuse. Moreover, by
the argument in the proof of Proposition 3.4, this sequence is weakly
decreasing. Thus, we can rewrite the play sequence as
$(i_{1}^{\alpha_{1}},\ldots.i_{s}^{\alpha_{s}})$ where $(i_{1},\ldots,i_{s})$
is strictly decreasing and $\alpha_{j}\leq i_{j-1}-i_{j}$. Now we fill in the
parts of the weak composition from right to left. For each
$i_{j}^{\alpha_{j}}$, we fill in $(\alpha_{j},0,\ldots,0)$ with
$i_{j-1}-i_{j}+1$ zeros (here we take $i_{0}=k$). Finally, we fill the rest
with zeros, if necessary. It is easy to check that this is the inverse of step
(1) and (2) above. ∎

Figure 13 shows an example of this bijection. Take the composition $(2,1)$ for
instance, the $1$ means that we start by playing $R_{3}$ once. Then we are
left with the $2$-fuse $(\overline{2},\overline{4})$ and the composition $2$.
This tells us that we play $R_{1}$ twice, and hence we obtain the empty
element after the sequence $R_{3},R_{1},R_{1}$.

(a) Tree of a 3-fuse

(b) Corresponding compositions

Figure 13: Tree of a 3-fuse and the corresponding compositions

######  Remark 3.10.

Although there is no simple explicit formula for $c_{k,i}$ that we know of,
there is a nice family of generating functions for these numbers. Fixing $i$,
one has

$\sum_{k=0}^{\infty}c_{k,i}x^{k}=\left(\dfrac{1-x}{1-2x}\right)^{i+1}.$

Observe that when $i=0$,

$\sum_{k=0}^{\infty}c_{k,0}x^{k}=\dfrac{1-x}{1-2x}=1+\sum_{k=1}^{\infty}2^{k-1}x^{k},$

which is indeed the generating function for the number of strong compositions.

###  3.3 $k$-pre-fuses

Now we briefly discuss $k$-pre-fuses, which will be discussed in more detail
in Section 5.

######  Definition 3.11.

We say $(\mu_{1},\ldots,\mu_{k})$ is a $k$-pre-fuse if they satisfy

  1. 1.

$\mu_{1},\mu_{2},\ldots,\mu_{k}$ are either $1$ or $2$,

  2. 2.

all parts $1,2,\ldots,k$ are playable, and

  3. 3.

for all $j\leq k-1$, $\mu_{j}=1$ implies $\mu_{j+1}\neq 1$, i.e. there is no
consecutive ones.

If $\mu=(\mu_{1},\ldots,\mu_{k},\ldots)$, that is, the first $k$ parts of
$\mu$ are $\mu_{1},\ldots,\mu_{k}$, and $(\mu_{1},\ldots,\mu_{k})$ is a
$k$-pre-fuse, we say that $\mu$ contains a $k$-pre-fuse.

The only difference between this definition and Definition 3.1 is that
$\mu_{k}$ is also less than 3, so this is not a $k$-fuse. However, if we play
any $R_{i}$ for $2\leq i\leq k$, we immediately reach an $(i-1)$-fuse.

##  4 $B(WB)^{k}$ and $W(BW)^{k}$

Now, that we have a good understanding of the $k$-fuses, we are set to prove
Theorem 1.2, asserting $H_{B(WB)^{k}}(x)=H_{W(BW)^{k}}(x)$ for $k\geq 1$.

Recall from Section 2.4 that it suffices to study the generating functions
$g_{i}$’s corresponding to the trees $\mathcal{T}_{C_{i}}$ where $C_{i}$’s are
the recurrent cycle elements. Corollary 3.8 tells us that if in
$\mathcal{T}_{C_{i}}$ there is an element $\mu$ with a $k$-fuse followed by
$C_{j}$ for some $j$ (not necessarily different from $i$), then the weight of
the subtree rooted at this element is $u_{k}(x)\cdot g_{j}(x)$. Thus, we can
degenerate the whole subtree to one element representing the subtree with
weight $u_{k}(x)\cdot g_{j}(x)$. We call the tree obtained from
$\mathcal{T}_{C_{i}}$ by degenerating all such subtrees to single elements the
degenerate tree of $\mathcal{T}_{C_{i}}$. For two necklaces $P$ and
$P^{\prime}$, we say two quasi-infinite trees $\mathcal{T}_{C_{i}}$ and
$\mathcal{T}_{C^{\prime}_{i}}$ are almost isomorphic if their degenerate trees
are isomorphic, and if a degenerated element in $\mathcal{T}_{C_{i}}$ has
weight $u_{k}(x)g_{C_{j}}(x)$ then the corresponding element in
$\mathcal{T}_{C^{\prime}_{i}}$ is also degenerated and has weight
$u_{k}(x)g_{C^{\prime}_{j}}(x)$. Note that two trees being almost isomorphic
means that the subtrees that consist of the non-degenerate elements are
isomorphic.

For example, recall from Section 2.4 the quasi-infinite forest
$\mathcal{F}_{WBW}$ with three trees rooted at the recurrent cycle elements

$\\{C_{1},C_{2},C_{3}\\}=\\{(\overline{1},0,2,1,0,2,\ldots),\quad(0,\overline{2},1,0,2,1,\ldots),\quad(\overline{2},\overline{1},0,2,1,0,\ldots)\\}$

as shown in Figure 14(a). Observe that $R_{1}(C_{1})$ is $C_{2}$, so we
degenerate the whole subtree rooted at $R_{1}(C_{1})$ to an element with
weight $g_{C_{2}}(x)$. Similarly, we degenerate the whole subtree rooted at
$R_{1}(C_{2})$ to an element with weight $g_{C_{3}}(x)$, and the whole subtree
rooted at $R_{1}(C_{3})$ to an element with weight $g_{C_{1}}(x)$. Finally,
$R_{2}(C_{3})$ is a $1$-fuse followed by $C_{1}$, so we degenerate the whole
subtree rooted at $R_{2}(C_{3})$ to an element with weight
$u_{1}(x)g_{C_{2}}(x)$. The degenerated forest is shown in Figure 14(b).

(a) $\mathcal{F}_{WBW}$

(b) $\mathcal{F}_{WBW}$ degenerated

Figure 14: $\mathcal{F}_{WBW}$ and its degenerated version

Similarly, the recurrent set for $\mathcal{O}_{BWB}$ is

$\\{C_{1},C_{2},C_{3}\\}=\\{(\overline{2},0,1,2,0,1,\ldots),\quad(0,\overline{1},2,0,1,2,\ldots),\quad(\overline{1},\overline{2},0,1,2,0,\ldots)\\}.$

The quasi-infinite forest $\mathcal{F}_{BWB}$ is shown in Figure 15(a), and
its degenerated forest is shown in Figure 15(b). One can easily check that the
degenerated forests of $\mathcal{F}_{WBW}$ and $\mathcal{F}_{BWB}$ are
isomorphic by comparing Figures 14(b) and 15(b). Thus, $\mathcal{F}_{WBW}$ and
$\mathcal{F}_{BWB}$ are almost isomorphic. Lemma 4.1 will show that this
implies $\mathcal{F}_{WBW}$ and $\mathcal{F}_{BWB}$ are isomorphic, which can
be seen by comparing Figures 14(a) and 15(a). This will be our method for
proving Theorem 1.2.

(a) $\mathcal{F}_{BWB}$

(b) $\mathcal{F}_{BWB}$ degenerated

Figure 15: $\mathcal{F}_{BWB}$ and its degenerated version

######  Lemma 4.1.

If $\mathcal{T}_{C_{i}}$ and $\mathcal{T}_{C^{\prime}_{i}}$ are almost
isomorphic for all $i$, then $\mathcal{T}_{C_{i}}$ and
$\mathcal{T}_{C^{\prime}_{i}}$ are isomorphic for all $i$.

###### Proof.

It suffices to prove that from the roots of $\mathcal{T}_{C_{i}}$ and
$\mathcal{T}_{C^{\prime}_{i}}$, one can play a sequence of moves
$R_{j_{1}},\ldots,R_{j_{m}}$ in $\mathcal{T}_{C_{i}}$ if and only if one can
play the same sequence in $\mathcal{T}_{C^{\prime}_{i}}$. Observe that we
start at the root of both trees. If before $R_{j_{r}}$, we have non-degenerate
elements in both trees, then $R_{j_{r}}$ is playable in one tree if and only
if it is playable in the other. If we have degenerate elements in both trees,
then by definition of almost isomorphic, the degenerate elements both have
$k$-fuses followed by $C_{j}$ and $C_{j}^{\prime}$ respectively. If $1\leq
j_{r}\leq k$, then $R_{j_{r}}$ is playable in both trees, and playing
$R_{j_{r}}$ leads to the “terminal phase” of the $k$-fuses, which we already
know are isomorphic. If $j_{r}>k$ then playing $R_{j_{r}}$ is the same as
playing $R_{j_{r}-k}$ in $\mathcal{T}_{C_{j}}$ and
$\mathcal{T}_{C^{\prime}_{j}}$. Since $\mathcal{T}_{C_{j}}$ and
$\mathcal{T}_{C^{\prime}_{j}}$ are also almost isomorphic, $R_{j_{r}-k}$ is
playable in one tree if and only if it is playable in the other. ∎

We first analyze the quasi-infinite trees of the families $B(WB)^{k}$ and
$W(BW)^{k}$. For the former family, the recurrent cycle elements are

$\displaystyle C_{1}$
$\displaystyle=(\overline{2},0,2,0,2,0,\ldots,2,0,1,\ldots)$ $\displaystyle
C_{2}$ $\displaystyle=(0,\overline{2},0,2,0,\ldots,2,0,1,2,\ldots)$
$\displaystyle C_{3}$
$\displaystyle=(\overline{2},0,\overline{2},0,\ldots,2,0,1,2,0,\ldots)$
$\displaystyle C_{4}$
$\displaystyle=(0,\overline{2},0,\ldots,2,0,1,2,0,2,\ldots)$
$\displaystyle\vdots$ $\displaystyle C_{2k-2}$
$\displaystyle=(0,\overline{2},0,1,2,0,2,\ldots,0,2,\ldots)$ $\displaystyle
C_{2k-1}$
$\displaystyle=(\overline{2},0,\overline{1},2,0,2,\ldots,0,2,0,\ldots)$
$\displaystyle C_{2k}$
$\displaystyle=(0,\overline{1},2,0,2,\ldots,0,2,0,2,\ldots)$ $\displaystyle
C_{2k+1}$
$\displaystyle=(\overline{1},\overline{2},0,2,\ldots,0,2,0,2,0,\ldots)$

where each element has $k$ twos, $k$ zeros and a one. Similarly, the recurrent
cycle elements of the latter family are

$\displaystyle C^{\prime}_{1}$
$\displaystyle=(\overline{1},0,2,0,2,0,\ldots,2,0,2,\ldots)$ $\displaystyle
C^{\prime}_{2}$ $\displaystyle=(0,\overline{2},0,2,0,\ldots,2,0,2,1,\ldots)$
$\displaystyle C^{\prime}_{3}$
$\displaystyle=(\overline{2},0,\overline{2},0,\ldots,2,0,2,1,0,\ldots)$
$\displaystyle C^{\prime}_{4}$
$\displaystyle=(0,\overline{2},0,\ldots,2,0,2,1,0,2,\ldots)$
$\displaystyle\vdots$ $\displaystyle C^{\prime}_{2k-2}$
$\displaystyle=(0,\overline{2},0,2,1,0,2,\ldots,0,2,\ldots)$ $\displaystyle
C^{\prime}_{2k-1}$
$\displaystyle=(\overline{2},0,\overline{2},1,0,2,\ldots,0,2,0,\ldots)$
$\displaystyle C^{\prime}_{2k}$
$\displaystyle=(0,\overline{2},1,0,2,\ldots,0,2,0,2,\ldots)$ $\displaystyle
C^{\prime}_{2k+1}$
$\displaystyle=(\overline{2},\overline{1},0,2,\ldots,0,2,0,2,0,\ldots)$

where each element also has $k$ twos, $k$ zeros and a one.

Our first lemma is clear.

######  Lemma 4.2.

For $i=1$ and $i=2j$ ($1\leq j\leq k$), $\mathcal{T}_{C_{i}}$ and
$\mathcal{T}_{C^{\prime}_{i}}$ are almost isomorphic.

###### Proof.

This is clear because for these $C_{i}$, there is only one playable move,
which gives $C_{i+1}$. Thus, the degenerate tree has only two elements:
$C_{i}$ and the degenerate element for $\mathcal{T}_{C_{i+1}}$. ∎

Our next lemma is also straightforward.

######  Lemma 4.3.

$\mathcal{T}_{C_{2k+1}}$ and $\mathcal{T}_{C^{\prime}_{2k+1}}$ are almost
isomorphic.

###### Proof.

From $C_{2k+1}$, we have two moves: $R_{1}$ and $R_{2}$. If we play $R_{1}$,
we get the degenerate element for $\mathcal{T}_{C_{1}}$. If we play $R_{2}$,
we get a $1$-fuse followed by $C_{2}$, which is also a degenerate element. The
tree for $C^{\prime}_{2k+1}$ is exactly the same, so they are almost
isomorphic. ∎

Now we tackle the more complicated elements.

######  Lemma 4.4.

For $i=2j+1$ ($1\leq j\leq k-1$), $\mathcal{T}_{C_{i}}$ and
$\mathcal{T}_{C^{\prime}_{i}}$ are almost isomorphic.

###### Proof.

First note that

$C_{i}=(\overline{2},0,\overline{2},0,\ldots,0,1,2,\ldots)$

and

$C^{\prime}_{i}=(\overline{2},0,\overline{2},0,\ldots,0,2,1,\ldots).$

Specifically, both elements begin with
$(\overline{2},0,\overline{2},0,2,0,\ldots)$ and the first difference is in
the $(2k+1-2i)$th and $(2k+2-2i)$th parts where those of $C_{i}$ are $1,2$
while those of $C^{\prime}_{i}$ are $2,1$. Let us call these two parts the
significant parts. Until these two parts are played, the two trees are
isomorphic. Now we claim that in order for the significant parts to be
playable, we need to always play the last playable part, i.e. the playable
part with the largest index. Indeed, suppose we have an element
$(\overline{2},\overline{2},\ldots,\overline{2},0,\overline{2},0,\ldots)$
(note that $C_{i}$ and $C^{\prime}_{i}$ also have this form themselves), if we
play the last playable part, then we get another element of this form. If we
do not play the last playable part, then we reach an $\ell$-fuse
$(\overline{2},\ldots,\overline{4},\overline{2},2,\ldots,2,0,2,\ldots)$. From
here, if we play $R_{j}$ with $j<\ell$, we trigger the terminating phase and
will eventually stop before the significant parts are playable. Else, we can
only play $R_{\ell}$ repeatedly until we get
$(\overline{2},\ldots,\overline{2m},0,\overline{2},\ldots)$, which is an
$\ell$-fuse followed by a recurrent cycle element. Thus, this degenerates to
an element before the significant parts are playable.

When the first significant part become playable, the elements in the two trees
are $(\overline{2},\ldots,\overline{2},0,\overline{1},2,\ldots)$ and
$(\overline{2},\ldots,\overline{2},0,\overline{2},1,\ldots)$. Similar to
above, if we do not play the last playable part, we will either terminate or
get a fuse followed by $C_{2k}$ and $C^{\prime}_{2k}$, and so the subtrees are
almost isomorphic. If we play the last playable part, then we get
$(\overline{2},\ldots,\overline{2},\overline{1},\overline{2},0,2,\ldots)$ and
$(\overline{2},\ldots,\overline{2},\overline{2},\overline{1},0,2,\ldots)$.
Once again, if we do not play the last playable part, then the subtrees are
almost isomorphic. If we play the last playable part, in both trees, we get
$(\overline{2},\ldots,\overline{2},\overline{3},0,\overline{2},\ldots)$, which
is a fuse followed by $C_{2}$ and $C^{\prime}_{2}$, and so this degenerates to
the same element in both trees, and hence the trees are almost isomorphic. ∎

The last three lemmas combine to prove Theorem 1.2.

######  Theorem 1.2.

For $k\geq 1$, one has

$H_{B(WB)^{k}}(x)=H_{W(BW)^{k}}(x).$

###### Proof.

From the lemmas, we have that $\mathcal{T}_{C_{i}}$ and
$\mathcal{T}_{C^{\prime}_{i}}$ are almost isomorphic for all $i$, so they are
isomorphic for all $i$. Thus, the generating functions $g_{i}$ and
$g^{\prime}_{i}$ are the same for all $i$, and hence
$H_{B(WB)^{k}}(x)=H_{W(BW)^{k}}(x)$. ∎

##  5 $BW^{k}$ and $WB^{k}$

Now, we shift our focus to the families $BW^{k}$ and $WB^{k}$ and Theorem 1.3,
asserting that $H_{BW^{k}}(x)$ and $H_{WB^{k}}(x)$ can be both written as a
rational function over the same denominator of degree $k+1$ for $k\geq 1$.

Let us start with a warm-up example with $P=BWWW$. Figure 16 shows the
degenerated forest for this necklace.

Figure 16: $F_{BWWW}$ degenerated

From Figure 16, we can write the following system of equations

$\displaystyle\begin{cases}g_{1}&=1+x+2x^{2}+2x^{3}+xg_{2}+(x^{4}+x^{3}u_{1}+x^{2}u_{2})g_{1}\\\
g_{2}&=1+xg_{3}\\\ g_{3}&=1+xg_{4}+xu_{1}g_{1}\\\ g_{4}&=1+xg_{1}.\end{cases}$
(5)

We can solve this system by substitution. We have

$g_{2}=1+xg_{3}=1+x(1+xg_{4}+xu_{1}g_{1})=1+x(1+x(1+xg_{1})+xu_{1}g_{1})$
$=1+x+x^{2}+x^{3}g_{1}+x^{2}u_{1}g_{1}.$

Thus,

$\displaystyle g_{1}$
$\displaystyle=1+x+2x^{2}+2x^{3}+xg_{2}+(x^{4}+x^{3}u_{1}+x^{2}u_{2})g_{1}$
$\displaystyle=A_{1}+(2x^{4}+2x^{3}u_{1}+x^{2}u_{2})g_{1}$
$\displaystyle=A_{1}+(2x^{4}+2x^{3}(1+x)+x^{2}(1+2x+2x^{2}))g_{1}$
$\displaystyle=A_{1}+(6x^{4}+4x^{3}+x^{2})g_{1}.$

Therefore,

$g_{1}=\dfrac{-A_{1}}{6x^{4}+4x^{3}+x^{2}-1}.$

Working backwards, we can solve for $g_{2},g_{3}$ and $g_{4}$:

$\displaystyle g_{4}$
$\displaystyle=1+xg_{1}=1+x\dfrac{-A_{1}}{6x^{4}+4x^{3}+x^{2}-1}=\dfrac{-A_{4}}{6x^{4}+4x^{3}+x^{2}-1}$
$\displaystyle g_{3}$
$\displaystyle=1+xg_{4}+xu_{1}g_{1}=\dfrac{-A_{3}}{6x^{4}+4x^{3}+x^{2}-1}$
$\displaystyle g_{2}$
$\displaystyle=1+xg_{3}=\dfrac{-A_{2}}{6x^{4}+4x^{3}+x^{2}-1}$

for some polynomials $A_{2},A_{3},A_{4}$. Recall from Section 2.4 that this
means

$g=g_{1}+g_{2}+g_{3}+g_{4}=\dfrac{-A_{1}(x)-A_{2}(x)-A_{3}(x)-A_{4}(x)}{6x^{4}+4x^{3}+x^{2}-1},$

and hence

$H_{BWWW}(x)=(1-x)\dfrac{-A_{1}(x)-A_{2}(x)-A_{3}(x)-A_{4}(x)}{6x^{4}+4x^{3}+x^{2}-1}.$

Thus, $H_{BWWW}(x)$ can be written as a rational generating function over a
polynomial of degree $4$.

Similarly, for $P=WBBB$, we have the following system of equations. We
encourage the readers to check that this is the correct system.

$\displaystyle\begin{cases}g_{1}&=1+x+x^{2}+xg_{2}+(x^{3}+x^{2}u_{1}+xu_{2})g_{4}\\\
g_{2}&=1+xg_{3}+xu_{1}g_{4}\\\ g_{3}&=1+xg_{4}\\\ g_{4}&=1+xg_{1}.\end{cases}$

Although this system is a bit different from (5), by substitution, we also
have

$g_{2}=1+xg_{3}+xu_{1}g_{4}=1+x(1+x(1+xg_{1}))+xu_{1}(1+xg_{1})$
$=1+x+x^{2}+xu_{1}+x^{3}g_{1}+x^{2}u_{1}g_{1}.$

Thus,

$\displaystyle g_{1}$
$\displaystyle=1+x+x^{2}+xg_{2}+(x^{3}+x^{2}u_{1}+xu_{2})g_{4}$
$\displaystyle=A^{\prime}_{1}+(x^{4}+x^{3}u_{1})g_{1}+(x^{4}+x^{3}u_{1}+x^{2}u_{2})g_{1}$
$\displaystyle=A^{\prime}_{1}+(2x^{4}+2x^{3}u_{1}+x^{2}u_{2})g_{1}$
$\displaystyle=A^{\prime}_{1}+(2x^{4}+2x^{3}(1+x)+x^{2}(1+2x+2x^{2}))g_{1}$
$\displaystyle=A^{\prime}_{1}+(6x^{4}+4x^{3}+x^{2})g_{1}.$

This means that

$g_{1}=\dfrac{-A^{\prime}_{1}}{6x^{4}+4x^{3}+x^{2}-1},$

and similar to above, eventually we have

$H_{BWWW}(x)=(1-x)\dfrac{-A^{\prime}_{1}(x)-A^{\prime}_{2}(x)-A^{\prime}_{3}(x)-A^{\prime}_{4}(x)}{6x^{4}+4x^{3}+x^{2}-1}$

for some polynomial $A^{\prime}_{2},A^{\prime}_{3},A^{\prime}_{4}$. This is
also a generating function over the same polynomial of degree $4$ as
$H_{BWWW}$.

Observe that in both examples above, we use substitution to derive

$g_{1}=A+(6x^{4}+4x^{3}+x^{2})g_{1}$

for some polynomial $A$. This means we have

$g_{1}=\dfrac{-A}{6x^{4}+4x^{3}+x^{2}-1},$

and eventually we can write both $H_{BWWW}$ and $H_{WBBB}$ as a generating
function over $6x^{4}+4x^{3}+x^{2}-1$, which is a polynomial of degree $4$.
This will be our main strategy in this section.

Also, observe from the example that in both cases, we encounter the sum
$x^{2}+xu_{1}+u_{2}$. This sum is indeed homogeneous, for Proposition 3.9
shows that $u_{2}(x)$ has degree $2$ and $u_{1}(x)$ has degree $1$. Thus, for
our convenience, we will “normalize” our $u_{k}$’s by redefining

$u_{k}(x)=\sum_{i=0}^{k}c_{i,k-i}x^{i-k}$

where $c_{n,i}$ is the number of weak compositions of $n$ with exactly $i$
zeros. Under this new definition, the sum $x^{2}+xu_{1}+u_{2}$ becomes
$x^{2}(u_{0}+u_{1}+u_{2})$ (since $u_{0}=1$). This motivates the following
abbreviation:

######  Definition 5.1.

Let $v_{k}(x):=u_{0}(x)+u_{1}(x)+\ldots+u_{k}(x).$

Now, we are ready to carry out the computations for Theorem 1.3.

###  5.1 $BW^{k}$

First, we will deal with the more “friendly” family of the two. The recurrent
cycle elements of this family are

$\displaystyle C_{1}$
$\displaystyle=(\overline{1},\overline{1},1,1,1,\ldots,1,0,2,1,\ldots)$
$\displaystyle C_{2}$
$\displaystyle=(\overline{1},\overline{1},1,1,\ldots,1,0,2,1,1,\ldots)$
$\displaystyle C_{3}$
$\displaystyle=(\overline{1},\overline{1},1,\ldots,1,0,2,1,1,1,\ldots)$
$\displaystyle\vdots$ $\displaystyle C_{k-3}$
$\displaystyle=(\overline{1},\overline{1},0,2,1,1,\ldots,1,1,1,\ldots)$
$\displaystyle C_{k-2}$
$\displaystyle=(\overline{1},0,\overline{2},1,1,\ldots,1,1,1,1,\ldots)$
$\displaystyle C_{k-1}$
$\displaystyle=(0,\overline{2},1,1,\ldots,1,1,1,1,1,\ldots)$ $\displaystyle
C_{k}$ $\displaystyle=(\overline{2},\overline{1},1,\ldots,1,1,1,1,1,0,\ldots)$
$\displaystyle C_{k+1}$
$\displaystyle=(\overline{1},1,\ldots,1,1,1,1,1,0,2,\ldots)$

######  Definition 5.2.

For $k\geq 2$, define $f_{k}$ to be the polynomial such that when using
substitution to solve the system of equations for $BW^{k}$, we have

$g_{1}=A+f_{k}g_{1}$

for some polynomial $A$. Then $H_{BW^{k}}$ can be written as a rational
generating function over $f_{k}-1$.

It is actually not clear yet why such $f_{k}$ always exists. Its existence
will be proved in Proposition 5.5; furthermore, we will show that these
$f_{k}$’s satisfy the recurrence given in (6). Once we can write
$g_{1}=A+f_{k}g_{1}$, it follows that we can write $g_{1}$ as a rational
generating function over $f_{k}-1$. Along the way, Proposition 5.3 implies
that the equation for any $g_{\ell}$ only depends on
$g_{\ell+1},\ldots,g_{k+1}$ and $g_{1}$. Thus, we can iteratively write
$g_{k+1},\ldots,g_{2}$ as rational generating functions over $f_{k}-1$. This
implies that we can write $H_{BW^{k}}$ as a rational generating function over
$f_{k}-1$.

Let us start once again with an example that will illustrate the idea of the
recurrence. Figure 17 shows the quasi-infinite trees corresponding to the
recurrent cycle elements for $BWWWW=BW^{4}$. From the forest, we can set up
the following system of equations

$\displaystyle g_{1}$
$\displaystyle=A_{1}^{(4)}+xv_{0}g_{2}+x^{2}v_{0}g_{3}+x^{4}v_{1}g_{5}+x^{5}u_{2}g_{1}$
$\displaystyle g_{2}$
$\displaystyle=A_{2}^{(4)}+xv_{0}g_{3}+x^{3}v_{1}g_{5}+x^{4}u_{2}g_{1}$
$\displaystyle g_{3}$ $\displaystyle=A_{3}^{(4)}+xv_{0}g_{4}$ $\displaystyle
g_{4}$ $\displaystyle=A_{4}^{(4)}+xv_{0}g_{5}+x^{2}u_{1}g_{1}$ $\displaystyle
g_{5}$ $\displaystyle=A_{5}^{(4)}+xv_{0}g_{1}$

where each $A_{i}^{(4)}$ is a sum of the terms whose weights do not contain
any $g_{i}$. Hence, each $A_{i}^{(4)}$ is not relevant to our study of the
denominator.

Figure 17: Quasi-infinite forest for $BWWWW$

Similarly, we can set up the following system for $BWWWWW=BW^{5}$

$\displaystyle g_{1}$
$\displaystyle=A_{1}^{(5)}+xv_{0}g_{2}+x^{3}v_{1}g_{4}+x^{5}v_{2}g_{6}+x^{6}u_{3}g_{1}$
$\displaystyle g_{2}$
$\displaystyle=A_{2}^{(5)}+xv_{0}g_{3}+x^{2}v_{0}g_{4}+x^{4}v_{1}g_{6}+x^{5}u_{2}g_{1}$
$\displaystyle g_{3}$
$\displaystyle=A_{3}^{(5)}+xv_{0}g_{4}+x^{3}v_{1}g_{6}+x^{4}u_{2}g_{1}$
$\displaystyle g_{4}$ $\displaystyle=A_{4}^{(5)}+xv_{0}g_{5}$ $\displaystyle
g_{5}$ $\displaystyle=A_{5}^{(5)}+xv_{0}g_{6}+x^{2}u_{1}g_{1}$ $\displaystyle
g_{6}$ $\displaystyle=A_{6}^{(5)}+xv_{0}g_{1}$

Observe that the equations for $g_{2},g_{3},\ldots,g_{6}$ are exactly the same
(up to shifting the indices) as those for $g_{1},g_{2},\ldots,g_{5}$ for
$BW^{4}$. This is indeed true in general.

######  Proposition 5.3.

If for $P=BW^{k}$ we have an equation

$g_{\ell}=A_{\ell}^{(k)}+\sum_{i>0}x^{i}a_{i}g_{\ell+i}$

where $a_{i}$ is some coefficient (in this case $a_{i}$ is either $v_{j}$ or
$u_{j}$ for some $j$), then for $P=BW^{k+m}$, we have an equation

$g_{\ell+m}=A_{\ell+m}^{(k+m)}+\sum_{i>0}x^{i}a_{i}g_{\ell+m+i}.$

###### Proof.

The equation $g_{\ell}=A_{\ell}^{(k)}+\sum_{i>0}x^{i}a_{i}g_{\ell+i}$ for
$P=BW^{k}$ is set up using the quasi-infinite tree rooted at the element

$(\underbrace{\overline{1},\overline{1},1,\ldots,1}_{j\text{ copies of
}1},0,2,1,\ldots)$

for some $j$. Then, for $P=BW^{k+m}$, the equation for $g_{\ell+m}$ is set up
using the quasi-infinite tree rooted at the element of the exact same type,
i.e.

$(\underbrace{\overline{1},\overline{1},1,\ldots,1}_{j\text{ copies of
}1},0,2,1,\ldots).$

Thus, the equations are the same up to shifting of the indices. ∎

Proposition 5.3 leads to a useful corollary.

######  Corollary 5.4.

If for $P=BW^{k}$, we have

$g_{1}=A^{(k)}+f_{k}g_{1}$

for some polynomial $A^{(k)}$, then for $P=BW^{k+m}$, we have

$g_{m+1}=A^{(k+m)}+f_{k}g_{1}$

for some polynomial $A^{(k+m)}$.

###### Proof.

The equations for $g_{1},\ldots,g_{k+1}$ of $BW^{k}$ is the same as those for
$g_{m+1},\ldots,g_{k+m+1}$ for $BW^{k+m}$, so substitution yields the desired
identity. ∎

For example, for $P=BW^{4}$, we computed that
$g_{1}=A^{(4)}+(12x^{5}+8x^{4}+2x^{3})g_{1}$, then we know that for
$P=BW^{5}$, we have $g_{2}=A^{(5)}+(12x^{5}+8x^{4}+2x^{3})g_{1}$. Thus, we
obtain the following recurrence.

######  Proposition 5.5.

The coefficients $f_{n}$ satisfy the following recurrence

$\displaystyle
f_{n}=\begin{cases}\left(\sum_{i=0}^{\frac{n-4}{2}}x^{2i+1}v_{i}f_{n-(2i+1)}\right)+x^{n-2}v_{\frac{n-4}{2}}f_{2}+x^{n+1}v_{\frac{n}{2}}&~{}~{}\text{if
$n$ is even}\\\
\left(\sum_{i=0}^{\frac{n-3}{2}}x^{2i+1}v_{i}f_{n-(2i+1)}\right)+x^{n+1}v_{\frac{n+1}{2}}&~{}~{}\text{if
$n$ is odd}\end{cases}.$ (6)

###### Proof.

This proposition is best illustrated by a figure.

Figure 18: Quasi-infinite trees $\mathcal{T}_{C_{1}}$ when $n$ is even (left)
and odd (right)

Figure 18 shows the quasi-infinite trees $\mathcal{T}_{C_{1}}$ for both cases.
Hence, we can set up the equation

$\displaystyle
g_{1}=A_{1}^{(n)}+\begin{cases}\left(\sum_{i=0}^{\frac{n-4}{2}}x^{2i+1}v_{i}g_{2i+2}\right)+x^{n-2}v_{\frac{n-4}{2}}g_{n-1}+x^{n}v_{\frac{n-2}{2}}g_{n+1}+x^{n+1}u_{\frac{n}{2}}g_{1}&\text{if
$n$ is even}\\\
\left(\sum_{i=0}^{\frac{n-3}{2}}x^{2i+1}v_{i}g_{2i+2}\right)+x^{n}v_{\frac{n-1}{2}}g_{n+1}+x^{n+1}u_{\frac{n+1}{2}}g_{1}&\text{if
$n$ is odd}\end{cases}.$

By Corollary 5.4, each $g_{i+1}$ can be substituted by $A_{i+1}+f_{n-i}g_{1}$
for some polynomial $A_{i+1}$. In addition, in both cases, we have
$g_{n+1}=1+xg_{1}$, and since $v_{i}+u_{i+1}=v_{i+1}$, we have

$x^{n}v_{\frac{n-2}{2}}g_{n+1}+x^{n+1}u_{\frac{n}{2}}g_{1}=x^{n}v_{\frac{n-2}{2}}+x^{n+1}v_{\frac{n}{2}}g_{1}$

for even $n$ and

$x^{n}v_{\frac{n-1}{2}}g_{n+1}+x^{n+1}u_{\frac{n+1}{2}}g_{1}=x^{n}v_{\frac{n-1}{2}}+x^{n+1}v_{\frac{n+1}{2}}g_{1}$

for odd $n$. Thus,

$\displaystyle
g_{1}=A^{(n)}+\begin{cases}\left(\sum_{i=0}^{\frac{n-4}{2}}x^{2i+1}v_{i}f_{n-(2i+1)}g_{1}\right)+x^{n-2}v_{\frac{n-4}{2}}f_{2}g_{1}+x^{n+1}v_{\frac{n}{2}}g_{1}&~{}~{}\text{if
$n$ is even}\\\
\left(\sum_{i=0}^{\frac{n-3}{2}}x^{2i+1}v_{i}g_{2i+2}\right)+x^{n+1}v_{\frac{n+1}{2}}g_{1}&~{}~{}\text{if
$n$ is odd}\end{cases}$

for some polynomial $A^{(n)}$. This gives equation (6). ∎

######  Corollary 5.6.

For all $n$, $f_{n}$ has degree $n+1$.

###### Proof.

This is immediate from (6), knowing that $v_{i}$ has degree $0$ for all $i$. ∎

Corollary 5.6 means that for all $n$, $H_{BW^{n}}$ can be written as a
generating function over $f_{n}-1$, which is a polynomial of degree $n+1$.

###  5.2 $WB^{k}$

Now we will shift our attention to the other family, namely $WB^{k}$. The
recurrent cycle elements of this family are

$\displaystyle C_{1}$
$\displaystyle=(\overline{1},\overline{1},\overline{1},1,1,\ldots,2,0,\ldots)$
$\displaystyle C_{2}$
$\displaystyle=(\overline{1},\overline{1},1,1,\ldots,2,0,1,\ldots)$
$\displaystyle C_{3}$
$\displaystyle=(\overline{1},\overline{1},1,\ldots,2,0,1,1,\ldots)$
$\displaystyle\vdots$ $\displaystyle C_{k-2}$
$\displaystyle=(\overline{1},\overline{1},2,0,1,1,1,\ldots,1,\ldots)$
$\displaystyle C_{k-1}$
$\displaystyle=(\overline{1},\overline{2},0,1,1,1,\ldots,1,1,\ldots)$
$\displaystyle C_{k}$
$\displaystyle=(\overline{2},0,1,1,1,\ldots,1,1,1,\ldots)$ $\displaystyle
C_{k+1}$ $\displaystyle=(0,\overline{1},1,1,\ldots,1,1,1,2,\ldots)$

Figure 19 shows the forest for $P=WBBBB=WB^{4}$.

Figure 19: Quasi-infinite forest for $WBBBB$

From Figure 19, we can set up the following system of equations.

$\displaystyle g_{1}$
$\displaystyle=B_{1}^{(4)}+xv_{0}g_{2}+x^{3}v_{1}g_{4}+x^{4}u_{2}g_{5}+x^{3}v_{1}g_{4}+x^{4}u_{2}g_{5}$
$\displaystyle g_{2}$
$\displaystyle=B_{2}^{(4)}+xv_{0}g_{3}+x^{2}v_{0}g_{4}+x^{3}u_{1}g_{5}$
$\displaystyle g_{3}$ $\displaystyle=B_{3}^{(4)}+xv_{0}g_{4}+x^{2}u_{1}g_{5}$
$\displaystyle g_{4}$ $\displaystyle=B_{4}^{(4)}+xv_{0}g_{5}$ $\displaystyle
g_{5}$ $\displaystyle=B_{5}^{(4)}+xv_{0}g_{1}$

Similarly, we can set up the following system for $P=WB^{5}$.

$\displaystyle g_{1}$
$\displaystyle=B_{1}^{(5)}+xv_{0}g_{2}+x^{3}v_{1}g_{4}+x^{4}v_{1}g_{5}+x^{5}u_{2}g_{6}+x^{4}v_{2}g_{5}+x^{5}u_{3}g_{6}$
$\displaystyle g_{2}$
$\displaystyle=B_{2}^{(5)}+xv_{0}g_{3}+x^{3}v_{1}g_{5}+x^{4}u_{2}g_{6}$
$\displaystyle g_{3}$
$\displaystyle=B_{3}^{(5)}+xv_{0}g_{4}+x^{2}v_{0}g_{5}+x^{3}u_{1}g_{6}$
$\displaystyle g_{4}$ $\displaystyle=B_{4}^{(5)}+xv_{0}g_{5}+x^{2}u_{1}g_{6}$
$\displaystyle g_{5}$ $\displaystyle=B_{5}^{(5)}+xv_{0}g_{6}$ $\displaystyle
g_{6}$ $\displaystyle=B_{6}^{(5)}+xv_{0}g_{1}$

Similar to the case for $P=BW^{k}$, we can see that the equations for
$g_{2},\ldots,g_{5}$ for $WB^{4}$ are the same as those for
$g_{3},\ldots,g_{6}$ for $WB^{5}$. However, there is a minor difference
between the equation for $g_{1}$ for $WB^{4}$ and that for $g_{2}$ for
$WB^{5}$. This is because $C_{1}$ has three playable parts, so besides the
main branch after playing $R_{1}$ and $R_{2}$, we also have the extra branch
after playing $R_{3}$. This extra branch, however, does not show up in longer
necklaces, so the equations are different. To take into account this minor
difference, we have a slightly different definition.

######  Definition 5.7.

For $k\geq 2$, let $h_{k}$ be the polynomial such that when using substitution
to solve the system of equation for $WB^{k+1}$, one has

$g_{2}=B+h_{k}g_{1}$

for some polynomial $B$.

Note that we have to define $h_{k}$ using the tree $\mathcal{T}_{C_{2}}$ of
$WB^{n+1}$ to account for the minor difference above. We also have two results
analogous to Proposition 5.3 and Corollary 5.4.

######  Proposition 5.8.

If for $P=WB^{k}$ we have an equation

$g_{\ell}=B_{\ell}^{(k)}+\sum_{i>0}x^{i}a_{i}g_{\ell+i}$

where $\ell>1$ and $a_{i}$ is some coefficient (in this case $a_{i}$ is either
$v_{j}$ or $u_{j}$ for some $j$), then for $P=BW^{k+m}$, we have an equation

$g_{\ell+m}=B_{\ell+m}^{(k+m)}+\sum_{i>0}x^{i}a_{i}g_{\ell+m+i}.$

######  Corollary 5.9.

If for $P=BW^{k+1}$, we have

$g_{2}=B^{(k)}+h_{k}g_{1}$

for some polynomial $B^{(k)}$, then for $P=BW^{k+m+1}$, we have

$g_{m+1}=B^{(k+m)}+h_{k}g_{1}$

for some polynomial $B^{(k+m)}$.

Moreover, we also have an analogous recurrence.

######  Proposition 5.10.

The coefficients $h_{n}$ satisfy the following recurrence

$\displaystyle
h_{n}=B+\begin{cases}\left(\sum_{i=0}^{\frac{n-4}{2}}x^{2i+1}v_{i}h_{n-(2i+1)}\right)+x^{n+1}v_{\frac{n}{2}}&~{}~{}\text{if
$n$ is even}\\\
\left(\sum_{i=0}^{\frac{n-3}{2}}x^{2i+1}v_{i}h_{n-(2i+1)}\right)+x^{n+1}v_{\frac{n-1}{2}}&~{}~{}\text{if
$n$ is odd}\end{cases}$ (7)

for some polynomial $B$.

###### Proof.

Once again, this proposition is best illustrated by a figure.

Figure 20: Main branch of $\mathcal{T}_{C_{1}}$ when $n$ is even (left) and
odd (right)

Figure 20 shows the main branch of $\mathcal{T}_{C_{1}}$ for both cases. Note
that in both cases, we have

$g_{n}=1+xg_{n+1}=1+x+x^{2}g_{1}$

and since $v_{i}+u_{i+1}=v_{i+1}$, we have

$x^{n-1}v_{\frac{n-2}{2}}g_{n}+x^{n}u_{\frac{n}{2}}g_{n+1}=C+x^{n+1}v_{\frac{n}{2}}g_{1}$

when $n$ is even, and

$x^{n-1}v_{\frac{n-3}{2}}g_{n}+x^{n}u_{\frac{n-1}{2}}g_{n+1}=C+x^{n+1}v_{\frac{n-1}{2}}g_{1}$

when $n$ is odd for some polynomial $C$. This gives equation 7. ∎

######  Corollary 5.11.

For all $n$, $h_{n}$ has degree $n+1$.

###### Proof.

This is immediate from equation (7), knowing that $v_{i}$ has degree $0$ for
all $i$. ∎

Before wrapping up this subsection, let us give the relationship between the
coefficients $h_{n}$ and the denominators of $H_{WB^{n}}(x)$.

######  Proposition 5.12.

For $n\geq 4$, define $p_{n}(x)$ by the condition that when using substitution
to solve the system of equations for $WB^{n}$, one has

$g_{1}=A+p_{n}g_{1}$

for some polynomial $A$. Thus, $H_{WB^{n}}$ can be written as a generating
function over $p_{n}-1$. Then,

$p_{n}=x^{-1}h_{n+1}-x^{2}v_{1}h_{n-2}.$

###### Proof.

Note that $p_{n}$ satisfies

$g_{1}=B+p_{n}g_{1}$

for some polynomial $B$ when solving the system of equations for $WB^{n}$. Let
us compute $p_{n}$. The main branch of $C_{1}$ contributes $h_{1}$ to $p_{n}$.
As for the extra branch, observe that the elements of this branch has the form
$(\overline{1},\overline{2},\overline{2},\ldots)$. If we replace the first
part $\overline{1}$ by $\overline{2}$, we get the elements in the main branch
of $C_{1}$ in $WB^{n+1}$. Note that this replacement does not change the
weight since it does not change the pre-fuses and fuses. Thus, the elements in
the extra branch of $C_{1}$ in $WB^{n}$ are those in the main branch of
$C_{1}$ in $WB^{n+1}$, with a few top elements missing, namely $xv_{0}g_{2}$
and $x^{3}v_{1}g_{4}$ (both in $WB^{n+1}$). Thus, the extra branch contributes
$x^{-1}(h_{n+1}-xv_{0}h_{n}-x^{3}v_{1}h_{n-2})$, where the coefficient
$x^{-1}$ is needed to shift the exponents. Since $v_{0}=1$, we have

$p_{n}=h_{n}+x^{-1}(h_{n+1}-xv_{0}h_{n}-x^{3}v_{1}h_{n-2})=x^{-1}h_{n+1}-x^{2}v_{1}h_{n-2}.$

∎

######  Corollary 5.13.

For all $n$, $p_{n}$ has degree $n+1$.

###### Proof.

This is immediate from the equation

$p_{n}=x^{-1}h_{n+1}-x^{2}v_{1}h_{n-2}$

because $h_{n+1}$ has degree $n+2$ and $h_{n-2}$ has degree $n-1$ (by
Corollary 5.11). ∎

By Corollary 5.13, for all $n$, $H_{WB^{n}}$ can be written as a generating
function over $p_{n}-1$, which is a polynomial of degree $n+1$.

###  5.3 Proof of Theorem 1.3

Now we are ready to prove Theorem 1.3.

######  Theorem 1.3.

For all $k\geq 1$, the functions $H_{BW^{k}}(x)$ and $H_{WB^{k}}(x)$ can both
be written over the same denominator which is a polynomial of degree $k+1$.

###### Proof.

By Corollary 5.6, $H_{BW^{k}}$ can be written as a generating function over
$f_{k}-1$, which is a polynomial of degree $k+1$. By Corollary 5.13,
$H_{WB^{k}}$ can be written as a generating function over $p_{k}-1$, which is
also a polynomial of degree $k+1$. Hence, it suffices to prove that
$f_{k}=p_{k}$ for all $k$.

For the base cases, when $k=1$, $BW$ and $WB$ are the same necklace, so
$H_{BW}=H_{WB}$. For $k=2$, Pham in [Pha22] (and Theorem 1.2) showed that
$H_{BWW}=H_{WBB}$. For $k=3$, the example at the beginning of this section
showed that $H_{BWWW}$ and $H_{WBBB}$ can both be written as a generating
function over $6x^{4}+4x^{3}+x^{2}-1$, which is a polynomial of degree $4$. In
particular, $p_{k}=f_{k}$ for $k\leq 3$. Thus, it suffices to prove that
$p_{k}$ satisfies equation (6) for $k\geq 4$.

  * •

Case 1: $k$ is even. We need to check

$p_{k}=\left(\sum_{i=0}^{\frac{k-4}{2}}x^{2i+1}v_{i}p_{k-(2i+1)}\right)+x^{k-2}v_{\frac{k-4}{2}}p_{2}+x^{k+1}v_{\frac{k}{2}}.$

Substituting $p_{i}=x^{-1}h_{i+1}-x^{2}v_{1}h_{i-2}$ for $i\geq 4$, this is
equivalent to

$\displaystyle x^{-1}h_{k+1}-x^{2}v_{1}h_{k-2}$
$\displaystyle=\left(\sum_{i=0}^{\frac{k-6}{2}}x^{2i+1}v_{i}\left(x^{-1}h_{k-2i}-x^{2}v_{1}h_{k-2i-3}\right)\right)$
$\displaystyle+x^{k-3}v_{\frac{k-4}{2}}p_{3}+x^{k-2}v_{\frac{k-4}{2}}p_{2}+x^{k+1}v_{\frac{k}{2}}.$

From equation 7, we have

$h_{k+1}=\left(\sum_{i=0}^{\frac{k-6}{2}}x^{2i+1}v_{i}h_{k-2i}\right)+x^{k-3}v_{\frac{k-4}{2}}h_{4}+x^{k-1}v_{\frac{k-2}{2}}h_{2}+x^{k+2}v_{\frac{k}{2}}$

and

$h_{k-2}=\left(\sum_{i=0}^{\frac{k-6}{2}}x^{2i+1}v_{i}h_{k-2i-3}\right)+x^{k-1}v_{\frac{k-2}{2}}.$

Thus, it suffices to check

$x^{-1}\left(x^{k-3}v_{\frac{k-4}{2}}h_{4}+x^{k-1}v_{\frac{k-2}{2}}h_{2}+x^{k+2}v_{\frac{k}{2}}\right)-x^{2}v_{1}\cdot
x^{k-1}v_{\frac{k-2}{2}}$
$=x^{k-3}v_{\frac{k-4}{2}}p_{3}+x^{k-2}v_{\frac{k-4}{2}}p_{2}+x^{k+1}v_{\frac{k}{2}}.$

Fortunately, this can be checked by direct computation. We have
$h_{4}=x^{5}(2v_{1}+v_{2})$, $h_{2}=x^{3}v_{1}$, $p_{3}=x^{4}(v_{1}+v_{2})$,
and $p_{2}=x^{3}v_{1}$. Hence,

LHS
$\displaystyle=x^{k+1}v_{\frac{k-4}{2}}(2v_{1}+v_{2})+x^{k+1}v_{\frac{k-2}{2}}v_{1}+x^{k+1}v_{\frac{k}{2}}-x^{k+1}v_{\frac{k-2}{2}}v_{1}$
$\displaystyle=x^{k+1}v_{\frac{k-4}{2}}(v_{1}+v_{2})+x^{k+1}v_{\frac{k-4}{2}}v_{1}+x^{k+1}v_{\frac{k}{2}}$
$\displaystyle=\text{RHS}.$

  * •

Case 2: $k$ is odd. We need to check

$p_{k}=\left(\sum_{i=0}^{\frac{k-3}{2}}x^{2i+1}v_{i}p_{k-(2i+1)}\right)+x^{k+1}v_{\frac{k+1}{2}}$

Substituting $p_{i}=x^{-1}h_{i+1}-x^{2}v_{1}h_{i-2}$ for $i\geq 4$, this is
equivalent to

$\displaystyle x^{-1}h_{k+1}-x^{2}v_{1}h_{k-2}$
$\displaystyle=\left(\sum_{i=0}^{\frac{k-5}{2}}x^{2i+1}v_{i}\left(x^{-1}h_{k-2i}-x^{2}v_{1}h_{k-2i-3}\right)\right)$
$\displaystyle+x^{k-2}v_{\frac{k-3}{2}}p_{2}+x^{k+1}v_{\frac{k+1}{2}}.$

From equation 7, we have

$h_{k+1}=\left(\sum_{i=0}^{\frac{k-5}{2}}x^{2i+1}v_{i}h_{k-2i}\right)+x^{k-2}v_{\frac{k-3}{2}}h_{3}+x^{k+2}v_{\frac{k+1}{2}}$

and

$h_{k-2}=\left(\sum_{i=0}^{\frac{k-5}{2}}x^{2i+1}v_{i}h_{k-2i-3}\right)+x^{k-1}v_{\frac{k-3}{2}}.$

Thus, it suffices to check

$x^{-1}\left(x^{k-2}v_{\frac{k-3}{2}}h_{3}+x^{k+2}v_{\frac{k+1}{2}}\right)-x^{2}v_{1}\cdot
x^{k-1}v_{\frac{k-3}{2}}$
$=x^{k-2}v_{\frac{k-3}{2}}p_{2}+x^{k+1}v_{\frac{k+1}{2}}.$

Again, by manual computation, we have $h_{3}=2x^{4}v_{1}$ and
$p_{2}=x^{3}v_{1}$. Hence,

LHS
$\displaystyle=2x^{k+1}v_{\frac{k-3}{2}}v_{1}+x^{k+1}v_{\frac{k+1}{2}}-x^{k+1}v_{\frac{k-3}{2}}v_{1}$
$\displaystyle=x^{k+1}v_{\frac{k-3}{2}}v_{1}+x^{k+1}v_{\frac{k+1}{2}}$
$\displaystyle=\text{RHS}.$

Therefore, $p_{k}$ satisfies equation (6), so the proof is complete. ∎

##  6 Discussion

As mentioned in the introduction, Theorem 1.3 is a special case of Conjecture
1.1 on the duality operation for primitive necklaces $P\mapsto P^{*}$, since
the dual of $BW^{k}$ is $B^{k}W=WB^{k}$. Theorem 1.2 is also a special case of
this conjecture, but the two families $B(WB)^{k}$ and $W(BW)^{k}$ also have a
stronger property that $H_{B(WB)^{k}(x)}$ and $H_{W(BW)^{k}}(x)$ are the same.
We hope that our new representation and the combinatorial interpretation of
$k$-fuses may lead to a proof of the conjecture. Furthermore, our proof of
Theorem 1.3 is computationally heavy and is not combinatorial, so a new
combinatorial proof of Theorem 1.3 may shed light on a proof of the general
conjecture.

Pham proposed another nice conjecture about the size of the finite Bulgarian
solitaire orbits $\mathcal{O}_{P^{k}}$ for primitive necklaces $P$.

######  Conjecture 6.1.

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

$|\mathcal{O}_{P^{k}}|=c_{P}^{k-1}|\mathcal{O}_{P}|.$

If such $c_{P}$ exist, then there is an even more beautiful conjecture.

######  Conjecture 6.2.

For any primitive necklace $P$ such that $c_{P}$ and $c_{P^{*}}$ both exist,

$c_{P}=c_{P^{*}}.$

A special case was proved in by Pham in her thesis.

######  Theorem 6.3.

For all $k$,

$|\mathcal{O}_{(BWW)^{k}}|=5^{k}$

and

$|\mathcal{O}_{(BBW)^{k}}|=7\cdot 5^{k-1}.$

Thus,

$c_{BWW}=c_{BBW}=5.$

It is also an interesting question to find a combinatorial interpretation of
these $c_{P}$. In addition, the relationship between $c_{P}$ and the
denominator of $H_{P}$ is not clear. For example, $BWBWBWB$ and $BWBBWWW$ are
not the dual of each other, and $c_{BWBWBWB}=63\neq c_{BWBBWWW}=94$, yet our
data shows that

$H_{BWBWBWB}(x)=H_{BWBBWWW}(x)$
$=(1-x)\dfrac{x^{9}+8x^{8}+42x^{7}-19x^{6}-63x^{5}-56x^{4}-34x^{3}-18x^{2}-10x-7}{18x^{7}+16x^{6}+6x^{5}+x^{4}-1}.$

The converse appears to be more probable. The smallest and only interesting
example that we could compute is $WWWBBWWB$ and $WWWBBWBB$. They are not the
dual of each other, but our data shows that

$c_{WWWBBWWB}=c_{WWWBBWBB}=135,$

and indeed $H_{WWWBBWWB}(x)$ and $H_{WWWBBWBB}(x)$ have the same denominator.
Thus, we make the following conjecture.

######  Conjecture 6.4.

For any two primitive necklaces $P_{1}$ and $P_{2}$, if $c_{P_{1}}=c_{P_{2}}$
then $H_{P_{1}}(x)$ and $H_{P_{2}}(x)$ have the same denominator.

More data about $c_{P}$ and $H_{P}$ can be found in the Appendix below.

## Acknowledgments

We would like to offer our sincerest thanks to Nhung Pham for sparking our
interest in the Bulgarian Solitaire Problem, as well as to Vic Reiner for
providing us with his expert guidance throughout this project. We would also
like to thank Elise Catania and Connor McCausland for their help with editing
and proofreading.

## References

  * [Bra82] Jørgen Brandt.  Cycles of partitions.  Proceedings of the American Mathematical Society, pages 483–486, 1982.
  * [EJ17] Henrik Eriksson and Markus Jonsson.  Level sizes of the bulgarian solitaire game tree.  The Fibonacci quarterly, 55(3):243–251, 2017.
  * [Pha22] Nhung Pham.  Limiting behavior in growth of bulgarian solitaire orbits.  arXiv preprint arXiv:2208.14496, 2022.

## Appendix: Data

### Data on the conjectural ratios $c_{P}$

These tables show the conjectural $c_{P}$ and $|\mathcal{O}_{P^{k}}|$ for
primitive necklaces of size up to 8.

$P$ | $c_{P}$ | $|\mathcal{O}_{P^{k}}|$ | Verified for
---|---|---|---
$BWWW$ | 15 | $15\cdot 15^{k-1}$ | $k\leq 6$
$BBBW$ | 15 | $30\cdot 15^{k-1}$ | $k\leq 6$
$BBWW$ | 10 | $15\cdot 10^{k-1}$ | $k\leq 6$
Table 1: $|\mathcal{O}_{P^{k}}|$ and $c_{P}$ for primitive necklaces of size $4$ $P$ | $c_{P}$ | $|\mathcal{O}_{P^{k}}|$ | Verified for
---|---|---|---
$BWWWW$ | 44 | $56\cdot 44^{k-1}$ | $k\leq 4$
$BBBBW$ | 44 | $135\cdot 44^{k-1}$ | $k\leq 4$
$BBWWW$ | 27 | $45\cdot 27^{k-1}$ | $k\leq 4$
$BBBWW$ | 27 | $67\cdot 27^{k-1}$ | $k\leq 4$
$BWBWB$ | 17 | $34\cdot 17^{k-1}$ | $k\leq 5$
$WBWBW$ | 17 | $32\cdot 17^{k-1}$ | $k\leq 5$
Table 2: $|\mathcal{O}_{P^{k}}|$ and $c_{P}$ for primitive necklaces of size $5$ $P$ | $c_{P}$ | $|\mathcal{O}_{P^{k}}|$ | Verified for
---|---|---|---
$BWWWWW$ | 164 | $231\cdot 164^{k-1}$ | $k\leq 3$
$BBBBBW$ | 164 | $627\cdot 164^{k-1}$ | $k\leq 3$
$BBWWWW$ | 96 | $185\cdot 96^{k-1}$ | $k\leq 3$
$BBBBWW$ | 96 | $322\cdot 96^{k-1}$ | $k\leq 3$
$BBBWWW$ | 80 | $214\cdot 80^{k-1}$ | $k\leq 3$
$BWBWWW$ | 53 | $87\cdot 53^{k-1}$ | $k\leq 4$
$BBBWBW$ | 53 | $133\cdot 53^{k-1}$ | $k\leq 4$
$WWBWBB$ | 38 | $80\cdot 38^{k-1}$ | $k\leq 4$
$BBWBWW$ | 30 | $65\cdot 30^{k-1}$ | $k\leq 4$
Table 3: $|\mathcal{O}_{P^{k}}|$ and $c_{P}$ for primitive necklaces of size
$6$

$P$ | $c_{P}$ | $|\mathcal{O}_{P^{k}}|$ | Verified for
---|---|---|---
$BWWWWWW$ | 578 | $1002\cdot 578^{k-1}$ | $k\leq 2$
$BBBBBBW$ | 578 | $3010\cdot 578^{k-1}$ | $k\leq 2$
$BBWWWWW$ | 351 | $811\cdot 351^{k-1}$ | $k\leq 2$
$BBBBBWW$ | 351 | $1637\cdot 351^{k-1}$ | $k\leq 2$
$BBBWWWW$ | 290 | $777\cdot 290^{k-1}$ | $k\leq 2$
$BBBBWWW$ | 290 | $1114\cdot 290^{k-1}$ | $k\leq 2$
$BWBWWWW$ | 152 | $294\cdot 152^{k-1}$ | $k\leq 3$
$BBBBWBW$ | 152 | $544\cdot 152^{k-1}$ | $k\leq 3$
$BWBBWWW$ | 94 | $336\cdot 94^{k-1}$ | $k\leq 3$
$BBBWWBW$ | 94 | $286\cdot 94^{k-1}$ | $k\leq 3$
$BBWBWWW$ | 81 | $189\cdot 81^{k-1}$ | $k\leq 3$
$BBBWBWW$ | 81 | $255\cdot 81^{k-1}$ | $k\leq 3$
$BWWBWWW$ | 75 | $150\cdot 75^{k-1}$ | $k\leq 3$
$BBBWBBW$ | 75 | $255\cdot 75^{k-1}$ | $k\leq 3$
$WBWBWBW$ | 63 | $148\cdot 63^{k-1}$ | $k\leq 3$
$BWBWBWB$ | 63 | $158\cdot 63^{k-1}$ | $k\leq 3$
$BBWWBWW$ | 50 | $125\cdot 50^{k-1}$ | $k\leq 4$
$BBWBBWW$ | 50 | $145\cdot 50^{k-1}$ | $k\leq 4$
Table 4: $|\mathcal{O}_{P^{k}}|$ and $c_{P}$ for primitive necklaces of size
$7$

$P$ | $c_{P}$ | $|\mathcal{O}_{P^{k}}|$ | Verified for
---|---|---|---
$BWWWWWWW$ | 2313 | $4565\cdot 2313^{k-1}$ | $k\leq 2$
$BBBBBBBW$ | 2313 | $14883\cdot 2313^{k-1}$ | $k\leq 2$
$BBWWWWWW$ | 1426 | $3727\cdot 1426^{k-1}$ | $k\leq 2$
$BBBBBBWW$ | 1426 | $8463\cdot 1426^{k-1}$ | $k\leq 2$
$BBBWWWWW$ | 1185 | $3880\cdot 1185^{k-1}$ | $k\leq 2$
$BBBBBWWW$ | 1185 | $5972\cdot 1185^{k-1}$ | $k\leq 2$
$BBBBWWWW$ | 956 | $4420\cdot 956^{k-1}$ | $k\leq 2$
$BWBWWWWW$ | 562 | $1152\cdot 562^{k-1}$ | $k\leq 2$
$BBBBBWBW$ | 562 | $2414\cdot 562^{k-1}$ | $k\leq 2$
$WWWBWBBB$ | 436 | $1076\cdot 436^{k-1}$ | $k\leq 2$
$BBWBWWWW$ | 288 | $747\cdot 288^{k-1}$ | $k\leq 2$
$BBBBWBWW$ | 288 | $1158\cdot 288^{k-1}$ | $k\leq 2$
$BWBBWWWW$ | 273 | $815\cdot 273^{k-1}$ | $k\leq 2$
$BBBBWWBW$ | 273 | $1082\cdot 273^{k-1}$ | $k\leq 2$
$BBBWBWWW$ | 240 | $802\cdot 240^{k-1}$ | $k\leq 2$
$BWWBWWWW$ | 220 | $500\cdot 220^{k-1}$ | $k\leq 2$
$BBBBWBBW$ | 220 | $983\cdot 220^{k-1}$ | $k\leq 2$
$BWBWBWWW$ | 197 | $420\cdot 197^{k-1}$ | $k\leq 3$
$BBBWBWBW$ | 197 | $593\cdot 197^{k-1}$ | $k\leq 3$
$WWWBWWBB$ | 150 | $375\cdot 150^{k-1}$ | $k\leq 3$
$WWBBWBBB$ | 150 | $525\cdot 150^{k-1}$ | $k\leq 3$
$WWWBBWBB$ | 135 | $414\cdot 135^{k-1}$ | $k\leq 3$
$WWBWWBBB$ | 135 | $470\cdot 135^{k-1}$ | $k\leq 3$
$WWWBBWWB$ | 135 | $360\cdot 135^{k-1}$ | $k\leq 3$
$WBBWWBBB$ | 135 | $524\cdot 135^{k-1}$ | $k\leq 3$
$BBWBWWBW$ | 114 | $316\cdot 114^{k-1}$ | $k\leq 3$
$BBWBWBWW$ | 110 | $295\cdot 110^{k-1}$ | $k\leq 3$
$WWBWBWBB$ | 97 | $309\cdot 97^{k-1}$ | $k\leq 3$
$BWBWWBWW$ | 85 | $245\cdot 85^{k-1}$ | $k\leq 3$
$BBWBBWBW$ | 85 | $289\cdot 85^{k-1}$ | $k\leq 3$
Table 5: $|\mathcal{O}_{P^{k}}|$ and $c_{P}$ for primitive necklaces of size
$8$

### Data on the generating functions
$H_{P}(x)=\displaystyle\lim_{\ell\rightarrow\infty}\mathcal{D}_{P^{\ell}}(x)$

Here are $H_{P}(x),H_{P^{*}}(x)$ for some primitive necklaces $P$ and their
duals $P^{*}$.

$\displaystyle H_{BWW}$
$\displaystyle=(1-x)\dfrac{x^{3}-3x^{2}-4x-3}{2x^{3}+x^{2}-1}$
$\displaystyle=H_{BBW}$ $\displaystyle H_{BWWW}$
$\displaystyle=(1-x)\dfrac{x^{5}+8x^{4}-3x^{3}-8x^{2}-6x-4}{6x^{4}+4x^{3}+x^{2}-1}$
$\displaystyle H_{BBBW}$
$\displaystyle=(1-x)\dfrac{2x^{5}+8x^{4}-5x^{3}-10x^{2}-7x-4}{6x^{4}+4x^{3}+x^{2}-1}$
$\displaystyle H_{BBWW}$
$\displaystyle=(1-x)\dfrac{x^{5}+4x^{4}-3x^{3}-6x^{2}-6x-4}{3x^{4}+2x^{3}+x^{2}-1}$
$\displaystyle H_{BWWWW}$
$\displaystyle=(1-x)\dfrac{2x^{6}+16x^{5}-12x^{4}-23x^{3}-16x^{2}-8x-5}{12x^{5}+8x^{4}+2x^{3}-1}$
$\displaystyle H_{BBBBW}$
$\displaystyle=(1-x)\dfrac{4x^{6}+16x^{5}-16x^{4}-28x^{3}-19x^{2}-9x-5}{12x^{5}+8x^{4}+2x^{3}-1}$
$\displaystyle H_{BBWWW}$
$\displaystyle=(1-x)\dfrac{3x^{6}+14x^{5}-10x^{4}-19x^{3}-15x^{2}-8x-5}{9x^{5}+6x^{4}+2x^{3}-1}$
$\displaystyle H_{BBBWW}$
$\displaystyle=(1-x)\dfrac{3x^{6}+10x^{5}-15x^{4}-24x^{3}-18x^{2}-9x-5}{9x^{5}+6x^{4}+2x^{3}-1}$
$\displaystyle H_{BWBWB}$
$\displaystyle=(1-x)\dfrac{x^{6}+8x^{5}-9x^{4}-16x^{3}-12x^{2}-7x-5}{6x^{5}+4x^{4}+x^{3}-1}$
$\displaystyle=H_{WBWBW}$ $\displaystyle H_{BBBWWW}$
$\displaystyle=(1-x)\dfrac{6x^{8}+31x^{7}+69x^{6}-16x^{5}-57x^{4}-46x^{3}-24x^{2}-11x-6}{27x^{6}+20x^{5}+7x^{4}+x^{3}-1}$
$\displaystyle H_{BWWWWW}$
$\displaystyle=(1-x)\dfrac{2x^{8}+13x^{7}+51x^{6}-10x^{5}-49x^{4}-40x^{3}-21x^{2}-10x-6}{24x^{6}+20x^{5}+7x^{4}+x^{3}-1}$
$\displaystyle H_{BBBBBW}$
$\displaystyle=(1-x)\dfrac{4x^{8}+18x^{7}+52x^{6}-18x^{5}-61x^{4}-49x^{3}-25x^{2}-11x-6}{24x^{6}+20x^{5}+7x^{4}+x^{3}-1}$
$\displaystyle H_{BBWWWW}$
$\displaystyle=(1-x)\dfrac{3x^{8}+13x^{7}+39x^{6}-17x^{5}-43x^{4}-35x^{3}-20x^{2}-10x-6}{18x^{6}+13x^{5}+5x^{4}+x^{3}-1}$
$\displaystyle H_{BBBBWW}$
$\displaystyle=(1-x)\dfrac{6x^{8}+20x^{7}+40x^{6}-21x^{5}-51x^{4}-43x^{3}-24x^{2}-11x-6}{18x^{6}+13x^{5}+5x^{4}+x^{3}-1}$
$\displaystyle H_{BWBWWW}$
$\displaystyle=(1-x)\dfrac{x^{8}+8x^{7}+42x^{6}-x^{5}-35x^{4}-32x^{3}-18x^{2}-9x-6}{18x^{6}+16x^{5}+6x^{4}+x^{3}-1}$
$\displaystyle H_{BBBWBW}$
$\displaystyle=(1-x)\dfrac{2x^{8}+12x^{7}+43x^{6}-7x^{5}-43x^{4}-38x^{3}-21x^{2}-10x-6}{18x^{6}+16x^{5}+6x^{4}+x^{3}-1}$
$\displaystyle H_{BBWBWW}$
$\displaystyle=(1-x)\dfrac{2x^{7}+12x^{6}-3x^{5}-20x^{4}-23x^{3}-16x^{2}-9x-6}{6x^{6}+7x^{5}+4x^{4}+x^{3}-1}$
$\displaystyle H_{WWBWBB}$
$\displaystyle=(1-x)\dfrac{x^{7}+8x^{6}-15x^{5}-26x^{4}-21x^{3}-13x^{2}-8x-6}{6x^{6}+4x^{5}+x^{4}-1}$
$\displaystyle H_{BBWBWWW}$
$\displaystyle=(1-x)\dfrac{6x^{8}+40x^{7}-9x^{6}-67x^{5}-69x^{4}-42x^{3}-21x^{2}-11x-7}{18x^{7}+21x^{6}+10x^{5}+2x^{4}-1}$
$\displaystyle H_{BBBWBWW}$
$\displaystyle=(1-x)\dfrac{6x^{8}+32x^{7}-23x^{6}-79x^{5}-76x^{4}-47x^{3}-24x^{2}-12x-7}{18x^{7}+21x^{6}+10x^{5}+2x^{4}-1}$
$\displaystyle H_{BWBWBWB}$
$\displaystyle=(1-x)\dfrac{x^{9}+8x^{8}+42x^{7}-19x^{6}-63x^{5}-56x^{4}-34x^{3}-18x^{2}-10x-7}{18x^{7}+16x^{6}+6x^{5}+x^{4}-1}$
$\displaystyle=H_{WBWBWBW}$ $\displaystyle H_{BWBBWWW}$
$\displaystyle=(1-x)\dfrac{x^{9}+8x^{8}+42x^{7}-19x^{6}-63x^{5}-56x^{4}-34x^{3}-18x^{2}-10x-7}{18x^{7}+16x^{6}+6x^{5}+x^{4}-1}$
$\displaystyle H_{BBBWWBW}$
$\displaystyle=(1-x)\dfrac{2x^{9}+12x^{8}+43x^{7}-25x^{6}-77x^{5}-70x^{4}-43x^{3}-22x^{2}-11x-7}{18x^{7}+16x^{6}+6x^{5}+x^{4}-1}$
$\displaystyle H_{BBWWBWW}$
$\displaystyle=(1-x)\dfrac{2x^{8}+12x^{7}-9x^{6}-33x^{5}-38x^{4}-28x^{3}-17x^{2}-10x-7}{6x^{7}+7x^{6}+4x^{5}+x^{4}-1}$
$\displaystyle H_{BBWBBWW}$
$\displaystyle=(1-x)\dfrac{2x^{8}+12x^{7}-9x^{6}-32x^{5}-36x^{4}-26x^{3}-16x^{2}-10x-7}{6x^{7}+7x^{6}+4x^{5}+x^{4}-1}$
$\displaystyle H_{BWWBWWW}$
$\displaystyle=(1-x)\dfrac{2x^{8}+23x^{7}-12x^{6}-54x^{5}-53x^{4}-33x^{3}-18x^{2}-10x-7}{12x^{7}+14x^{6}+6x^{5}+x^{4}-1}$
$\displaystyle H_{BBBWBBW}$
$\displaystyle=(1-x)\dfrac{4x^{8}+24x^{7}-16x^{6}-60x^{5}-57x^{4}-36x^{3}-20x^{2}-11x-7}{12x^{7}+14x^{6}+6x^{5}+x^{4}-1}$