In this paper
AbstractIntroductionBackgroundPartitions and Ferrers diagramsClassical Bulgarian solitaireFour variants of Bulgarian solitaire on partitions with distinguishable cellsConnection to classical Bulgarian solitaireConnections between T1, T2, T3 and T4Initial analysis of the orbit sizesThe orbit size of pi under the action T1The orbit size of under the action The induced permutationColoring algorithmThe colored inducedEquality of the coloring and induced permutationsThe order of Exact sizes of orbits under Conjugation symmetriesReferencesWorksMathematics
Bulgarian solitaire with distinguishable cells
Abstract
Classical Bulgarian solitaire tracks only the sizes of the stacks. We ask how the lengths of its periodic orbits change when individual cards are distinguished. To study this question, we introduce four actions on partitions with labeled cells. The actions differ in whether the top or bottom cell is removed from each column and in the order in which the removed cells are arranged to form a new column. We determine the exact sizes of the periodic orbits for all four actions. The main work lies in the analysis of , for which we develop a coloring algorithm on Ferrers diagrams. The coloring encodes the cycle structure of the permutation of the labels induced by one full period of the underlying partition.
Introduction
Bulgarian solitaire is a mathematical game played with cards. One starts with cards divided into stacks and placed face down. One step of the game consists of taking one card from every stack to form a new stack. Figure 1 shows one move in a game with 5 cards, from the configuration with stack sizes to the configuration . Since the cards are treated as indistinguishable, a configuration is encoded by its stack sizes. These stack sizes are traditionally ordered in weakly decreasing order and represented as a partition of . Thus, Bulgarian solitaire defines a discrete dynamical system on the finite set of partitions of , and every sequence of iterates is eventually periodic.

Figure 1. One move of Bulgarian solitaire from to . Remove one card from each stack to create a stack of size 3; the original stack of size 3 becomes a stack of size 2, and the two singleton stacks disappear.
According to the survey [16], which also discusses the origin of the game’s name, Bulgarian solitaire initially spread among mathematicians through informal conversations. A central observation was that, when the number of cards is triangular, , every initial configuration eventually settles into the partition . This observation inspired several mathematicians to seek a proof (see, e.g., [2, 6]) and to investigate the behavior for general . Early analyses of the general case appeared in [3, 25]; see also [1, 14]. Gardner popularized the game in his Scientific American column, bringing it to an international audience [11].
The dynamics of Bulgarian solitaire have been studied from several perspectives, including the enumeration of periodic orbits and the study of periodicity [3, 12, 14, 20], as well as the analysis of Garden of Eden partitions [18, 19]. Related work examines the game graph and the distribution of level sizes [7, 13, 23]. Beyond the classical game, numerous variants have been studied (see, e.g., [4, 5, 9, 15, 17, 21, 22, 26]), including probabilistic versions (see, e.g., [8, 24]).
In the classical game, the cards are treated as indistinguishable and only the stack sizes are tracked. This paper asks what happens to individual cards as the game proceeds. A return of the stack sizes need not return each card to its original position, so the labeled configurations can have longer periods than their underlying partitions. To study this behavior, we extend Bulgarian solitaire to partitions with distinguishable cells, denoted by , and define four natural actions . These actions differ in whether a card is removed from the top or the bottom of each stack and in the order in which the removed cards are arranged to form a new stack. We determine the sizes of the periodic orbits for all four actions. The main work lies in the analysis of , for which we develop a coloring algorithm on Ferrers diagrams that describes how the cards are permuted over one period of the underlying partition.
The paper is organized as follows. Section 2 reviews partitions, Ferrers diagrams, and classical Bulgarian solitaire, including the characterization of periodic points. Section 3 introduces the four actions, establishes their relationship with the classical game, and uses reversal to reduce the orbit-size analysis to and . Section 4 determines the periodic orbit sizes under and develops the coloring algorithm for . Section 5 completes the analysis by determining the exact periodic orbit sizes under . Finally, Section 6 studies the interaction with conjugation and the resulting orbit-reversing symmetries.
Background
In this section, we recall the necessary definitions of partitions, Ferrers diagrams, and classical Bulgarian solitaire, in particular the characterization of periodic points, which will be used to analyze the generalization introduced later.
Partitions and Ferrers diagrams
Definition 2.1. A partition of a positive integer is a finite sequence of positive integers such that and . The integers are called the parts of the partition, and is called the length of the partition. The set of all partitions of is denoted by .
A partition of is traditionally represented by its Ferrers diagram: a left-aligned array of cells in which the -th row from the top contains cells. In our pictorial representation, we rotate this diagram by counterclockwise so that the parts correspond to columns (representing stacks of cards) rather than rows (e.g., Figure 2). We refer to the cells of this diagram using Euclidean coordinates, with the bottom-left cell at position .

Figure 2. Rotated Ferrers diagram of .
For two partitions and , we define their union to be the partition obtained by combining the parts of with those of and arranging the resulting entries in weakly decreasing order. For example, .
Classical Bulgarian solitaire
Bulgarian solitaire is a discrete dynamical system defined on . The system evolves through an iterative process governed by the following rule: from a given partition, remove one cell from each part (column) and use the removed cells to form a new part. Formally, Bulgarian solitaire is the map defined by
where parts of size zero are omitted. The set
is called the orbit of under . Since is finite, the sequence of iterates is eventually periodic. A partition is said to be periodic under the transformation if there exists a positive integer such that
The smallest such integer is called the period of under .
Definition 2.2. For a fixed positive integer , the -th upper diagonal, denoted by , is the set of positions
For a positive integer , let be the unique integer such that the -th triangular number satisfies
Define . The periodic points of were characterized by Toom as follows.
Theorem 2.3 [14, 25]. Let , let be the unique integer such that and let . Let be a partition of , and let denote its Ferrers diagram. Then is a periodic point of if and only if
In the special case where , contains only one periodic point, namely,
When is not triangular, the period of a periodic partition divides . As can be gleaned from Example 2.5, for periodic points, the newly formed part is always at least as large as all remaining parts and can be placed in the first position. The overall change in the Ferrers shape amounts to a cyclic downward shift of the cells in .
The number of distinct periodic orbits of under the action of is equal to the number of necklaces consisting of black beads and white beads, where the symmetry group is the cyclic group of order . Their number is given by the following elegant formula due to Brandt.
Theorem 2.4 [3]. Given , write uniquely as for some integer with . The number of distinct periodic orbits in under is
where is Euler’s totient function.
Example 2.5. Figure 3 illustrates the orbit of under . By Theorem 2.3, is a periodic point of . The action of corresponds to cyclically shifting the cells in down the diagonal.

Figure 3. Orbit of under .
In this case, , so and . The period is , which divides . This orbit corresponds to the unique necklace with black beads and white bead, shown in Figure 4.

Figure 4. A necklace with 2 black beads and 1 white bead.
The depth of classical Bulgarian solitaire is the maximum, over , of the minimum number of applications of needed to reach a periodic partition. Igusa [20] and Etienne [10] proved that for . Griggs and Ho [12] gave an upper bound for non-triangular numbers: for and , with equality when . For results on counting partitions according to the number of moves required to reach a given periodic orbit, see [13, 23].
Four variants of Bulgarian solitaire on partitions with distinguishable cells
When the cards are turned face up, each card becomes individually identifiable, so each stack is represented by an ordered sequence of distinct labels. This motivates the study of partitions with distinguishable cells, where the identity of each card is taken into account.
A partition with distinguishable cells is a Ferrers diagram whose cells are bijectively labeled by a fixed set of labels. No order conditions are imposed on the labels. We write each part as , where is the length of the -th column and the entries represent distinct cells. We depict each as a column in the Ferrers diagram, and denotes the labeled cell in position , that is, the cell in the -th column and -th row.
We denote the set of all partitions of with distinguishable cells by . The set of all labeled cells of a partition's Ferrers diagram is denoted by .
Example 3.1. Consider the partition with distinguishable cells . It corresponds to the Ferrers diagram shown in Figure 5.
Figure 5. Ferrers diagram of .
Moreover, we have .
For two partitions with distinguishable cells and with disjoint label sets, define their union by combining their columns and arranging them in weakly decreasing order of length. The order of the cells within each column is preserved. Among columns of the same length, the original left-to-right order within each partition is preserved, and all columns from are placed before those from . For example,
We now introduce four actions, for , acting on . Each action is defined by choosing a rule for removing one cell from each column, followed by a rule for arranging the removed cells into a new column. There are two natural ways to remove cells: either extract the bottom cell from each column or the top cell . Likewise, there are two natural methods for placing these cells: stack them in the new column from bottom to top, following their original left-to-right order, or arrange them from top to bottom. The four actions arise from all possible combinations of these removal and placement choices, and their formal definitions are given below.
Definition 3.2. Let be
The actions , for , are defined by
Empty columns are omitted. In these formulas, the tuple to the right of is regarded as a one-column partition.
In other words, and remove the bottom cell from each column. They differ in how the removed cells are stacked: preserves the left-to-right order, while reverses it. Similarly, and remove the top cell from each column; stacks them preserving the left-to-right order, while reverses it.
As proved in Proposition 3.4, a partition with distinguishable cells is periodic under if and only if its underlying partition is periodic under . As in the classical Bulgarian solitaire case, for periodic partitions the new column is always at least as long as the remaining columns, and hence the union places it as the first column after applying each . Figure 6 and Figure 7 illustrate the orbits of under and , respectively. The other two actions are related to these by the reversal symmetry established in Proposition 3.7.
Figure 6. One orbit under the action .
Figure 7. One orbit under the action .
Connection to classical Bulgarian solitaire
Each of the four actions removes one cell from every column and forms a new column of size equal to the number of columns. Consequently, although the labels are permuted differently, the multiset of column sizes evolves exactly as in the classical game. To make this precise, define the shape map
Proposition 3.3. For every and every ,
where is the classical Bulgarian solitaire map. In other words, the following diagram commutes:
Proof. Let . Each removes one cell from every column and forms a new column from the removed cells. Thus
where zero parts are omitted and the remaining parts are arranged in weakly decreasing order.
Proposition 3.4. For each , a partition with distinguishable cells is periodic under if and only if its shape is periodic under .
Proof. First suppose that is periodic under . Then, for some ,
Using Proposition 3.3, namely , we get
Thus is periodic under .
Conversely, suppose that is periodic under . Then there exists such that . For any partition , denote the fiber over by
Each is finite; indeed because it consists of all bijections from a set of distinguishable labels to the cells of the Ferrers diagram of .
By Proposition 3.3, we have . Moreover, the map
is injective: the source shape is fixed, so the newly created column has known length . By the tie-breaking rule, it is the leftmost column of that length. Removing it leaves the nonempty remnants of the original columns in their original order. Reading its labels in the order prescribed by and reinserting them reconstructs the original configuration, including any singleton columns that disappeared. Since , the injection is a bijection.
Consequently, maps the fiber bijectively onto . Thus is a permutation of the finite set . Any permutation of a finite set has finite order, so there exists such that . Therefore is periodic under .
The following is an immediate consequence of Proposition 3.4.
Corollary 3.5. For and , let and be the least nonnegative integers such that and are periodic, respectively. Then . In particular, the maximum preperiod under each of the four actions is .
Connections between T1, T2, T3 and T4
The four maps introduced above are related pairwise through a natural reversal operation, which we now define.
Definition 3.6. For , where , define
where for .
Proposition 3.7. Let . The following diagrams commute:
i.e., and .
Proof. Reversing a column after removing its bottom cell gives the same column as removing its top cell after reversal. Hence the columns remaining from are identical in and . The new columns also agree: both contain the original bottom cells in right-to-left order when read from bottom to top. Since reversal preserves column lengths and the left-to-right order of columns, the sorting and tie-breaking rules give the same arrangement in both constructions. Thus .
The same argument applies to and , except that the original bottom cells appear in the new column in left-to-right order when read from bottom to top. Therefore .
Corollary 3.8. For every periodic , and .
Proof. By Proposition 3.7, sends the -orbit of bijectively to the -orbit of , and similarly sends the -orbit of bijectively to the -orbit of .
For each , the map commutes with every permutation of the labels, since its rules depend only on the positions of the cells. Consequently, any two labelings of the same shape have the same orbit size under . Since and have the same shape, the stated equalities follow.
Therefore, it suffices to study the orbit sizes of periodic under the actions and .
Initial analysis of the orbit sizes
In this section, we first determine the orbit size under , then focus on by developing a coloring algorithm on the Ferrers diagram. The coloring algorithm reveals the permutation induced by on the labeled cells, and we prove that the colored regions correspond exactly to the cycles of . We then compute the order of explicitly in terms of the parameters and , obtaining a bound on the orbit size under , with equality when the underlying shape has period . The section concludes with several illustrative examples.
The orbit size of pi under the action T1
Theorem 4.1. Let and be positive integers such that . Then every periodic orbit of under has size .
Proof. Suppose is a periodic partition with distinguishable cells. By Theorem 2.3, contains cells in for . We track how these cells move under . The cell in position moves to position , for . The cell in position moves to position .
These moves cyclically permute the positions of , so each cell on this diagonal first returns to its original position after exactly iterations. Since every diagonal with $1\le k\le m+1 contains at least one cell, and all labels are distinct, the orbit size is \operatorname{lcm}(1,2,\ldots,m+1).
:::
The orbit size of under the action
To better describe the movement of individual cells under the action of , we introduce coordinates. For a partition , let denote the cell in the column and row of its Ferrers diagram. The following proposition describes the new location of this cell after applying .
Proposition 4.2. Let and be positive integers such that and let be a periodic point. Then
The induced permutation
Let be periodic. Since the period of under divides , the configurations and have the same shape. Comparing the labels in corresponding positions therefore defines a permutation of .
Definition 4.3. Let be a periodic partition with distinguishable cells, and let be such that . Define by
Thus, means that after iterations of , the label occupies the position initially occupied by .
Example 4.4. For in Figure 7, we have and . Comparing the labels in corresponding positions gives .
Recall that the order of a permutation is the least positive integer such that ; equivalently, it is the least common multiple of the lengths of the cycles in its disjoint cycle decomposition.
The orbit of a partition under exhibits a dual periodicity: the Ferrers diagram returns to its original shape every iterations of , while the permutation governs the cyclic rearrangement of the labels within this fixed shape. We therefore obtain the following result.
Theorem 4.5. Let be a periodic partition under , and let be such that . Then
Moreover, if the period of the underlying shape under is , then
Proof. Because the rules of depend only on positions, successive applications of act on the labels by successive powers of . Consequently, , so the period of divides . If the underlying shape has period , every return time of is a multiple of . Moreover, if and only if is the identity. The least such positive is , proving the equality.
For the configuration in Example 4.4, the underlying shape has period and . Theorem 4.5 therefore gives , in agreement with Figure 7.
Coloring algorithm
The goal of the following subsection will be to describe the order of . We begin by introducing notation that will be used throughout.
Definition 4.6. Let be a periodic partition, and let be such that . The cells lying on the -th diagonal, denoted , are called extra cells. Their number is
where .
A row (respectively, column) containing an extra cell is called a long row (respectively, long column), while a row (respectively, column) containing no extra cell is called a short row (respectively, short column).
We show that the cycle structure of is encoded by a coloring of the cells of . In the following description of the coloring procedure, we assume . When , the diagonal contains no extra cells, and every cell remains uncolored.
Let
be the ordered list of extra cells of along the diagonal , with .
Define a map by
which returns the intersection of the column of and the row of .
For , define inductively by and
where is applied to consecutive pairs of entries in the input ordered list. That is, if
then
Note that .
We now define a coloring of the cells of . Let be a set of distinct colors. For each , we perform an initial coloring by assigning color to the cells in
After all initial colors have been assigned, extend the color of each initially colored cell straight downward in its column and straight leftward in its row, stopping before the first previously colored cell or at the boundary of the diagram. Newly colored cells do not initiate further propagation.
We also use to denote the color class consisting of all cells assigned color by this procedure.
Example 4.7. Consider the colored partition in Figure 8 with , , and . The diagonal contains the extra cells , , and .
We have
Since , we use colors. The initial coloring is given by
The coloring is then extended downward in columns and leftward in rows, as shown in Figure 8.

Figure 8. The cell coloring procedure applied to a . The cells marked with ‘X’ indicate the initially colored intersection points before color propagation.
Example 4.8. For , , and , consider the periodic partition whose extra cells are
The initial coloring assigns (yellow) to , (blue) to , and (orange) to . The resulting coloring after propagation is shown in Figure 9.

Figure 9. The cell coloring procedure applied to a . The cells marked with ‘X’ indicate the initially colored intersection points before color propagation.
We finish this subsection with a couple of observations about the resulting coloring which will be useful in the forthcoming analyses.
First, some cells of may remain uncolored by the coloring algorithm. In fact, a cell remains uncolored if and only if it lies in a short row and a short column of . Indeed, every long row and every long column contains an extra cell, from which the coloring propagates leftward or downward, while a cell lying in both a short row and a short column cannot be reached by either type of propagation.The total number of uncolored cells depends only on and as given in the following lemma.
Lemma 4.9. Let be a periodic point with where . Then the number of uncolored cells in under the coloring algorithm is exactly the triangular number
Proof. There are unoccupied positions on . Choose two such positions with column indices . The cell lies in a short column and a short row, and it belongs to the Ferrers diagram because .
Conversely, every uncolored cell lies in a short column and a short row, so it determines two unoccupied positions on with column indices and . Since is not an extra cell, , and hence .
Thus uncolored cells are in bijection with pairs of unoccupied positions on , and their number is
Secondly, the initial coloring pairs the sets and for , from which the colors propagate. Each of these sets, together with the cells colored by propagation from it, forms a chain in the weak southeast order. When is even, each color class consists of two distinct chains (see Figure 9). When is odd, each color class likewise consists of two distinct chains, except for the last color class, corresponding to , for which the two chains coincide because . This occurs in Figure 8, where and the last color class consists of a single chain.
The colored induced
We now relate the color classes of to the cycle structure of induced by the action of . The coloring not only partitions the Ferrers diagram but also encodes the cycle decomposition of : each color class corresponds to one cycle, while the uncolored labels are fixed. To make this precise, we define a permutation determined by the coloring and show that .
We define the permutation by specifying its disjoint cycle decomposition. For each color , , we construct a cycle as follows.
Using the heights from , set . To construct , first list the labels in the chain generated by in weak southeast order, starting at and ending at . When the two chains are distinct, append the labels in the chain generated by in the same order, starting at and ending at . Read the resulting list cyclically, so that the final label maps to the first. Thus, each is a cycle beginning at and ending at .
Definition 4.10. Let be a periodic partition with label set , and color its cells using the algorithm in § 4.2.2. The colored permutation is defined by
where the cycles are as constructed above. Every label of an uncolored cell is fixed.
Remark 4.11. For each cell , the following rules identify the label mapped to under .
Fixed points: If row and column are both short, then
Downward move: If row is short and column is long, then
Diagonal move: If row is long and column is long , then
Rightward move: If row is long and column is short , then
Jump move: If and row is long, then or , and
Example 4.12. Consider the labeling in Figure 10(a) of the partition colored in Figure 8, where , , and . The two yellow chains give a cycle of length 14, while the single blue chain gives a cycle of length 7:

Figure 10. The configurations in (a) and in (b), with cells colored by the coloring algorithm. Comparing labels in corresponding positions gives the induced permutation .
All uncolored labels are fixed. Figure 10(b) shows . Comparing the labels in corresponding positions in the two panels gives the same permutation, verifying that in this example.
Equality of the coloring and induced permutations
We now prove that . This requires analyzing the behavior of cells under the action and verifying that the coloring and cycle-tracing procedures capture the induced dynamics. We begin with a lemma describing the movement of individual cells.
Lemma 4.13. Let be a periodic partition, and let be a label in cell of . Under repeated applications of , the following hold:
If is in a short row and a short column, then the label remains in a short row and a short column.
If is in a short row and a long column, then the label remains in a short row and a long column until it reaches the bottom row, after which it moves to a long row and a short column.
If is in a long row and column is long (), then the label remains in a long row until it reaches the bottom row, after which it moves to a long row and a long column.
If is in a long row and column is short (), then the label remains in a long row until it reaches the bottom row, after which it moves to a short row and a long column.
Proof. We analyze each case using Proposition 4.2 and the structure of periodic partitions.
Recall that a row (respectively, column) is short if it does not contain an extra cell, equivalently if there is an empty position on the diagonal in that row (respectively, column).
(1) Suppose lies in a short row and a short column. Then there are empty positions at and .
For , the map moves the label from to , while these empty positions move to and , respectively. Thus remains in a row and column that are both short.
If , the label moves to . The corresponding empty positions ensure that this row and column remain short, so the property is preserved.
(2) Suppose lies in a short row and a long column. Then column contains an extra cell at .
For , the label moves to and remains in a short row, and the extra cell moves to , so the column remains long. If , the cell moves to . Since the extra cell moves to , the row becomes long, while the first column is short. Thus the type changes to (long row, short column).
(3) Suppose lies in a long row and column is long. Then there is an extra cell at . For , the image remains in a long row, since the extra cell structure propagates accordingly. If , the cell moves to . The extra cell at moves to , showing that this row is long, and the first column is also long. Hence the type becomes (long row, long column).
(4) Suppose lies in a long row and column is short. Then there is no extra cell at . For , the image remains in a long row. If , the cell moves to . Since no extra cell moves into , this row is short, while the first column is long. Hence the type becomes (short row, long column).
Now we are ready to state and prove the main result of this subsection.
Theorem 4.14. Let be a periodic partition. Then
Proof. We fix a cell of and follow its label under applications of . By Proposition 4.2, the label moves one step to the right and one step down until it reaches the bottom row, where it moves to the first column. We use Lemma 4.13 to determine which bottom-row rule applies and consider the five movement types in Remark 4.11.
The iteration counts in each of Table 1–Table 5 sum to . By Definition 4.3, the label originally occupying the final position maps to under .
| Initial position | Number of iterations of | New position |
Table 1. Position changes for Case 1.
| Initial position | Number of iterations of | New position |
Table 5. Position changes for Case 5.
Case 1. Uncolored cells: row and column are both short.
Both bottom-row moves use the short-row rule. Table 1 gives the trajectory, which returns the label to . Thus
Case 2. Downward move: row is short and column is long.
The first bottom-row move uses the short-row rule, while the second uses the long-row rule. As shown in Table 2, the final position is . Therefore,
| Initial position | Number of iterations of | New position |
Table 2. Position changes for Case 2.
Case 3. Diagonal move: row and column are both long, with .
Both bottom-row moves use the long-row rule. Table 3 gives the final position , so
| Initial position | Number of iterations of | New position |
Table 3. Position changes for Case 3.
Case 4. Rightward move: row is long and column is short, with .
The first bottom-row move uses the long-row rule, while the second uses the short-row rule. Table 4 therefore gives the final position , yielding
| Initial position | Number of iterations of | New position |
Table 4. Position changes for Case 4.
Case 5. Jump move: and or .
Since row is long, the bottom-row move uses the long-row rule. Table 5 gives the final position . Hence
These cases cover every cell of . Thus the two permutations have the same preimage for every label, and hence .
The order of
Having established that , we now determine the order of this permutation. Since the order of a permutation is the least common multiple of its cycle lengths, this reduces to analyzing the cycle structure of . We do this by studying the sizes of the color classes obtained with the coloring algorithm.
Theorem 4.15. Let , and let be the unique positive integer such that
Set , and let be periodic. Then
Proof. Let . We consider three cases.
Case 1: . Then is the full triangular partition of size . In this case, , and hence also , is the identity permutation. Therefore,
Case 2: . There is exactly one extra cell, say at location in the -st diagonal. The coloring algorithm colors this cell together with cells to its left and cells below. The total number of colored cells is
These labels form a single cycle, so .
Case 3: . Let the extra cells on be
so and hence . For set
Fix . The color consists of the two components and (coinciding if is odd and ). Write
Leftward propagation in row colors cells (with ), while downward propagation in column colors cells (with ). Thus, the total number of cells colored by in this component, starting from the cells in , is
Suppose first that the two chains of are distinct. Applying the preceding calculation to the two chains of ,
Thus every color class consisting of two distinct chains has cells. If is odd and , the two chains coincide, so the final color class has cells. If is even, every color class has cells. Since , at least one cycle has length , and every other cycle length divides this number. Therefore,
The equality now gives the stated formula.
:::
Corollary 4.16. Let be a periodic point with and . Then the orbit size of under divides
Moreover, if the period of the underlying shape under is , then “divides” may be replaced by “equals”.
Proof. The claim follows from substituting the values of from Theorem 4.15 into Theorem 4.5.
The following examples show that the bound may or may not be attained when the underlying shape has period less than .
Example 4.17 (, , ). There are four periodic orbits in under , corresponding to necklaces of length 6 with 3 black beads. Figure 11 shows a labeled representative of each underlying orbit, together with its shape period .

Figure 11. Labeled configurations whose underlying shapes represent the four distinct periodic orbits in under . Extra cells (the cells on diag[6]) are indicated in gray. The underlying shapes in (a)–(c) have period under , while the shape in (d) has period .
By Corollary 4.16, since , the first three orbits under the action of have size , while the fourth orbit has size dividing 60. However, direct computation shows that the fourth orbit also has size 60.
Example 4.18 (, , ). There are two periodic orbits in under , corresponding to necklaces of length 4 with 2 black beads. Figure 12 shows a labeled representative of each underlying orbit, together with its shape period .

Figure 12. Labeled configurations whose underlying shapes represent the two distinct periodic orbits in under . Extra cells on diag[4] are shaded gray and labeled in (a) and in (b). The underlying shapes in (a) and (b) have periods and under , respectively.
Here . By Corollary 4.16, since for orbit (a), its size under equals ; for orbit (b) with , the orbit size divides 28, and direct computation shows it is 14.
These examples illustrate the bound of Corollary 4.16: the orbit size under always divides , and sometimes attains it. In the next section, we determine the exact orbit sizes and prove that the upper bound from Corollary 4.16 is achieved in most cases, even when , and when it is not, the orbit size is exactly half of that bound.
Exact sizes of orbits under
In this section, we determine the exact orbit sizes of periodic partitions under and characterize when the bound from Corollary 4.16 is attained. As the preceding examples show, equality can hold even when the period of the underlying shape is less than . We prove that, for , the bound is attained except when and , in which case the orbit size is exactly half of the bound. To establish these results, we analyze the permutation induced by one full period of the underlying shape, treating the colored and uncolored labels separately.
We begin by introducing notation for the colored and uncolored labels.
Definition 5.1. Let be a periodic partition whose cells are colored using the algorithm in § 4.2.2. Define:
as the set of labels of colored cells of ,
as the set of labels of uncolored cells of ,
for each color (), as the set of labels of cells colored with .
Note that
We now introduce the permutation of all labels induced by one full period of the underlying shape.
Definition 5.2. Let be a periodic partition. The permutation is defined by
where is the period of the underlying unlabeled partition under .
Lemma 5.3. Let be a periodic point with , . Let be the period of the underlying unlabeled partition under and set . For each color class () the following hold:
(a) The set is invariant under , i.e.,
(b) The restriction is a permutation of and satisfies
where .
(c) The permutation is a single cycle on .
Proof. (a) We first show that a label retains its color after one application of , when the resulting configuration is colored by the algorithm.
Let be a colored cell, and let
where are the column indices of the extra cells. The color of is . Indeed, at a cell of the indicated interval contains exactly extra-cell column indices, and propagation along the corresponding chain does not change this number.
If , Proposition 4.2 sends to . The interval and the extra-cell positions shift together, so is unchanged.
Suppose . If the bottom row is long, the label moves to , and the number of extra-cell column indices in the new interval is . If the bottom row is short, then column must be long because the cell is colored. The label moves to , and the new count is again . In both cases the resulting cell is colored, and
Thus the label retains its color.
Iterating this observation times, and using the fact that has the same shape as , shows that
(b) Therefore, the restriction
is a permutation of . Since , by Definitions 4.3 and 5.2,
By Theorem 4.14, we also have . Restricting this identity to gives
(c) By construction, each is a single cycle. Since , a power of is a single cycle. Hence itself must be a single cycle on .
This completes the proof.
To combine the contributions of the colored and uncolored labels to the orbit size, we will also need the following coprimality condition.
Lemma 5.4. Let be a periodic partition with and . Let denote the period of the underlying unlabeled partition under , so that , and set . Then
Proof. We consider three cases based on the value of .
Case . Then, by Theorem 4.15, , so .
Case . Then, by Theorem 4.15, . Since there is a single extra cell, the underlying unlabeled partition has full period , hence . Thus .
Case . Then, by Theorem 4.15, we have . The binary word recording the occupied positions on consists of repetitions of a block of length . Therefore its number of occupied positions is divisible by . Write for some integer . Since , we compute
Hence , which implies .
We are now ready to state the main theorem that gives the exact orbit sizes under .
Theorem 5.5. Let be a periodic point under the action , with and , . Let be the period of the underlying unlabeled partition under . Then, the orbit size of under is
Proof. Let and , and let be the permutation from Definition 5.2. Since , Definitions 4.3 and 5.2 give .
By Lemma 5.3, preserves each colored label set . Consequently, it preserves their union and its complement . Define the restrictions
and let and . Since these restrictions act on disjoint label sets,
Moreover, fixes every uncolored label, so restricting to gives . Hence .
Every return time of under is a multiple of , since its underlying shape has period . Because the shape repeats every steps and the rules of do not depend on the labels, if and only if . Therefore,
By Lemma 5.3, each restriction is a single cycle on the same label set as , so these cycles have the same length. Since fixes all uncolored labels, taking the least common multiple of the colored cycle lengths gives . This also holds when , since both permutations are identities.
Next, we determine . Suppose first that there is no more than one uncolored cell. Then must be the identity on at most one label, hence .
Suppose now that there are at least three uncolored cells.
Suppose now that there at least two uncolored cells. Let . Let be the set of column indices of the unoccupied positions on . Then .
The uncolored labels are in bijection with the two-element subsets of via
Indeed, an uncolored cell lies in a short column and a short row, and . Conversely, for in , the cell is uncolored.
By Proposition 4.2, if , the cell moves to , so its associated pair becomes . If , the bottom row must be short because the cell is uncolored. Hence the second branch of Proposition 4.2 applies, sending to , whose associated pair is . In both cases, the associated unordered pair is obtained by adding modulo to each of its indices, with residues represented by . Since the shape returns after steps, addition of modulo permutes . Its induced action on the two-element subsets of is the inverse of .
Suppose . Then addition of modulo fixes every two-element subset of . For any , choose distinct . Since this translation fixes both and , it fixes their intersection . Thus , which implies . Together with , this proves that .
We have shown that , while if and otherwise. By Lemma 5.4, . Consequently,
Since , this proves the theorem.
Combining Theorem 5.5 with the explicit formula for from Theorem 4.15, we obtain the following closed-form expressions for orbit sizes when .
Theorem 5.6. Let be a periodic point under the action , where with and . Let be the period of the underlying unlabeled partition under . Then, the orbit size of
under is
The second value occurs exactly when , equivalently when the two white beads in the associated necklace are opposite each other. This is possible only when is odd.
Proof. For , we have , so the stated orbit sizes follow directly from Theorems 4.15 and 5.5.
Suppose . These theorems give . The associated necklace has length and exactly two white beads. Any nonidentity rotation preserving its bead coloring must interchange the two white beads and is therefore a half-turn. Hence unless the white beads are opposite each other, in which case . The latter is possible only when is odd, giving the two stated orbit sizes.
Finally, if , the associated necklace has exactly one white bead and therefore has full period . Since , Theorem 5.5 gives .
Conjugation symmetries
In Section 3, we established how the reversal operation interacts with our four actions , : it conjugates to and to . Conjugation of Ferrers diagrams is another standard operation on partitions with distinguishable cells, so it is natural to ask how it interacts with these actions. Here we establish such relations for and on periodic partitions and use reversal to obtain corresponding relations for and .
Definition 6.1. Let . The conjugate of , denoted , is the partition obtained by reflecting the Ferrers diagram of across its main diagonal. Equivalently,
for every cell in the Ferrers diagram of . Thus, the label occupying row and column in occupies row and column in . Note that conjugation is an involution; that is, for every .
Since conjugation preserves each diagonal setwise, Theorem 2.3 and Proposition 3.4 imply that it preserves periodicity. We examine how the actions and interact with conjugation.
Proposition 6.2. For every periodic , the following diagrams commute:
Equivalently,
:::`
Proof. Let be periodic. Under conjugation, the label moves to position in .
The action . Under , the label moves to if , and to if . After conjugation, these positions become
Applying once more, the entry at moves to , whereas the cell at moves to . Thus in either case the final position is , exactly the position of in . Therefore
The action . Let denote the number of columns of , equivalently the length of its bottom row. Under , an entry with again moves to , while a bottom row entry at is placed in the new first column at position . After conjugation, these become
Since is periodic, the newly formed column of has length and is at least as long as every remaining column. Thus has exactly rows, so the bottom row of has length . Hence applying again sends the entry at to , while the entry at moves to . Thus the final position is again , which is precisely the position of in . Therefore
Since this holds for every entry of , the result follows.
On the set of periodic partitions, Proposition 6.2 can equivalently be written as
Thus conjugation sends each periodic orbit to a periodic orbit of the same size and reverses the direction of the action.
Remark 6.3. Combining Propositions 3.7 and 6.2 gives corresponding identities for and . On the set of periodic partitions,
Indeed, these identities follow by composing the identities in Proposition 6.2 on both sides with and using Proposition 3.7. Thus, the involution reverses the direction of the action on periodic orbits of and , just as does for and .
Remark 6.4. Proposition 6.2 does not hold for arbitrary (non-periodic) partitions. For example, let and consider the one-column partition (where the cells are listed from bottom to top). Then ; in particular has three columns of size 1. On the other hand,
and finally
Thus the identity for fails for this nonperiodic partition. Similarly,
Consequently, the periodicity assumption in Proposition 6.2 cannot be omitted.
References
References
- [1]Ethan Akin and Morton Davis. Bulgarian solitaire. Amer. Math. Monthly, 92(4):237–250, 1985.DOI
- [2]Borislav Bojanov. Problem solution 4. Obuchenieto po matematika, 24(5):59–60, 1981.
- [3]Jørgen Brandt. Cycles of partitions. Proc. Amer. Math. Soc., 85(3):483–486, 1982.DOI
- [4]C. Cannings and J. Haigh. Montreal solitaire. J. Combin. Theory Ser. A, 60(1):50–66, 1992.DOI
- [5]Robson da Silva, Brian Hopkins, and James A. Sellers. Garden of Eden states in Austrian solitaire. European J. Combin., 83:103023, 8, 2020.DOI
- [6]Henrik Eriksson. Bulgarisk patiens. Elementa, 64(4):186–188, 1981.
- [7]Henrik Eriksson and Markus Jonsson. Level sizes of the Bulgarian solitaire game tree. Fibonacci Quart., 55(3):243–251, 2017.
- [8]Kimmo Eriksson, Markus Jonsson, and Jonas Sjöstrand. An exponential limit shape of random q-proportion Bulgarian solitaire. Integers, 18:Paper No. A58, 22, 2018.arxiv.org/abs/1703.07102
- [9]Kimmo Eriksson, Markus Jonsson, and Jonas Sjöstrand. Limit shapes of stable and recurrent configurations of a generalized Bulgarian solitaire. Online J. Anal. Comb., (15):Paper No. 10, 19, 2020.DOI
- [10]Gwihen Etienne. Tableaux de Young et solitaire bulgare. J. Combin. Theory Ser. A, 58(2):181–197, 1991.
- [11]Martin Gardner. Bulgarian solitaire and other seemingly endless tasks. In The Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications, pages 27–43. Springer, 1997.DOI
- [12]Jerrold R. Griggs and Chih-Chang Ho. The cycling of partitions and compositions under repeated shifts. Adv. in Appl. Math., 21(2):205–227, 1998.DOI
- [13]A. J. Harris and Son Nguyen. Bulgarian solitaire: a new representation for depth generating functions. Australas. J. Combin., 93:224–273, 2025.
- [14]Therese A. Hart, Gabriel Khan, and Mizan R. Khan. Revisiting Toom’s proof of Bulgarian solitaire. Ann. Sci. Math. Québec, 36(2):477–486, 2012.arxiv.org/abs/1101.1546
- [15]Brian Hopkins. Column-to-row operations on partitions: the envelopes. In Combinatorial number theory, pages 65–76. Walter de Gruyter, Berlin, 2009.DOI
- [16]Brian Hopkins. 30 years of Bulgarian solitaire. College Math. J., 43(2):135–140, 2012.
- [17]Brian Hopkins. Henrik Eriksson’s Bulgarian solitaire variant. Integers, 24A:Paper No. A9, 14, 2024.
- [18]Brian Hopkins and Michael A. Jones. Shift-induced dynamical systems on partitions and compositions. Electron. J. Combin., 13(1):Research Paper 80, 19, 2006.
- [19]Brian Hopkins and James A. Sellers. Exact enumeration of Garden of Eden partitions. In Combinatorial number theory, pages 299–303. de Gruyter, Berlin, 2007.
- [20]Kiyoshi Igusa. Solution of the Bulgarian solitaire conjecture. Math. Mag., 58(5):259–271, 1985.DOI
- [21]Aaron Meyerowitz, Stephen J. Curran, Stephen C. Locke, and Richard M. Low. Floridian solitaire: A new variant of Bulgarian solitaire. arXiv:2608.08313, 2026.arxiv.org/abs/2608.08313
- [22]Jeffrey S. Olson. Variants of Bulgarian solitaire. Integers, 16:Paper No. A8, 11, 2016.DOI
- [23]Nhung Pham. Limiting behavior in growth of Bulgarian solitaire orbits. Integers, 23:Paper No. A58, 25, 2023.arxiv.org/abs/2208.14496
- [24]Serguei Popov. Random Bulgarian solitaire. Random Structures Algorithms, 27(3):310–330, 2005.DOI
- [25]A. L. Toom. Problem solution M655. Kvant, 12(7):28–30, 1981.
- [26]Yeong Nan Yeh. A remarkable endofunction involving compositions. Stud. Appl. Math., 95(4):419–432, 1995.DOI


