betaFeedback

WorksMathematics

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 T1,T2,T3,T4T_1,T_2,T_3,T_4 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 T2T_2, 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 nn 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 (3,1,1)(3,1,1) to the configuration (3,2)(3,2). 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 nn. Thus, Bulgarian solitaire defines a discrete dynamical system on the finite set PnP_n of partitions of nn, and every sequence of iterates is eventually periodic.

One move of Bulgarian solitaire from (3, 1, 1) to (3, 2)

Figure 1. One move of Bulgarian solitaire from (3,1,1)(3,1,1) to (3,2)(3,2). 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, n=k(k+1)/2n=k(k+1)/2, every initial configuration eventually settles into the partition (k,k−1,…,1)(k,k-1,\ldots,1). This observation inspired several mathematicians to seek a proof (see, e.g., [2, 6]) and to investigate the behavior for general nn. 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 Pn∗\mathcal{P}_n^*, and define four natural actions T1,T2,T3,T4T_1,T_2,T_3,T_4. 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 T2T_2, 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 T1T_1 and T2T_2. Section 4 determines the periodic orbit sizes under T1T_1 and develops the coloring algorithm for T2T_2. Section 5 completes the analysis by determining the exact periodic orbit sizes under T2T_2. 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 nn is a finite sequence π=(π1,π2,…,πk)\pi=(\pi_1,\pi_2,\ldots,\pi_k) of positive integers such that π1≥π2≥⋯≥πk\pi_1\ge\pi_2\ge\cdots\ge\pi_k and ∑i=1kπi=n\sum_{i=1}^{k}\pi_i=n. The integers πi\pi_i are called the parts of the partition, and k=ℓ(π)k=\ell(\pi) is called the length of the partition. The set of all partitions of nn is denoted by Pn\mathcal{P}_n.

A partition π=(π1,π2,…,πk)\pi=(\pi_1,\pi_2,\ldots,\pi_k) of nn is traditionally represented by its Ferrers diagram: a left-aligned array of cells in which the ii-th row from the top contains πi\pi_i cells. In our pictorial representation, we rotate this diagram by 90∘90^\circ 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 (1,1)(1,1).

Rotated Ferrers diagram of $\pi=(3,2)\in\mathcal{P}_5$

Figure 2. Rotated Ferrers diagram of π=(3,2)∈P5\pi=(3,2)\in\mathcal{P}_5.

For two partitions μ\mu and π\pi, we define their union μ∪π\mu\cup\pi to be the partition obtained by combining the parts of μ\mu with those of π\pi and arranging the resulting entries in weakly decreasing order. For example, (3,2)∪(5,4,2,1)=(5,4,3,2,2,1)(3,2)\cup(5,4,2,1)=(5,4,3,2,2,1).

Classical Bulgarian solitaire

Bulgarian solitaire is a discrete dynamical system defined on Pn\mathcal{P}_n. 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 T:Pn→PnT:\mathcal{P}_n\to\mathcal{P}_n defined by

T(π)=(π1−1,π2−1,…,πℓ(π)−1)∪(ℓ(π)),T(\pi)=(\pi_1-1,\pi_2-1,\ldots,\pi_{\ell(\pi)}-1)\cup(\ell(\pi)),

where parts of size zero are omitted. The set

OT(π)={π,T(π),T2(π),…}O_T(\pi)=\{\pi,T(\pi),T^2(\pi),\ldots\}

is called the orbit of π\pi under TT. Since Pn\mathcal{P}_n is finite, the sequence of iterates is eventually periodic. A partition π\pi is said to be periodic under the transformation TT if there exists a positive integer ℓ\ell such that

Tℓ(π)=π.T^\ell(\pi)=\pi.

The smallest such integer ℓ\ell is called the period of π\pi under TT.

Definition 2.2. For a fixed positive integer kk, the kk-th upper diagonal, denoted by diag⁡[k]\operatorname{diag}[k], is the set of positions

diag⁡[k]={(1,k),(2,k−1),…,(k,1)}.\operatorname{diag}[k]=\{(1,k),(2,k-1),\ldots,(k,1)\}.

For a positive integer nn, let mm be the unique integer such that the mm-th triangular number Δm=m(m+1)2\Delta_m=\frac{m(m+1)}{2} satisfies

Δm≤n<Δm+1.\Delta_m\le n<\Delta_{m+1}.

Define m′=n−Δmm'=n-\Delta_m. The periodic points of TT were characterized by Toom as follows.

Theorem 2.3 [14, 25]. Let n≥1n\ge1, let mm be the unique integer such that Δm≤n<Δm+1\Delta_m\le n<\Delta_{m+1} and let m′=n−Δmm'=n-\Delta_m. Let π\pi be a partition of nn, and let FF denote its Ferrers diagram. Then π\pi is a periodic point of TT if and only if

∣F∩diag⁡[k]∣={k,1≤k≤m,m′,k=m+1,0,k>m+1.|F\cap\operatorname{diag}[k]|= \begin{cases} k, & 1\le k\le m,\\ m', & k=m+1,\\ 0, & k>m+1. \end{cases}

In the special case where n=Δmn=\Delta_m, Pn\mathcal{P}_n contains only one periodic point, namely,

(m,m−1,m−2,…,2,1).(m,m-1,m-2,\ldots,2,1).

When nn is not triangular, the period ℓ\ell of a periodic partition divides m+1m+1. 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 diag⁡[m+1]\operatorname{diag}[m+1].

The number of distinct periodic orbits of Pn\mathcal{P}_n under the action of TT is equal to the number of necklaces consisting of m′m' black beads and m+1−m′m+1-m' white beads, where the symmetry group is the cyclic group of order m+1m+1. Their number is given by the following elegant formula due to Brandt.

Theorem 2.4 [3]. Given n≥1n\ge1, write nn uniquely as Δm+m′\Delta_m+m' for some integer m′m' with 0≤m′≤m0\le m'\le m. The number of distinct periodic orbits in Pn\mathcal{P}_n under TT is

1m+1∑d∣gcd⁡(m+1,m′)ϕ(d)(m+1dm′d),\frac{1}{m+1}\sum_{d\mid\gcd(m+1,m')}\phi(d)\binom{\frac{m+1}{d}}{\frac{m'}{d}},

where ϕ\phi is Euler’s totient function.

Example 2.5. Figure 3 illustrates the orbit of π=(3,1,1)\pi=(3,1,1) under TT. By Theorem 2.3, π\pi is a periodic point of TT. The action of TT corresponds to cyclically shifting the cells in diag⁡[m+1]\operatorname{diag}[m+1] down the diagonal.

Orbit of the partition $(3,1,1)$ under $T$

Figure 3. Orbit of π=(3,1,1)\pi=(3,1,1) under TT.

In this case, n=5=Δ2+2n = 5 = \Delta_{2} + 2, so m=2m = 2 and m′=2m' = 2. The period is ℓ=3\ell= 3, which divides m+1m + 1. This orbit corresponds to the unique necklace with m′=2m' = 2 black beads and m+1−m′=1m + 1 - m' = 1 white bead, shown in Figure 4.

A necklace with 2 black beads and 1 white bead

Figure 4. A necklace with 2 black beads and 1 white bead.

The depth D(n)D(n) of classical Bulgarian solitaire is the maximum, over π∈Pn\pi\in\mathcal{P}_n, of the minimum number of applications of TT needed to reach a periodic partition. Igusa [20] and Etienne [10] proved that D(Δm)=m(m−1)D(\Delta_m) = m(m - 1) for m≥1m \ge1. Griggs and Ho [12] gave an upper bound for non-triangular numbers: D(Δm+m′)≤m2−2D(\Delta_m + m') \le m^2 - 2 for m≥3m \ge3 and 1≤m′≤m1 \le m' \le m, with equality when m′=mm' = m. 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 nn labels. No order conditions are imposed on the labels. We write each part as πi=(πi1,πi2,…,πini)\pi_i = (\pi_{i1}, \pi_{i2}, \ldots, \pi_{in_i}), where nin_i is the length of the ii-th column and the entries represent distinct cells. We depict each πi\pi_i as a column in the Ferrers diagram, and πij\pi_{ij} denotes the labeled cell in position (i,j)(i,j), that is, the cell in the ii-th column and jj-th row.

We denote the set of all partitions of nn with distinguishable cells by Pn⋆\mathcal{P}_n^\star. The set of all labeled cells of a partition's Ferrers diagram is denoted by Lπ\mathcal{L}_{\pi}.

Example 3.1. Consider the partition with distinguishable cells π⋆=((a,b,c),(d),(e))∈P5⋆\pi^\star= ((a,b,c),(d),(e)) \in\mathcal{P}_5^\star. It corresponds to the Ferrers diagram shown in Figure 5.

Figure 5. Ferrers diagram of π⋆=((a,b,c),(d),(e))\pi^\star= ((a,b,c),(d),(e)).

Moreover, we have Lπ⋆={a,b,c,d,e}\mathcal{L}_{\pi^\star} = \{a,b,c,d,e\}.

For two partitions with distinguishable cells μ⋆\mu^\star and π⋆\pi^\star with disjoint label sets, define their union μ⋆∪π⋆\mu^\star\cup\pi^\star 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 π⋆\pi^\star are placed before those from μ⋆\mu^\star. For example,

((a,b,c),(d),(e))∪((A,B,C),(D,E),(F))=((A,B,C),(a,b,c),(D,E),(F),(d),(e)).((a,b,c),(d),(e)) \cup((A,B,C),(D,E),(F)) = ((A,B,C),(a,b,c),(D,E),(F),(d),(e)).

We now introduce four actions, TiT_i for i=1,2,3,4i=1,2,3,4, acting on Pn⋆P_n^\star. 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 πi1\pi_{i1} from each column or the top cell πini\pi_{in_i}. 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 π∈Pn⋆\pi\in P_n^\star be

π=((π11,π12,…,π1n1),(π21,π22,…,π2n2),…,(πk1,πk2,…,πknk)).\pi=((\pi_{11},\pi_{12},\ldots,\pi_{1n_1}),(\pi_{21},\pi_{22},\ldots,\pi_{2n_2}),\ldots,(\pi_{k1},\pi_{k2},\ldots,\pi_{kn_k})).

The actions Ti:Pn⋆→Pn⋆T_i:P_n^\star\to P_n^\star, for i=1,2,3,4i=1,2,3,4, are defined by

T1(π)=((π12,…,π1n1),(π22,…,π2n2),…,(πk2,…,πknk))∪(π11,π21,…,πk1),T2(π)=((π12,…,π1n1),(π22,…,π2n2),…,(πk2,…,πknk))∪(πk1,πk−1,1,…,π11),T3(π)=((π11,…,π1,n1−1),(π21,…,π2,n2−1),…,(πk1,…,πk,nk−1))∪(π1n1,π2n2,…,πknk),T4(π)=((π11,…,π1,n1−1),(π21,…,π2,n2−1),…,(πk1,…,πk,nk−1))∪(πknk,πk−1,nk−1,…,π1n1).\begin{aligned} T_1(\pi)&=((\pi_{12},\ldots,\pi_{1n_1}),(\pi_{22},\ldots,\pi_{2n_2}),\ldots,(\pi_{k2},\ldots,\pi_{kn_k}))\cup(\pi_{11},\pi_{21},\ldots,\pi_{k1}),\\ T_2(\pi)&=((\pi_{12},\ldots,\pi_{1n_1}),(\pi_{22},\ldots,\pi_{2n_2}),\ldots,(\pi_{k2},\ldots,\pi_{kn_k}))\cup(\pi_{k1},\pi_{k-1,1},\ldots,\pi_{11}),\\ T_3(\pi)&=((\pi_{11},\ldots,\pi_{1,n_1-1}),(\pi_{21},\ldots,\pi_{2,n_2-1}),\ldots,(\pi_{k1},\ldots,\pi_{k,n_k-1}))\cup(\pi_{1n_1},\pi_{2n_2},\ldots,\pi_{kn_k}),\\ T_4(\pi)&=((\pi_{11},\ldots,\pi_{1,n_1-1}),(\pi_{21},\ldots,\pi_{2,n_2-1}),\ldots,(\pi_{k1},\ldots,\pi_{k,n_k-1}))\cup(\pi_{kn_k},\pi_{k-1,n_k-1},\ldots,\pi_{1n_1}). \end{aligned}

Empty columns are omitted. In these formulas, the tuple to the right of ∪\cup is regarded as a one-column partition.

In other words, T1T_1 and T2T_2 remove the bottom cell πi1\pi_{i1} from each column. They differ in how the removed cells are stacked: T1T_1 preserves the left-to-right order, while T2T_2 reverses it. Similarly, T3T_3 and T4T_4 remove the top cell πini\pi_{in_i} from each column; T3T_3 stacks them preserving the left-to-right order, while T4T_4 reverses it.

As proved in Proposition 3.4, a partition with distinguishable cells is periodic under TiT_i if and only if its underlying partition is periodic under TT. 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 TiT_i. Figure 6 and Figure 7 illustrate the orbits of π=((a,b,c),(d),(e))\pi=((a,b,c),(d),(e)) under T1T_1 and T2T_2, 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 T1T_1.

Figure 7. One orbit under the action T2T_2.

Connection to classical Bulgarian solitaire

Each of the four actions T1,T2,T3,T4T_1,T_2,T_3,T_4 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

S:Pn⋆⟶Pn,S(π⋆)=nonincreasing list of column lengths of π⋆∈Pn⋆.S : \mathcal{P}^{\star}_n \longrightarrow\mathcal{P}_n,\qquad S(\pi^\star) = \text{nonincreasing list of column lengths of }\pi^\star\in\mathcal{P}^{\star}_n.

Proposition 3.3. For every π⋆∈Pn⋆\pi^\star\in\mathcal{P}^{\star}_n and every i∈{1,2,3,4}i \in\{1,2,3,4\},

S(Ti(π⋆))=T(S(π⋆)),S(T_i(\pi^\star)) = T(S(\pi^\star)),

where T:Pn→PnT : \mathcal{P}_n \to\mathcal{P}_n is the classical Bulgarian solitaire map. In other words, the following diagram commutes:

Pn⋆→TiPn⋆S↓↓SPn→TPn\begin{CD} \mathcal{P}^{\star}_n @>{T_i}>> \mathcal{P}^{\star}_n \\ @V{S}VV @VV{S}V \\ \mathcal{P}_n @>{T}>> \mathcal{P}_n \end{CD}

Proof. Let S(π⋆)=(a1,…,ak)S(\pi^\star)=(a_1,\ldots,a_k). Each TiT_i removes one cell from every column and forms a new column from the kk removed cells. Thus

S(Ti(π⋆))=(a1−1,…,ak−1)∪(k)=T(S(π⋆)),S(T_i(\pi^\star))=(a_1-1,\ldots,a_k-1)\cup(k)=T(S(\pi^\star)),

where zero parts are omitted and the remaining parts are arranged in weakly decreasing order.

Proposition 3.4. For each i∈{1,2,3,4}i \in\{1,2,3,4\}, a partition with distinguishable cells π⋆\pi^\star is periodic under TiT_i if and only if its shape S(π⋆)S(\pi^\star) is periodic under TT.

Proof. (⇒)(\Rightarrow) First suppose that π⋆\pi^\star is periodic under TiT_i. Then, for some ℓ>0\ell>0,

Tiℓ(π⋆)=π⋆.T_i^\ell(\pi^\star)=\pi^\star.

Using Proposition 3.3, namely S∘Ti=T∘SS\circ T_i=T\circ S, we get

Tℓ(S(π⋆))=S(Tiℓ(π⋆))=S(π⋆).T^\ell(S(\pi^\star))=S(T_i^\ell(\pi^\star))=S(\pi^\star).

Thus S(π⋆)S(\pi^\star) is periodic under TT.

(⇐)(\Leftarrow) Conversely, suppose that λ=S(π⋆)\lambda=S(\pi^\star) is periodic under TT. Then there exists p>0p>0 such that Tp(λ)=λT^p(\lambda)=\lambda. For any partition ν∈Pn\nu\in\mathcal{P}_n, denote the fiber over ν\nu by

Fν={μ⋆∈Pn⋆∣S(μ⋆)=ν}.F_\nu=\{\mu^\star\in\mathcal{P}^{\star}_n\mid S(\mu^\star)=\nu\}.

Each FνF_\nu is finite; indeed ∣Fν∣=n!|F_\nu|=n! because it consists of all bijections from a set of nn distinguishable labels to the cells of the Ferrers diagram of ν\nu.

By Proposition 3.3, we have Ti(Fν)⊆FT(ν)T_i(F_\nu)\subseteq F_{T(\nu)}. Moreover, the map

Ti:Fν⟶FT(ν)T_i:F_\nu\longrightarrow F_{T(\nu)}

is injective: the source shape ν\nu is fixed, so the newly created column has known length ℓ(ν)\ell(\nu). 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 TiT_i and reinserting them reconstructs the original configuration, including any singleton columns that disappeared. Since ∣Fν∣=∣FT(ν)∣=n!|F_\nu|=|F_{T(\nu)}|=n!, the injection is a bijection.

Consequently, TipT_i^p maps the fiber FλF_\lambda bijectively onto FTp(λ)=FλF_{T^p(\lambda)}=F_\lambda. Thus TipT_i^p is a permutation of the finite set FλF_\lambda. Any permutation of a finite set has finite order, so there exists m≥1m\geq1 such that (Tip)m(π⋆)=π⋆(T_i^p)^m(\pi^\star)=\pi^\star. Therefore π⋆\pi^\star is periodic under TiT_i.

The following is an immediate consequence of Proposition 3.4.

Corollary 3.5. For π⋆∈Pn⋆\pi^\star\in\mathcal{P}^{\star}_n and i∈{1,2,3,4}i\in\{1,2,3,4\}, let kik_i and kk be the least nonnegative integers such that Tiki(π⋆)T_i^{k_i}(\pi^\star) and Tk(S(π⋆))T^k(S(\pi^\star)) are periodic, respectively. Then ki=kk_i=k. In particular, the maximum preperiod under each of the four actions is D(n)D(n).

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 π=(π1,…,πk)∈Pn⋆\pi=(\pi_1,\ldots,\pi_k)\in\mathcal{P}_n^\star, where πi=(πi1,…,πini)\pi_i=(\pi_{i1},\ldots,\pi_{in_i}), define

rev⁡:Pn⋆→Pn⋆,rev⁡(π)=(rev⁡(π1),…,rev⁡(πk)).\operatorname{rev}:\mathcal{P}_n^\star\to\mathcal{P}_n^\star,\qquad\operatorname{rev}(\pi)=\left(\operatorname{rev}(\pi_1),\ldots,\operatorname{rev}(\pi_k)\right).

where rev⁡(πi)=(πini,πini−1,…,πi1)\operatorname{rev}(\pi_i)=(\pi_{in_i},\pi_{in_i-1},\ldots,\pi_{i1}) for 1≤i≤k1\le i\le k.

Proposition 3.7. Let π∈Pn⋆\pi\in\mathcal{P}_n^\star. The following diagrams commute:

π→T1T1(π)↓rev⁡↓rev⁡rev⁡(π)→T4T4(rev⁡(π))π→T2T2(π)↓rev⁡↓rev⁡rev⁡(π)→T3T3(rev⁡(π))\begin{array}{ccc} \pi& \xrightarrow{T_1} & T_1(\pi) \\ \downarrow\scriptstyle{\operatorname{rev}} & & \downarrow\scriptstyle{\operatorname{rev}} \\ \operatorname{rev}(\pi) & \xrightarrow{T_4} & T_4(\operatorname{rev}(\pi)) \end{array} \qquad \begin{array}{ccc} \pi& \xrightarrow{T_2} & T_2(\pi) \\ \downarrow\scriptstyle{\operatorname{rev}} & & \downarrow\scriptstyle{\operatorname{rev}} \\ \operatorname{rev}(\pi) & \xrightarrow{T_3} & T_3(\operatorname{rev}(\pi)) \end{array}

i.e., rev⁡∘T1=T4∘rev⁡\operatorname{rev}\circ T_1=T_4\circ\operatorname{rev} and rev⁡∘T2=T3∘rev⁡\operatorname{rev}\circ T_2=T_3\circ\operatorname{rev}.

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 π\pi are identical in rev⁡(T1(π))\operatorname{rev}(T_1(\pi)) and T4(rev⁡(π))T_4(\operatorname{rev}(\pi)). 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 rev⁡∘T1=T4∘rev⁡\operatorname{rev}\circ T_1=T_4\circ\operatorname{rev}.

The same argument applies to T2T_2 and T3T_3, except that the original bottom cells appear in the new column in left-to-right order when read from bottom to top. Therefore rev⁡∘T2=T3∘rev⁡\operatorname{rev}\circ T_2=T_3\circ\operatorname{rev}.

Corollary 3.8. For every periodic π∈Pn⋆\pi\in\mathcal{P}_n^\star, ∣OT1(π)∣=∣OT4(π)∣\lvert O_{T_1}(\pi)\rvert=\lvert O_{T_4}(\pi)\rvert and ∣OT2(π)∣=∣OT3(π)∣\lvert O_{T_2}(\pi)\rvert=\lvert O_{T_3}(\pi)\rvert.

Proof. By Proposition 3.7, rev⁡\operatorname{rev} sends the T1T_1-orbit of π\pi bijectively to the T4T_4-orbit of rev⁡(π)\operatorname{rev}(\pi), and similarly sends the T2T_2-orbit of π\pi bijectively to the T3T_3-orbit of rev⁡(π)\operatorname{rev}(\pi).

For each ii, the map TiT_i 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 TiT_i. Since π\pi and rev⁡(π)\operatorname{rev}(\pi) have the same shape, the stated equalities follow.

Therefore, it suffices to study the orbit sizes of periodic π∈Pn⋆\pi\in\mathcal{P}_n^\star under the actions T1T_1 and T2T_2.

Initial analysis of the orbit sizes

In this section, we first determine the orbit size under T1T_1, then focus on T2T_2 by developing a coloring algorithm on the Ferrers diagram. The coloring algorithm reveals the permutation σπ\sigma_\pi induced by T2m+1T_2^{m+1} on the labeled cells, and we prove that the colored regions correspond exactly to the cycles of σπ\sigma_\pi. We then compute the order of σπ\sigma_\pi explicitly in terms of the parameters mm and m′m', obtaining a bound on the orbit size under T2T_2, with equality when the underlying shape has period m+1m+1. The section concludes with several illustrative examples.

The orbit size of pi under the action T1

Theorem 4.1. Let nn and mm be positive integers such that Δm<n≤Δm+1\Delta_m<n\le\Delta_{m+1}. Then every periodic orbit of Pn⋆\mathcal{P}_n^\star under T1T_1 has size lcm⁡(1,2,…,m+1)\operatorname{lcm}(1,2,\ldots,m+1).

Proof. Suppose π∈Pn⋆\pi\in\mathcal{P}_n^\star is a periodic partition with distinguishable cells. By Theorem 2.3, π\pi contains cells in diag⁡[k]\operatorname{diag}[k] for 1≤k≤m+11\le k\le m+1. We track how these cells move under T1T_1. The cell in position (i,j)(i,j) moves to position (i+1,j−1)(i+1,j-1), for j>1j>1. The cell in position (1,j)(1,j) moves to position (1,j)(1,j).

These moves cyclically permute the kk positions of diag⁡[k]\operatorname{diag}[k], so each cell on this diagonal first returns to its original position after exactly kk iterations. Since every diagonal diag⁡[k]\operatorname{diag}[k] 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 π\pi under the action T2T_2

To better describe the movement of individual cells under the action of T2T_2, we introduce coordinates. For a partition π\pi, let π(i,j)\pi(i,j) denote the cell in the ithi^{\mathrm{th}} column and jthj^{\mathrm{th}} row of its Ferrers diagram. The following proposition describes the new location of this cell after applying T2T_2.

Proposition 4.2. Let nn and mm be positive integers such that Δm≤n<Δm+1\Delta_m \le n < \Delta_{m+1} and let π∈Pn∗\pi\in\mathcal{P}_n^* be a periodic point. Then

π(i,j)={(T2π)(i+1,j−1)if j>1,(T2π)(1,m+1−i)if j=1 and π has m cells in its bottom row,(T2π)(1,m+2−i)if j=1 and π has m+1 cells in its bottom row.\pi(i,j)= \begin{cases} (T_2\pi)(i+1,j-1) & \text{if } j>1,\\ (T_2\pi)(1,m+1-i) & \text{if } j=1 \text{ and } \pi\text{ has } m \text{ cells in its bottom row},\\ (T_2\pi)(1,m+2-i) & \text{if } j=1 \text{ and } \pi\text{ has } m+1 \text{ cells in its bottom row}. \end{cases}

The induced permutation

Let π∈Pn∗\pi\in\mathcal{P}_n^* be periodic. Since the period of S(π)S(\pi) under TT divides m+1m+1, the configurations π\pi and T2m+1(π)T_2^{m+1}(\pi) have the same shape. Comparing the labels in corresponding positions therefore defines a permutation of Lπ\mathcal{L}_\pi.

Definition 4.3. Let π∈P∗\pi\in\mathcal{P}^* be a periodic partition with distinguishable cells, and let m∈Nm \in\mathbb{N} be such that Δm≤n<Δm+1\Delta_m \le n < \Delta_{m+1}. Define σπ:Lπ→Lπ\sigma_\pi:\mathcal{L}_\pi\to\mathcal{L}_\pi by

σπ(π(i,j))=(T2m+1π)(i,j).\sigma_\pi(\pi(i,j))=(T_2^{m+1}\pi)(i,j).

Thus, σπ(a)=b\sigma_\pi(a)=b means that after m+1m+1 iterations of T2T_2, the label bb occupies the position initially occupied by aa.

Example 4.4. For π=((a,b,c),(d),(e))\pi=((a,b,c),(d),(e)) in Figure 7, we have m=2m=2 and T23(π)=((c,d,b),(e),(a))T_2^3(\pi)=((c,d,b),(e),(a)). Comparing the labels in corresponding positions gives σπ=(a c b d e)\sigma_\pi=(a\,c\,b\,d\,e).

Recall that the order ord⁡(σ)\operatorname{ord}(\sigma) of a permutation σ∈Sn\sigma\in S_n is the least positive integer kk such that σk=id⁡\sigma^k=\operatorname{id}; equivalently, it is the least common multiple of the lengths of the cycles in its disjoint cycle decomposition.

The orbit of a partition π∈Pn∗\pi\in\mathcal{P}_n^* under T2T_2 exhibits a dual periodicity: the Ferrers diagram returns to its original shape every m+1m+1 iterations of T2T_2, while the permutation σπ\sigma_\pi governs the cyclic rearrangement of the labels within this fixed shape. We therefore obtain the following result.

Theorem 4.5. Let π∈Pn∗\pi\in\mathcal{P}_n^* be a periodic partition under T2T_2, and let m∈Nm \in\mathbb{N} be such that Δm≤n<Δm+1\Delta_m \le n < \Delta_{m+1}. Then

∣OT2(π)∣∣(m+1)ord⁡(σπ).\lvert O_{T_2}(\pi)\rvert\mid(m+1)\operatorname{ord}(\sigma_\pi).

Moreover, if the period of the underlying shape S(π)S(\pi) under TT is ℓ=m+1\ell=m+1, then

∣OT2(π)∣=(m+1)ord⁡(σπ).\lvert O_{T_2}(\pi)\rvert=(m+1)\operatorname{ord}(\sigma_\pi).

Proof. Because the rules of T2T_2 depend only on positions, successive applications of T2m+1T_2^{m+1} act on the labels by successive powers of σπ\sigma_\pi. Consequently, T2(m+1)ord⁡(σπ)(π)=πT_2^{(m+1)\operatorname{ord}(\sigma_\pi)}(\pi)=\pi, so the period of π\pi divides (m+1)ord⁡(σπ)(m+1)\operatorname{ord}(\sigma_\pi). If the underlying shape has period m+1m+1, every return time of π\pi is a multiple of m+1m+1. Moreover, T2k(m+1)(π)=πT_2^{k(m+1)}(\pi)=\pi if and only if σπk\sigma_\pi^k is the identity. The least such positive kk is ord⁡(σπ)\operatorname{ord}(\sigma_\pi), proving the equality. □\square

For the configuration in Example 4.4, the underlying shape has period m+1=3m+1=3 and ord⁡(σπ)=5\operatorname{ord}(\sigma_\pi)=5. Theorem 4.5 therefore gives ∣OT2(π)∣=3⋅5=15\lvert O_{T_2}(\pi)\rvert=3\cdot5=15, in agreement with Figure 7.

Coloring algorithm

The goal of the following subsection will be to describe the order of σπ\sigma_\pi. We begin by introducing notation that will be used throughout.

Definition 4.6. Let π∈Pn⋆\pi\in P_n^{\star} be a periodic partition, and let m∈Nm \in\mathbb{N} be such that Δm≤n<Δm+1\Delta_m \le n < \Delta_{m+1}. The cells lying on the (m+1)(m+1)-th diagonal, denoted diag⁡[m+1]\operatorname{diag}[m+1], are called extra cells. Their number is

m′=n−m(m+1)2,m' = n - \frac{m(m+1)}{2},

where 0≤m′≤m0 \le m' \le m.

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 σπ\sigma_\pi is encoded by a coloring of the cells of π\pi. In the following description of the coloring procedure, we assume m′>0m' > 0. When m′=0m' = 0, the diagonal diag⁡[m+1]\operatorname{diag}[m+1] contains no extra cells, and every cell remains uncolored.

Let

E=((i1,h1),…,(im′,hm′)).E=((i_1,h_1),\ldots,(i_{m'},h_{m'})).

be the ordered list of extra cells of π\pi along the diagonal diag⁡[m+1]\operatorname{diag}[m+1], with i1<i2<⋯<im′i_1 < i_2 < \cdots< i_{m'}.

Define a map X:N2×N2→N2X:\mathbb{N}^2 \times\mathbb{N}^2 \to\mathbb{N}^2 by

X((a1,b1),(a2,b2))=(a1,b2),X((a_1,b_1),(a_2,b_2))=(a_1,b_2),

which returns the intersection of the column of (a1,b1)(a_1,b_1) and the row of (a2,b2)(a_2,b_2).

For 0≤k≤m′−10 \le k \le m'-1, define Xk(E)X^k(E) inductively by X0(E)=EX^0(E)=E and

Xk(E)=X(Xk−1(E)),X^k(E)=X\left(X^{k-1}(E)\right),

where XX is applied to consecutive pairs of entries in the input ordered list. That is, if

Xk−1(E)=((c1,d1),…,(cr,dr)),X^{k-1}(E)=((c_1,d_1),\ldots,(c_r,d_r)),

then

Xk(E)=(X((c1,d1),(c2,d2)),…,X((cr−1,dr−1),(cr,dr))).X^k(E)=\left(X((c_1,d_1),(c_2,d_2)),\ldots,X((c_{r-1},d_{r-1}),(c_r,d_r))\right).

Note that Xm′−1(E)=((i1,hm′))X^{m'-1}(E)=((i_1,h_{m'})).

We now define a coloring of the cells of π\pi. Let {C1,…,C⌈m′/2⌉}\{C_1,\ldots,C_{\lceil m'/2\rceil}\} be a set of distinct colors. For each 1≤r≤⌈m′/2⌉1 \le r \le\lceil m'/2\rceil, we perform an initial coloring by assigning color CrC_r to the cells in

Xr−1(E)∪Xm′−r(E).X^{r-1}(E) \cup X^{m'-r}(E).

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 CiC_i to denote the color class consisting of all cells assigned color CiC_i by this procedure.

Example 4.7. Consider the colored partition in Figure 8 with n=31n=31, m=7m=7, and m′=3m'=3. The diagonal diag⁡[8]\operatorname{diag}[8] contains the extra cells (1,8)(1,8), (4,5)(4,5), and (7,2)(7,2).

We have

E=((1,8),(4,5),(7,2)),X1(E)=((1,5),(4,2)),X2(E)=((1,2)).E=((1,8),(4,5),(7,2)), \qquad X^1(E)=((1,5),(4,2)), \qquad X^2(E)=((1,2)).

Since m′=3m'=3, we use ⌈m′/2⌉=2\lceil m'/2\rceil=2 colors. The initial coloring is given by

C1(yellow):X0(E)∪X2(E)={(1,8),(4,5),(7,2),(1,2)},C2(blue):X1(E)={(1,5),(4,2)}.C_1(\mathit{yellow}): X^0(E)\cup X^2(E)=\{(1,8),(4,5),(7,2),(1,2)\}, \qquad C_2(\mathit{blue}): X^1(E)=\{(1,5),(4,2)\}.

The coloring is then extended downward in columns and leftward in rows, as shown in Figure 8.

Cell coloring procedure for a $\pi \in \mathcal{P}^{\ast}_{31}$

Figure 8. The cell coloring procedure applied to a π∈P31∗\pi\in\mathcal{P}^{\ast}_{31}. The cells marked with ‘X’ indicate the initially colored intersection points before color propagation.

Example 4.8. For n=84n=84, m=12m=12, and m′=6m'=6, consider the periodic partition whose extra cells are

E=((3,11),(4,10),(5,9),(6,8),(9,5),(12,2)).E=((3,11),(4,10),(5,9),(6,8),(9,5),(12,2)).

The initial coloring assigns C1C_{1} (yellow) to E∪X5(E)E\cup X^{5}(E), C2C_{2} (blue) to X1(E)∪X4(E)X^{1}(E)\cup X^{4}(E), and C3C_{3} (orange) to X2(E)∪X3(E)X^{2}(E)\cup X^{3}(E). The resulting coloring after propagation is shown in Figure 9.

Cell coloring procedure for a $\pi \in \mathcal{P}^{\ast}_{84}$

Figure 9. The cell coloring procedure applied to a π∈P84∗\pi\in\mathcal{P}^{\ast}_{84}. 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 π\pi 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 π\pi. 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 mm and m′m' as given in the following lemma.

Lemma 4.9. Let π∈P∗\pi\in\mathcal{P}^{\ast} be a periodic point with n=Δm+m′n=\Delta_m+m' where 0≤m′≤m0\leq m'\leq m. Then the number of uncolored cells in π\pi under the coloring algorithm is exactly the triangular number

Δm−m′=(m−m′)(m−m′+1)2.\Delta_{m-m'}=\frac{(m-m')(m-m'+1)}{2}.

Proof. There are m+1−m′m+1-m' unoccupied positions on diag⁡[m+1]\operatorname{diag}[m+1]. Choose two such positions with column indices a<ba<b. The cell (a,m+2−b)(a,m+2-b) lies in a short column and a short row, and it belongs to the Ferrers diagram because a+(m+2−b)≤m+1a+(m+2-b)\le m+1.

Conversely, every uncolored cell (p,q)(p,q) lies in a short column and a short row, so it determines two unoccupied positions on diag⁡[m+1]\operatorname{diag}[m+1] with column indices a=pa=p and b=m+2−qb=m+2-q. Since (p,q)(p,q) is not an extra cell, p+q≤m+1p+q\le m+1, and hence a<ba<b.

Thus uncolored cells are in bijection with pairs of unoccupied positions on diag⁡[m+1]\operatorname{diag}[m+1], and their number is

(m+1−m′2)=Δm−m′.\binom{m+1-m'}{2}=\Delta_{m-m'}.

Secondly, the initial coloring pairs the sets Xt(E)X^t(E) and Xm′−1−t(E)X^{m'-1-t}(E) for t=0,…,⌈m′/2⌉−1t=0,\ldots,\lceil m'/2\rceil-1, 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 m′m' is even, each color class consists of two distinct chains (see Figure 9). When m′m' is odd, each color class likewise consists of two distinct chains, except for the last color class, corresponding to t=⌊m′/2⌋t=\lfloor m'/2\rfloor, for which the two chains coincide because Xt(E)=Xm′−1−t(E)X^t(E)=X^{m'-1-t}(E). This occurs in Figure 8, where m′=3m'=3 and the last color class consists of a single chain.

The colored induced

We now relate the color classes of π\pi to the cycle structure of σπ\sigma_\pi induced by the action of T2T_2. The coloring not only partitions the Ferrers diagram but also encodes the cycle decomposition of σπ\sigma_\pi: each color class corresponds to one cycle, while the uncolored labels are fixed. To make this precise, we define a permutation σπcol\sigma_\pi^{\mathrm{col}} determined by the coloring and show that σπcol=σπ\sigma_\pi^{\mathrm{col}}=\sigma_\pi.

We define the permutation σπcol\sigma_\pi^{\mathrm{col}} by specifying its disjoint cycle decomposition. For each color CiC_i, 1≤i≤⌈m′/2⌉1\le i\le\lceil m'/2\rceil, we construct a cycle σπCi\sigma_\pi^{C_i} as follows.

Using the heights h1,…,hm′h_1,\ldots,h_{m'} from EE, set li=hm′−i+1l_i=h_{m'-i+1}. To construct σπCi\sigma_\pi^{C_i}, first list the labels in the chain generated by Xi−1(E)X^{i-1}(E) in weak southeast order, starting at (1,hi)(1,h_i) and ending at (m+2−li,1)(m+2-l_i,1). When the two chains are distinct, append the labels in the chain generated by Xm′−i(E)X^{m'-i}(E) in the same order, starting at (1,li)(1,l_i) and ending at (m+2−hi,1)(m+2-h_i,1). Read the resulting list cyclically, so that the final label maps to the first. Thus, each σπCi\sigma_\pi^{C_i} is a cycle beginning at (1,hi)(1,h_i) and ending at (m+2−hi,1)(m+2-h_i,1).

Definition 4.10. Let π∈Pn⋆\pi\in P_n^\star be a periodic partition with label set LπL_\pi, and color its cells using the algorithm in § 4.2.2. The colored permutation σπcol:Lπ→Lπ\sigma_\pi^{\mathrm{col}}:L_\pi\to L_\pi is defined by

σπcol=σπC1σπC2⋯σπC⌈m′/2⌉,\sigma_\pi^{\mathrm{col}}=\sigma_\pi^{C_1}\sigma_\pi^{C_2}\cdots\sigma_\pi^{C_{\lceil m'/2\rceil}},

where the cycles σπCi\sigma_\pi^{C_i} are as constructed above. Every label of an uncolored cell is fixed.

Remark 4.11. For each cell (p,q)(p,q), the following rules identify the label mapped to π(p,q)\pi(p,q) under σπcol\sigma_\pi^{\mathrm{col}}.

  1. Fixed points: If row qq and column pp are both short, then

σπcol(π(p,q))=π(p,q).\sigma_\pi^{\mathrm{col}}(\pi(p,q))=\pi(p,q).
  1. Downward ↓\downarrow move: If row qq is short and column pp is long, then

σπcol(π(p,q+1))=π(p,q).\sigma_\pi^{\mathrm{col}}(\pi(p,q+1))=\pi(p,q).
  1. Diagonal ↘\searrow move: If row qq is long and column p−1p-1 is long (p≥2)(p\ge2), then

σπcol(π(p−1,q+1))=π(p,q).\sigma_\pi^{\mathrm{col}}(\pi(p-1,q+1))=\pi(p,q).
  1. Rightward →\to move: If row qq is long and column p−1p-1 is short (p≥2)(p\ge2), then

σπcol(π(p−1,q))=π(p,q).\sigma_\pi^{\mathrm{col}}(\pi(p-1,q))=\pi(p,q).
  1. Jump ↻\circlearrowright move: If p=1p=1 and row qq is long, then q=liq=l_i or q=hiq=h_i, and

σπcol(π(m+2−li,1))=π(1,li),σπcol(π(m+2−hi,1))=π(1,hi).\sigma_\pi^{\mathrm{col}}(\pi(m+2-l_i,1))=\pi(1,l_i),\qquad \sigma_\pi^{\mathrm{col}}(\pi(m+2-h_i,1))=\pi(1,h_i).

Example 4.12. Consider the labeling in Figure 10(a) of the partition colored in Figure 8, where n=31n = 31, m=7m = 7, and m′=3m' = 3. The two yellow chains give a cycle of length 14, while the single blue chain gives a cycle of length 7:

The configurations $\pi$ and $T_{2}^{8}(\pi)$

Figure 10. The configurations π\pi in (a) and T28(π)T_{2}^{8}(\pi) in (b), with cells colored by the coloring algorithm. Comparing labels in corresponding positions gives the induced permutation σπ\sigma_{\pi}.

σπcol=(1 2 3 6 7 8 12 16 22 23 24 31 18 25) (5 9 13 19 20 21 28).\sigma_{\pi}^{\mathrm{col}} = (1\ 2\ 3\ 6\ 7\ 8\ 12\ 16\ 22\ 23\ 24\ 31\ 18\ 25)\ (5\ 9\ 13\ 19\ 20\ 21\ 28).

All uncolored labels are fixed. Figure 10(b) shows T28(π)T_{2}^{8}(\pi). Comparing the labels in corresponding positions in the two panels gives the same permutation, verifying that σπ=σπcol\sigma_{\pi} = \sigma_{\pi}^{\mathrm{col}} in this example.

Equality of the coloring and induced permutations

We now prove that σπcol=σπ\sigma_{\pi}^{\mathrm{col}} = \sigma_{\pi}. This requires analyzing the behavior of cells under the action T2T_{2} 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 π∈Pn⋆\pi\in\mathcal{P}_{n}^{\star} be a periodic partition, and let aa be a label in cell (p,q)(p,q) of π\pi. Under repeated applications of T2T_{2}, the following hold:

  1. If (p,q)(p,q) is in a short row and a short column, then the label aa remains in a short row and a short column.

  1. If (p,q)(p,q) is in a short row and a long column, then the label aa 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.

  1. If (p,q)(p,q) is in a long row and column p−1p-1 is long (p≥2p \ge2), then the label aa remains in a long row until it reaches the bottom row, after which it moves to a long row and a long column.

  1. If (p,q)(p,q) is in a long row and column p−1p-1 is short (p≥2p \ge2), then the label aa 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 diag⁡[m+1]\operatorname{diag}[m+1] in that row (respectively, column).

(1) Suppose (p,q)(p,q) lies in a short row and a short column. Then there are empty positions at (m+2−q,q)(m+2-q,q) and (p,m+2−p)(p,m+2-p).

For q>1q > 1, the map T2T_{2} moves the label aa from (p,q)(p,q) to (p+1,q−1)(p+1,q-1), while these empty positions move to (m+3−q,q−1)(m+3-q,q-1) and (p+1,m+1−p)(p+1,m+1-p), respectively. Thus aa remains in a row and column that are both short.

If q=1q = 1, the label aa moves to (1,m+1−p)(1,m+1-p). The corresponding empty positions ensure that this row and column remain short, so the property is preserved.

(2) Suppose (p,q)(p,q) lies in a short row and a long column. Then column pp contains an extra cell at (p,m+2−p)(p,m+2-p).

For q>1q > 1, the label aa moves to (p+1,q−1)(p+1,q-1) and remains in a short row, and the extra cell moves to (p+1,m+1−p)(p+1,m+1-p), so the column remains long. If q=1q=1, the cell moves to (1,m+1−p)(1,m+1-p). Since the extra cell moves to (p+1,m+1−p)(p+1,m+1-p), the row becomes long, while the first column is short. Thus the type changes to (long row, short column).

(3) Suppose (p,q)(p,q) lies in a long row and column p−1p-1 is long. Then there is an extra cell at (p−1,m+3−p)(p-1,m+3-p). For q>1q>1, the image (p+1,q−1)(p+1,q-1) remains in a long row, since the extra cell structure propagates accordingly. If q=1q=1, the cell moves to (1,m+2−p)(1,m+2-p). The extra cell at (p−1,m+3−p)(p-1,m+3-p) moves to (p,m+2−p)(p,m+2-p), showing that this row is long, and the first column is also long. Hence the type becomes (long row, long column).

(4) Suppose (p,q)(p,q) lies in a long row and column p−1p-1 is short. Then there is no extra cell at (p−1,m+3−p)(p-1,m+3-p). For q>1q>1, the image (p+1,q−1)(p+1,q-1) remains in a long row. If q=1q=1, the cell moves to (1,m+2−p)(1,m+2-p). Since no extra cell moves into (p,m+2−p)(p,m+2-p), 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 π∈Pn⋆\pi\in\mathcal{P}^{\star}_{n} be a periodic partition. Then

σπ=σπcol.\sigma_{\pi}=\sigma_{\pi}^{\mathrm{col}}.

Proof. We fix a cell (p,q)(p,q) of π\pi and follow its label under m+1m+1 applications of T2T_2. 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 m+1m+1. By Definition 4.3, the label originally occupying the final position maps to π(p,q)\pi(p,q) under σπ\sigma_{\pi}.

Initial positionNumber of iterations of T2T_2New position
(p,q)(p,q)q−1q-1(p+q−1,1)(p+q-1,1)
(p+q−1,1)(p+q-1,1)11(1,m+2−p−q)(1,m+2-p-q)
(1,m+2−p−q)(1,m+2-p-q)m+1−p−qm+1-p-q(m+2−p−q,1)(m+2-p-q,1)
(m+2−p−q,1)(m+2-p-q,1)11(1,p+q−1)(1,p+q-1)
(1,p+q−1)(1,p+q-1)p−1p-1(p,q)(p,q)

Table 1. Position changes for Case 1.

Initial positionNumber of iterations of T2T_2New position
(1,q)(1,q)q−1q-1(q,1)(q,1)
(q,1)(q,1)11(1,m+2−q)(1,m+2-q)
(1,m+2−q)(1,m+2-q)m+1−qm+1-q(m+2−q,1)(m+2-q,1)

Table 5. Position changes for Case 5.

Case 1. Uncolored cells: row qq and column pp are both short.

Both bottom-row moves use the short-row rule. Table 1 gives the trajectory, which returns the label to (p,q)(p,q). Thus

σπ(π(p,q))=σπcol(π(p,q))=π(p,q).\sigma_{\pi}(\pi(p,q))=\sigma_{\pi}^{\mathrm{col}}(\pi(p,q))=\pi(p,q).

Case 2. Downward move: row qq is short and column pp 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 (p,q+1)(p,q+1). Therefore,

Initial positionNumber of iterations of T2T_2New position
(p,q)(p,q)q−1q-1(p+q−1,1)(p+q-1,1)
(p+q−1,1)(p+q-1,1)11(1,m+2−p−q)(1,m+2-p-q)
(1,m+2−p−q)(1,m+2-p-q)m+1−p−qm+1-p-q(m+2−p−q,1)(m+2-p-q,1)
(m+2−p−q,1)(m+2-p-q,1)11(1,p+q)(1,p+q)
(1,p+q)(1,p+q)p−1p-1(p,q+1)(p,q+1)

Table 2. Position changes for Case 2.

σπ(π(p,q+1))=σπcol(π(p,q+1))=π(p,q).\sigma_{\pi}(\pi(p,q+1))=\sigma_{\pi}^{\mathrm{col}}(\pi(p,q+1))=\pi(p,q).

Case 3. Diagonal move: row qq and column p−1p-1 are both long, with p≥2p \ge2.

Both bottom-row moves use the long-row rule. Table 3 gives the final position (p−1,q+1)(p-1,q+1), so

Initial positionNumber of iterations of T2T_2New position
(p,q)(p,q)q−1q-1(p+q−1,1)(p+q-1,1)
(p+q−1,1)(p+q-1,1)11(1,m+3−p−q)(1,m+3-p-q)
(1,m+3−p−q)(1,m+3-p-q)m+2−p−qm+2-p-q(m+3−p−q,1)(m+3-p-q,1)
(m+3−p−q,1)(m+3-p-q,1)11(1,p+q−1)(1,p+q-1)
(1,p+q−1)(1,p+q-1)p−2p-2(p−1,q+1)(p-1,q+1)

Table 3. Position changes for Case 3.

σπ(π(p−1,q+1))=σπcol(π(p−1,q+1))=π(p,q).\sigma_{\pi}\bigl(\pi(p-1,q+1)\bigr)=\sigma_{\pi}^{\mathrm{col}}\bigl(\pi(p-1,q+1)\bigr)=\pi(p,q).

Case 4. Rightward move: row qq is long and column p−1p-1 is short, with p≥2p \ge2.

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 (p−1,q)(p-1,q), yielding

Initial positionNumber of iterations of T2T_2New position
(p,q)(p,q)q−1q-1(p+q−1,1)(p+q-1,1)
(p+q−1,1)(p+q-1,1)11(1,m+3−p−q)(1,m+3-p-q)
(1,m+3−p−q)(1,m+3-p-q)m+2−p−qm+2-p-q(m+3−p−q,1)(m+3-p-q,1)
(m+3−p−q,1)(m+3-p-q,1)11(1,p+q−2)(1,p+q-2)
(1,p+q−2)(1,p+q-2)p−2p-2(p−1,q)(p-1,q)

Table 4. Position changes for Case 4.

σπ(π(p−1,q))=σπcol(π(p−1,q))=π(p,q).\sigma_{\pi}\bigl(\pi(p-1,q)\bigr)=\sigma_{\pi}^{\mathrm{col}}\bigl(\pi(p-1,q)\bigr)=\pi(p,q).

Case 5. Jump move: p=1p=1 and q=liq=l_i or q=hiq=h_i.

Since row qq is long, the bottom-row move uses the long-row rule. Table 5 gives the final position (m+2−q,1)(m+2-q,1). Hence

σπ(π(m+2−q,1))=σπcol(π(m+2−q,1))=π(1,q).\sigma_{\pi}\bigl(\pi(m+2-q,1)\bigr)=\sigma_{\pi}^{\mathrm{col}}\bigl(\pi(m+2-q,1)\bigr)=\pi(1,q).

These cases cover every cell of π\pi. Thus the two permutations have the same preimage for every label, and hence σπ=σπcol\sigma_{\pi}=\sigma_{\pi}^{\mathrm{col}}.

The order of σπcol\sigma_{\pi}^{\mathrm{col}}

Having established that σπcol=σπ\sigma_{\pi}^{\mathrm{col}}=\sigma_{\pi}, 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 σπcol\sigma_{\pi}^{\mathrm{col}}. We do this by studying the sizes of the color classes obtained with the coloring algorithm.

Theorem 4.15. Let n≥1n \ge1, and let mm be the unique positive integer such that

Δm≤n<Δm+1.\Delta_m \le n < \Delta_{m+1}.

Set m′=n−Δmm' = n-\Delta_m, and let π∈Pn∗\pi\in\mathcal{P}_n^* be periodic. Then

ord⁡(σπ)=ord⁡(σπcol)={1,if m′=0,m+1,if m′=1,2m−m′+3,if 2≤m′≤m.\operatorname{ord}(\sigma_\pi)=\operatorname{ord}(\sigma_\pi^{\mathrm{col}})= \begin{cases} 1, & \text{if }m'=0,\\ m+1, & \text{if }m'=1,\\ 2m-m'+3, & \text{if }2\le m'\le m. \end{cases}

Proof. Let m′=n−Δmm'=n-\Delta_m. We consider three cases.

Case 1: m′=0m'=0. Then π\pi is the full triangular partition of size Δm\Delta_m. In this case, σπcol\sigma_\pi^{\mathrm{col}}, and hence also σπ\sigma_\pi, is the identity permutation. Therefore,

ord⁡(σπ)=1.\operatorname{ord}(\sigma_\pi)=1.

Case 2: m′=1m'=1. There is exactly one extra cell, say at location (i,h)(i,h) in the (m+1)(m+1)-st diagonal. The coloring algorithm colors this cell together with i−1i-1 cells to its left and h−1h-1 cells below. The total number of colored cells is

1+(i−1)+(h−1)=i+h−1=m+1.1+(i-1)+(h-1)=i+h-1=m+1.

These labels form a single cycle, so ord⁡(σπ)=m+1\operatorname{ord}(\sigma_\pi)=m+1.

Case 3: 2≤m′≤m2\le m'\le m. Let the extra cells on diag⁡[m+1]\operatorname{diag}[m+1] be

E=((i1,h1),…,(im′,hm′)),i1<⋯<im′,E=((i_1,h_1),\ldots,(i_{m'},h_{m'})),\qquad i_1<\cdots<i_{m'},

so ik+hk=m+2i_k+h_k=m+2 and hence h1>⋯>hm′h_1>\cdots>h_{m'}. For 0≤t≤m′−10\le t\le m'-1 set

Xt(E)=((i1,h1+t),…,(im′−t,hm′)).X^t(E)=((i_1,h_{1+t}),\ldots,(i_{m'-t},h_{m'})).

Fix 1≤r≤⌈m′/2⌉1\le r\le\lceil m'/2\rceil. The color CrC_r consists of the two components Xr−1(E)X^{r-1}(E) and Xm′−r(E)X^{m'-r}(E) (coinciding if m′m' is odd and r=m′+12r=\frac{m'+1}{2}). Write

Xt(E)=((c1,d1),…,(cm′−t,dm′−t)).X^t(E)=((c_1,d_1),\ldots,(c_{m'-t},d_{m'-t})).

Leftward propagation in row djd_j colors cj−cj−1−1c_j-c_{j-1}-1 cells (with c0=0c_0=0), while downward propagation in column cjc_j colors dj−dj+1−1d_j-d_{j+1}-1 cells (with dm′−t+1=0d_{m'-t+1}=0). Thus, the total number of cells colored by CrC_r in this component, starting from the cells in Xt(E)X^t(E), is

∑j=1m′−t(1+cj−cj−1−1+dj−dj+1−1)=cm′−t+d1−(m′−t)=im′−t+h1+t−m′+t.\sum_{j=1}^{m'-t}(1+c_j-c_{j-1}-1+d_j-d_{j+1}-1) =c_{m'-t}+d_1-(m'-t) =i_{m'-t}+h_{1+t}-m'+t.

Suppose first that the two chains of CrC_r are distinct. Applying the preceding calculation to the two chains of CrC_r,

∣Cr∣=(im′−r+1+hr−m′+r−1)+(ir+hm′−r+1−r)=(im′−r+1+m+2−ir−m′+r−1)+(ir+m+2−im′−r+1−r)=2m−m′+3.\begin{aligned} |C_r|&=(i_{m'-r+1}+h_r-m'+r-1)+(i_r+h_{m'-r+1}-r)\\ &=(i_{m'-r+1}+m+2-i_r-m'+r-1)+(i_r+m+2-i_{m'-r+1}-r)\\ &=2m-m'+3. \end{aligned}

Thus every color class consisting of two distinct chains has 2m−m′+32m-m'+3 cells. If m′m' is odd and r=(m′+1)/2r=(m'+1)/2, the two chains coincide, so the final color class has (2m−m′+3)/2(2m-m'+3)/2 cells. If m′m' is even, every color class has 2m−m′+32m-m'+3 cells. Since m′≥2m'\ge2, at least one cycle has length 2m−m′+32m-m'+3, and every other cycle length divides this number. Therefore,

ord⁡(σπcol)=2m−m′+3.\operatorname{ord}(\sigma_\pi^{\mathrm{col}})=2m-m'+3.

The equality σπ=σπcol\sigma_\pi=\sigma_\pi^{\mathrm{col}} now gives the stated formula.

:::

Corollary 4.16. Let π∈Pn⋆\pi\in P_n^\star be a periodic point with n=Δm+m′n = \Delta_m + m' and 0≤m′≤m0 \le m' \le m. Then the orbit size of π\pi under T2T_2 divides

{m+1,if m′=0,(m+1)2,if m′=1,(m+1)(2m−m′+3),if 2≤m′≤m.\begin{cases} m+1, & \text{if }m'=0,\\ (m+1)^2, & \text{if }m'=1,\\ (m+1)(2m-m'+3), & \text{if }2\le m'\le m. \end{cases}

Moreover, if the period of the underlying shape S(π)S(\pi) under TT is ℓ=m+1\ell=m+1, then “divides” may be replaced by “equals”.

Proof. The claim follows from substituting the values of ord⁡(σπ)\operatorname{ord}(\sigma_\pi) 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 m+1m+1.

Example 4.17 (n=18n=18, m=5m=5, m′=3m'=3). There are four periodic orbits in P18P_{18} under TT, 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 ℓ\ell.

Labeled configurations representing four periodic orbits

Figure 11. Labeled configurations whose underlying shapes represent the four distinct periodic orbits in P18P_{18} under TT. Extra cells (the m′=3m'=3 cells on diag[6]) are indicated in gray. The underlying shapes in (a)–(c) have period ℓ=6\ell=6 under TT, while the shape in (d) has period ℓ=2\ell=2.

By Corollary 4.16, since ℓ=m+1\ell=m+1, the first three orbits under the action of T2T_2 have size (m+1)(2m−m′+3)=60(m+1)(2m-m'+3)=60, while the fourth orbit has size dividing 60. However, direct computation shows that the fourth orbit also has size 60.

Example 4.18 (n=8n=8, m=3m=3, m′=2m'=2). There are two periodic orbits in P8P_8 under TT, 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 ℓ\ell.

Labeled configurations representing two periodic orbits

Figure 12. Labeled configurations whose underlying shapes represent the two distinct periodic orbits in P8P_8 under TT. Extra cells on diag[4] are shaded gray and labeled d,gd,g in (a) and d,hd,h in (b). The underlying shapes in (a) and (b) have periods ℓ=4\ell=4 and ℓ=2\ell=2 under TT, respectively.

Here ord⁡(σπ)=2m−m′+3=7\operatorname{ord}(\sigma_\pi)=2m-m'+3=7. By Corollary 4.16, since ℓ=m+1\ell=m+1 for orbit (a), its size under T2T_2 equals (m+1)ord⁡(σπ)=28(m+1)\operatorname{ord}(\sigma_\pi)=28; for orbit (b) with ℓ=2\ell=2, 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 T2T_2 always divides (m+1)ord⁡(σπ)(m+1)\operatorname{ord}(\sigma_\pi), and sometimes attains it. In the next section, we determine the exact orbit sizes and prove that the upper bound (m+1)ord⁡(σπ)(m+1)\operatorname{ord}(\sigma_\pi) from Corollary 4.16 is achieved in most cases, even when ℓ≠m+1\ell\ne m+1, and when it is not, the orbit size is exactly half of that bound.

Exact sizes of orbits under T2T_2

In this section, we determine the exact orbit sizes of periodic partitions under T2T_2 and characterize when the bound (m+1)ord⁡(σπ)(m+1)\operatorname{ord}(\sigma_\pi) from Corollary 4.16 is attained. As the preceding examples show, equality can hold even when the period ℓ\ell of the underlying shape is less than m+1m+1. We prove that, for m≥3m\ge3, the bound is attained except when m′=m−1m'=m-1 and ℓ=(m+1)/2\ell=(m+1)/2, 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 π∈Pn⋆\pi\in P_n^\star be a periodic partition whose cells are colored using the algorithm in § 4.2.2. Define:

  • Lπ,C\mathcal{L}_{\pi,C} as the set of labels of colored cells of π\pi,

  • Lπ,U\mathcal{L}_{\pi,U} as the set of labels of uncolored cells of π\pi,

  • for each color CiC_i (i=1,…,⌈m′/2⌉i=1,\ldots,\lceil m'/2\rceil), Lπ,Ci\mathcal{L}_{\pi,C_i} as the set of labels of cells colored with CiC_i.

Note that

Lπ=Lπ,C⊔Lπ,UandLπ,C=⨆i=1⌈m′/2⌉Lπ,Ci.\mathcal{L}_\pi=\mathcal{L}_{\pi,C}\sqcup\mathcal{L}_{\pi,U}\quad\text{and}\quad\mathcal{L}_{\pi,C}=\bigsqcup_{i=1}^{\lceil m'/2\rceil}\mathcal{L}_{\pi,C_i}.

We now introduce the permutation of all labels induced by one full period of the underlying shape.

Definition 5.2. Let π∈Pn⋆\pi\in P_n^\star be a periodic partition. The permutation τπ:Lπ→Lπ\tau_\pi:\mathcal{L}_\pi\to\mathcal{L}_\pi is defined by

τπ(π(i,j))=(T2ℓπ)(i,j),\tau_\pi\bigl(\pi(i,j)\bigr)=\bigl(T_2^\ell\pi\bigr)(i,j),

where ℓ\ell is the period of the underlying unlabeled partition under TT.

Lemma 5.3. Let π∈Pn⋆\pi\in P_n^\star be a periodic point with n=Δm+m′n=\Delta_m+m', 0≤m′≤m0\le m'\le m. Let ℓ\ell be the period of the underlying unlabeled partition under TT and set r=(m+1)/ℓr=(m+1)/\ell. For each color class CiC_i (i=1,…,⌈m′/2⌉i=1,\ldots,\lceil m'/2\rceil) the following hold:

(a) The set Lπ,Ci\mathcal{L}_{\pi,C_i} is invariant under τπ\tau_\pi, i.e.,

τπ(Lπ,Ci)=Lπ,Ci.\tau_\pi(\mathcal{L}_{\pi,C_i})=\mathcal{L}_{\pi,C_i}.

(b) The restriction τπ,Ci:=τπ∣Lπ,Ci\tau_{\pi,C_i}:=\tau_\pi|_{\mathcal{L}_{\pi,C_i}} is a permutation of Lπ,Ci\mathcal{L}_{\pi,C_i} and satisfies

τπ,Cir=σπ,Ci,\tau_{\pi,C_i}^{r}=\sigma_{\pi,C_i},

where σπ,Ci:=σπ∣Lπ,Ci\sigma_{\pi,C_i}:=\sigma_\pi|_{\mathcal{L}_{\pi,C_i}}.

(c) The permutation τπ,Ci\tau_{\pi,C_i} is a single cycle on Lπ,Ci\mathcal{L}_{\pi,C_i}.

Proof. (a) We first show that a label retains its color after one application of T2T_2, when the resulting configuration is colored by the algorithm.

Let (p,q)(p,q) be a colored cell, and let

d=#{s:p≤is≤m+2−q},d=\#\{s:p\le i_s\le m+2-q\},

where i1,…,im′i_1,\ldots,i_{m'} are the column indices of the extra cells. The color of (p,q)(p,q) is Cmin⁡(d,m′+1−d)C_{\min(d,m'+1-d)}. Indeed, at a cell of Xd−1(E)X^{d-1}(E) the indicated interval contains exactly dd extra-cell column indices, and propagation along the corresponding chain does not change this number.

If q>1q>1, Proposition 4.2 sends (p,q)(p,q) to (p+1,q−1)(p+1,q-1). The interval and the extra-cell positions shift together, so dd is unchanged.

Suppose q=1q=1. If the bottom row is long, the label moves to (1,m+2−p)(1,m+2-p), and the number of extra-cell column indices in the new interval is m′+1−dm'+1-d. If the bottom row is short, then column pp must be long because the cell is colored. The label moves to (1,m+1−p)(1,m+1-p), and the new count is again m′+1−dm'+1-d. In both cases the resulting cell is colored, and

min⁡(d,m′+1−d)=min⁡(m′+1−d,d).\min(d,m'+1-d)=\min(m'+1-d,d).

Thus the label retains its color.

Iterating this observation ℓ\ell times, and using the fact that T2ℓ(π)T_2^\ell(\pi) has the same shape as π\pi, shows that

τπ(Lπ,Ci)=Lπ,Ci.\tau_\pi(\mathcal{L}_{\pi,C_i})=\mathcal{L}_{\pi,C_i}.

(b) Therefore, the restriction

τπ,Ci:=τπ∣Lπ,Ci\tau_{\pi,C_i}:=\left.\tau_\pi\right|_{\mathcal{L}_{\pi,C_i}}

is a permutation of Lπ,Ci\mathcal{L}_{\pi,C_i}. Since m+1=ℓrm+1=\ell r, by Definitions 4.3 and 5.2,

τπr=σπ.\tau_\pi^r=\sigma_\pi.

By Theorem 4.14, we also have σπ=σπcol\sigma_\pi=\sigma_\pi^{\mathrm{col}}. Restricting this identity to Lπ,Ci\mathcal{L}_{\pi,C_i} gives

τπ,Cir=σπ∣Lπ,Ci=σπcol∣Lπ,Ci=σπ,Ci.\tau_{\pi,C_i}^r=\left.\sigma_\pi\right|_{\mathcal{L}_{\pi,C_i}}=\left.\sigma_\pi^{\mathrm{col}}\right|_{\mathcal{L}_{\pi,C_i}}=\sigma_{\pi,C_i}.

(c) By construction, each σπ,Ci\sigma_{\pi,C_i} is a single cycle. Since σπ,Ci=τπ,Cir\sigma_{\pi,C_i}=\tau_{\pi,C_i}^r, a power of τπ,Ci\tau_{\pi,C_i} is a single cycle. Hence τπ,Ci\tau_{\pi,C_i} itself must be a single cycle on Lπ,Ci\mathcal{L}_{\pi,C_i}.

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 π∈Pn⋆\pi\in\mathcal{P}_n^\star be a periodic partition with n=Δm+m′n=\Delta m+m' and 0≤m′≤m0\le m'\le m. Let ℓ\ell denote the period of the underlying unlabeled partition under TT, so that ℓ∣(m+1)\ell\mid(m+1), and set r=(m+1)/ℓr=(m+1)/\ell. Then

gcd⁡(ord⁡(σπ),r)=1.\gcd(\operatorname{ord}(\sigma_\pi),r)=1.

Proof. We consider three cases based on the value of m′m'.

Case m′=0m'=0. Then, by Theorem 4.15, ord⁡(σπ)=1\operatorname{ord}(\sigma_\pi)=1, so gcd⁡(ord⁡(σπ),r)=1\gcd(\operatorname{ord}(\sigma_\pi),r)=1.

Case m′=1m'=1. Then, by Theorem 4.15, ord⁡(σπ)=m+1\operatorname{ord}(\sigma_\pi)=m+1. Since there is a single extra cell, the underlying unlabeled partition has full period ℓ=m+1\ell=m+1, hence r=1r=1. Thus gcd⁡(ord⁡(σπ),r)=1\gcd(\operatorname{ord}(\sigma_\pi),r)=1.

Case 2≤m′≤m2\le m'\le m. Then, by Theorem 4.15, we have ord⁡(σπ)=2m−m′+3\operatorname{ord}(\sigma_\pi)=2m-m'+3. The binary word recording the occupied positions on diag⁡[m+1]\operatorname{diag}[m+1] consists of rr repetitions of a block of length ℓ\ell. Therefore its number m′m' of occupied positions is divisible by rr. Write m′=ram'=ra for some integer a≥1a\ge1. Since m=ℓr−1m=\ell r-1, we compute

ord⁡(σπ)=2m−m′+3=2(ℓr−1)−ra+3=r(2ℓ−a)+1.\operatorname{ord}(\sigma_\pi)=2m-m'+3=2(\ell r-1)-ra+3=r(2\ell-a)+1.

Hence ord⁡(σπ)≡1(modr)\operatorname{ord}(\sigma_\pi)\equiv1\pmod r, which implies gcd⁡(ord⁡(σπ),r)=1\gcd(\operatorname{ord}(\sigma_\pi),r)=1.

We are now ready to state the main theorem that gives the exact orbit sizes under T2T_2.

Theorem 5.5. Let π∈Pn⋆\pi\in\mathcal{P}_n^\star be a periodic point under the action T2T_2, with n≥1n\ge1 and n=Δm+m′n=\Delta m+m', 0≤m′≤m0\le m'\le m. Let ℓ\ell be the period of the underlying unlabeled partition under TT. Then, the orbit size of π\pi under T2T_2 is

∣OT2(π)∣={(m+1)⋅ord⁡(σπ),if m−m′≥2,ℓ⋅ord⁡(σπ),otherwise.\left|O_{T_2}(\pi)\right|= \begin{cases} (m+1)\cdot\operatorname{ord}(\sigma_\pi), & \text{if }m-m'\ge2,\\ \ell\cdot\operatorname{ord}(\sigma_\pi), & \text{otherwise.} \end{cases}

Proof. Let L=ord⁡(σπ)L = \operatorname{ord}(\sigma_\pi) and r=(m+1)/ℓr = (m + 1)/\ell, and let τπ\tau_\pi be the permutation from Definition 5.2. Since m+1=ℓrm + 1 = \ell r, Definitions 4.3 and 5.2 give τπr=σπ\tau_\pi^r = \sigma_\pi.

By Lemma 5.3, τπ\tau_\pi preserves each colored label set Lπ,Ci\mathcal{L}_{\pi,C_i}. Consequently, it preserves their union Lπ,C\mathcal{L}_{\pi,C} and its complement Lπ,U\mathcal{L}_{\pi,U}. Define the restrictions

τc=τπ∣Lπ,C,τu=τπ∣Lπ,U,\tau_c = \tau_\pi|_{\mathcal{L}_{\pi,C}}, \qquad\tau_u = \tau_\pi|_{\mathcal{L}_{\pi,U}},

and let mc=ord⁡(τc)m_c = \operatorname{ord}(\tau_c) and mu=ord⁡(τu)m_u = \operatorname{ord}(\tau_u). Since these restrictions act on disjoint label sets,

ord⁡(τπ)=lcm⁡(mc,mu).\operatorname{ord}(\tau_\pi) = \operatorname{lcm}(m_c,m_u).

Moreover, σπ\sigma_\pi fixes every uncolored label, so restricting τπr=σπ\tau_\pi^r = \sigma_\pi to Lπ,U\mathcal{L}_{\pi,U} gives τur=id⁡\tau_u^r = \operatorname{id}. Hence mu∣rm_u \mid r.

Every return time of π\pi under T2T_2 is a multiple of ℓ\ell, since its underlying shape has period ℓ\ell. Because the shape repeats every ℓ\ell steps and the rules of T2T_2 do not depend on the labels, T2kℓ(π)=πT_2^{k\ell}(\pi) = \pi if and only if τπk=id⁡\tau_\pi^k = \operatorname{id}. Therefore,

∣OT2(π)∣=ℓord⁡(τπ)=ℓlcm⁡(mc,mu).|O_{T_2}(\pi)| = \ell\operatorname{ord}(\tau_\pi) = \ell\operatorname{lcm}(m_c,m_u).

By Lemma 5.3, each restriction τπ,Ci\tau_{\pi,C_i} is a single cycle on the same label set as σπ,Ci\sigma_{\pi,C_i}, so these cycles have the same length. Since σπ\sigma_\pi fixes all uncolored labels, taking the least common multiple of the colored cycle lengths gives mc=ord⁡(τc)=ord⁡(σπ)=Lm_c = \operatorname{ord}(\tau_c) = \operatorname{ord}(\sigma_\pi) = L. This also holds when m′=0m' = 0, since both permutations are identities.

Next, we determine mu=ord⁡(τu)m_u = \operatorname{ord}(\tau_u). Suppose first that there is no more than one uncolored cell. Then τu\tau_u must be the identity on at most one label, hence mu=1m_u = 1.

Suppose now that there are at least three uncolored cells.

Suppose now that there at least two uncolored cells. Let k=m−m′k = m - m'. Let A⊆{1,…,m+1}A \subseteq\{1,\ldots,m+1\} be the set of column indices of the unoccupied positions on diag⁡[m+1]\operatorname{diag}[m+1]. Then ∣A∣=m+1−m′=k+1≥3|A| = m + 1 - m' = k + 1 \ge3.

The uncolored labels are in bijection with the two-element subsets of AA via

π(p,q)⟷{p,m+2−q}.\pi(p,q) \longleftrightarrow\{p,m+2-q\}.

Indeed, an uncolored cell lies in a short column and a short row, and p<m+2−qp < m + 2 - q. Conversely, for a<ba < b in AA, the cell (a,m+2−b)(a,m+2-b) is uncolored.

By Proposition 4.2, if q>1q > 1, the cell (p,q)(p,q) moves to (p+1,q−1)(p+1,q-1), so its associated pair becomes {p+1,m+3−q}\{p+1,m+3-q\}. If q=1q = 1, the bottom row must be short because the cell is uncolored. Hence the second branch of Proposition 4.2 applies, sending (p,1)(p,1) to (1,m+1−p)(1,m+1-p), whose associated pair is {1,p+1}\{1,p+1\}. In both cases, the associated unordered pair is obtained by adding 11 modulo m+1m+1 to each of its indices, with residues represented by 1,…,m+11,\ldots,m+1. Since the shape returns after ℓ\ell steps, addition of ℓ\ell modulo m+1m+1 permutes AA. Its induced action on the two-element subsets of AA is the inverse of τu\tau_u.

Suppose τud=id⁡\tau_u^d = \operatorname{id}. Then addition of ℓd\ell d modulo m+1m+1 fixes every two-element subset of AA. For any a∈Aa \in A, choose distinct b,c∈A∖{a}b,c \in A \setminus\{a\}. Since this translation fixes both {a,b}\{a,b\} and {a,c}\{a,c\}, it fixes their intersection {a}\{a\}. Thus ℓd≡0(modm+1)\ell d \equiv0 \pmod{m+1}, which implies r∣dr \mid d. Together with τur=id⁡\tau_u^r = \operatorname{id}, this proves that mu=ord⁡(τu)=rm_u = \operatorname{ord}(\tau_u) = r.

We have shown that mc=Lm_c = L, while mu=rm_u = r if m−m′≥2m - m' \ge2 and mu=1m_u = 1 otherwise. By Lemma 5.4, gcd⁡(L,r)=1\gcd(L,r) = 1. Consequently,

∣OT2(π)∣=ℓlcm⁡(mc,mu)={ℓLr=(m+1)L,if m−m′≥2,ℓL,otherwise.|O_{T_2}(\pi)| = \ell\operatorname{lcm}(m_c,m_u) = \begin{cases} \ell Lr = (m+1)L, & \text{if } m-m' \ge2,\\ \ell L, & \text{otherwise.} \end{cases}

Since L=ord⁡(σπ)L = \operatorname{ord}(\sigma_\pi), this proves the theorem.

Combining Theorem 5.5 with the explicit formula for ord⁡(σπ)\operatorname{ord}(\sigma_\pi) from Theorem 4.15, we obtain the following closed-form expressions for orbit sizes when m≥3m \ge3.

Theorem 5.6. Let π∈Pn∗\pi\in\mathcal{P}_n^* be a periodic point under the action T2T_2, where n=Δm+m′n = \Delta_m + m' with m≥3m \ge3 and 0≤m′≤m0 \le m' \le m. Let ℓ\ell be the period of the underlying unlabeled partition under TT. Then, the orbit size of π\pi

under T2T_2 is

∣OT2(π)∣={m+1,if m′=0 (n=Δm),(m+1)2,if m′=1 (n=Δm+1),(m+1)(2m−m′+3),if 2≤m′≤m−2,(m+1)(m+4) or (m+1)(m+4)2,if m′=m−1 (n=Δm+m−1),(m+1)(m+3),if m′=m (n=Δm+m).\left|O_{T_2}(\pi)\right| = \begin{cases} m+1, & \text{if }m'=0\ (n=\Delta_m),\\ (m+1)^2, & \text{if }m'=1\ (n=\Delta_m+1),\\ (m+1)(2m-m'+3), & \text{if }2\le m'\le m-2,\\ (m+1)(m+4)\text{ or }\frac{(m+1)(m+4)}{2}, & \text{if }m'=m-1\ (n=\Delta_m+m-1),\\ (m+1)(m+3), & \text{if }m'=m\ (n=\Delta_m+m). \end{cases}

The second value occurs exactly when ℓ=(m+1)/2\ell=(m+1)/2, equivalently when the two white beads in the associated necklace are opposite each other. This is possible only when mm is odd.

Proof. For 0≤m′≤m−20\le m'\le m-2, we have m−m′≥2m-m'\ge2, so the stated orbit sizes follow directly from Theorems 4.15 and 5.5.

Suppose m′=m−1m'=m-1. These theorems give ∣OT2(π)∣=ℓ(m+4)\left|O_{T_2}(\pi)\right|=\ell(m+4). The associated necklace has length m+1m+1 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 ℓ=m+1\ell=m+1 unless the white beads are opposite each other, in which case ℓ=(m+1)/2\ell=(m+1)/2. The latter is possible only when mm is odd, giving the two stated orbit sizes.

Finally, if m′=mm'=m, the associated necklace has exactly one white bead and therefore has full period ℓ=m+1\ell=m+1. Since ord⁡(σπ)=m+3\operatorname{ord}(\sigma_\pi)=m+3, Theorem 5.5 gives ∣OT2(π)∣=(m+1)(m+3)\left|O_{T_2}(\pi)\right|=(m+1)(m+3).

Conjugation symmetries

In Section 3, we established how the reversal operation interacts with our four actions TiT_i, i=1,2,3,4i=1,2,3,4: it conjugates T1T_1 to T4T_4 and T2T_2 to T3T_3. 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 T1T_1 and T2T_2 on periodic partitions and use reversal to obtain corresponding relations for T3T_3 and T4T_4.

Definition 6.1. Let π∈Pn⋆\pi\in P_n^\star. The conjugate of π\pi, denoted conj⁡(π)\operatorname{conj}(\pi), is the partition obtained by reflecting the Ferrers diagram of π\pi across its main diagonal. Equivalently,

conj⁡(π)(i,j)=π(j,i)\operatorname{conj}(\pi)(i,j)=\pi(j,i)

for every cell (i,j)(i,j) in the Ferrers diagram of conj⁡(π)\operatorname{conj}(\pi). Thus, the label occupying row ii and column jj in π\pi occupies row jj and column ii in conj⁡(π)\operatorname{conj}(\pi). Note that conjugation is an involution; that is, conj⁡(conj⁡(π))=π\operatorname{conj}(\operatorname{conj}(\pi))=\pi for every π∈Pn⋆\pi\in P_n^\star.

Since conjugation preserves each diagonal diag⁡[k]\operatorname{diag}[k] setwise, Theorem 2.3 and Proposition 3.4 imply that it preserves periodicity. We examine how the actions T1T_1 and T2T_2 interact with conjugation.

Proposition 6.2. For every periodic π∈Pn⋆\pi\in P_n^\star, the following diagrams commute:

\begin{CD} \pi@>{T_1}>> T_1(\pi)\\ @V{\operatorname{conj}}VV @VV{\operatorname{conj}}V\\ \operatorname{conj}(\pi) @<<{T_1}< \operatorname{conj}(T_1(\pi)) \end{CD} \qquad \begin{CD} \pi@>{T_2}>> T_2(\pi)\\ @V{\operatorname{conj}}VV @VV{\operatorname{conj}}V\\ \operatorname{conj}(\pi) @<<{T_2}< \operatorname{conj}(T_2(\pi)) \end{CD}

Equivalently,

T1∘conj⁡∘T1=conj⁡,T2∘conj⁡∘T2=conj⁡.T_1\circ\operatorname{conj}\circ T_1=\operatorname{conj},\qquad T_2\circ\operatorname{conj}\circ T_2=\operatorname{conj}.

:::`

Proof. Let π∈Pn⋆\pi\in P_n^\star be periodic. Under conjugation, the label x=π(i,j)x = \pi(i,j) moves to position (j,i)(j,i) in conj⁡(π)\operatorname{conj}(\pi).

The action T1T_1. Under T1T_1, the label xx moves to (1,i)(1,i) if j=1j=1, and to (i+1,j−1)(i+1,j-1) if j>1j>1. After conjugation, these positions become

(i,1)if j=1,and(j−1,i+1)if j>1.(i,1) \qquad\text{if } j=1, \qquad\text{and} \qquad(j-1,i+1) \qquad\text{if } j>1.

Applying T1T_1 once more, the entry at (i,1)(i,1) moves to (1,i)(1,i), whereas the cell at (j−1,i+1)(j-1,i+1) moves to (j,i)(j,i). Thus in either case the final position is (j,i)(j,i), exactly the position of xx in conj⁡(π)\operatorname{conj}(\pi). Therefore

T1∘conj⁡∘T1=conj⁡.T_1 \circ\operatorname{conj} \circ T_1 = \operatorname{conj}.

The action T2T_2. Let kk denote the number of columns of π\pi, equivalently the length of its bottom row. Under T2T_2, an entry with j>1j>1 again moves to (i+1,j−1)(i+1,j-1), while a bottom row entry at (i,1)(i,1) is placed in the new first column at position (1,k+1−i)(1,k+1-i). After conjugation, these become

(k+1−i,1)if j=1,and(j−1,i+1)if j>1.(k+1-i,1) \qquad\text{if } j=1, \qquad\text{and} \qquad(j-1,i+1) \qquad\text{if } j>1.

Since π\pi is periodic, the newly formed column of T2(π)T_2(\pi) has length kk and is at least as long as every remaining column. Thus T2(π)T_2(\pi) has exactly kk rows, so the bottom row of conj⁡(T2(π))\operatorname{conj}(T_2(\pi)) has length kk. Hence applying T2T_2 again sends the entry at (k+1−i,1)(k+1-i,1) to (1,k+1−(k+1−i))=(1,i)(1,k+1-(k+1-i))=(1,i), while the entry at (j−1,i+1)(j-1,i+1) moves to (j,i)(j,i). Thus the final position is again (j,i)(j,i), which is precisely the position of xx in conj⁡(π)\operatorname{conj}(\pi). Therefore

T2∘conj⁡∘T2=conj⁡.T_2 \circ\operatorname{conj} \circ T_2 = \operatorname{conj}.

Since this holds for every entry xx of π\pi, the result follows.

On the set of periodic partitions, Proposition 6.2 can equivalently be written as

conj⁡∘Ti=Ti−1∘conj⁡,i=1,2.\operatorname{conj} \circ T_i = T_i^{-1} \circ\operatorname{conj}, \qquad i=1,2.

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 T3T_3 and T4T_4. On the set of periodic partitions,

Ti∘(rev⁡∘conj⁡∘rev⁡)∘Ti=rev⁡∘conj⁡∘rev⁡,i=3,4.T_i \circ(\operatorname{rev} \circ\operatorname{conj} \circ\operatorname{rev}) \circ T_i = \operatorname{rev} \circ\operatorname{conj} \circ\operatorname{rev}, \qquad i=3,4.

Indeed, these identities follow by composing the identities in Proposition 6.2 on both sides with rev⁡\operatorname{rev} and using Proposition 3.7. Thus, the involution rev⁡∘conj⁡∘rev⁡\operatorname{rev} \circ\operatorname{conj} \circ\operatorname{rev} reverses the direction of the action on periodic orbits of T3T_3 and T4T_4, just as conj⁡\operatorname{conj} does for T1T_1 and T2T_2.

Remark 6.4. Proposition 6.2 does not hold for arbitrary (non-periodic) partitions. For example, let n=3n=3 and consider the one-column partition π=((a,b,c))∈P3⋆\pi=((a,b,c)) \in P_3^\star (where the cells are listed from bottom to top). Then conj⁡(π)=((a),(b),(c))\operatorname{conj}(\pi)=((a),(b),(c)); in particular conj⁡(π)\operatorname{conj}(\pi) has three columns of size 1. On the other hand,

T2(π)=((b,c))∪(a)=((b,c),(a)),conj⁡(T2(π))=((b,a),(c)),T_2(\pi)=((b,c))\cup(a)=((b,c),(a)), \qquad\operatorname{conj}(T_2(\pi))=((b,a),(c)),

and finally

T2(conj⁡(T2(π)))=((c,b),(a))≠conj⁡(π).T_2(\operatorname{conj}(T_2(\pi)))=((c,b),(a))\ne\operatorname{conj}(\pi).

Thus the identity for T2T_2 fails for this nonperiodic partition. Similarly,

T1(conj⁡(T1(π)))=((b,c),(a))≠conj⁡(π).T_1(\operatorname{conj}(T_1(\pi)))=((b,c),(a))\ne\operatorname{conj}(\pi).

Consequently, the periodicity assumption in Proposition 6.2 cannot be omitted.

References

References

  1. [1]Ethan Akin and Morton Davis. Bulgarian solitaire. Amer. Math. Monthly, 92(4):237–250, 1985.DOI
  2. [2]Borislav Bojanov. Problem solution 4. Obuchenieto po matematika, 24(5):59–60, 1981.
  3. [3]Jørgen Brandt. Cycles of partitions. Proc. Amer. Math. Soc., 85(3):483–486, 1982.DOI
  4. [4]C. Cannings and J. Haigh. Montreal solitaire. J. Combin. Theory Ser. A, 60(1):50–66, 1992.DOI
  5. [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. [6]Henrik Eriksson. Bulgarisk patiens. Elementa, 64(4):186–188, 1981.
  7. [7]Henrik Eriksson and Markus Jonsson. Level sizes of the Bulgarian solitaire game tree. Fibonacci Quart., 55(3):243–251, 2017.
  8. [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. [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. [10]Gwihen Etienne. Tableaux de Young et solitaire bulgare. J. Combin. Theory Ser. A, 58(2):181–197, 1991.
  11. [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. [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. [13]A. J. Harris and Son Nguyen. Bulgarian solitaire: a new representation for depth generating functions. Australas. J. Combin., 93:224–273, 2025.
  14. [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. [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. [16]Brian Hopkins. 30 years of Bulgarian solitaire. College Math. J., 43(2):135–140, 2012.
  17. [17]Brian Hopkins. Henrik Eriksson’s Bulgarian solitaire variant. Integers, 24A:Paper No. A9, 14, 2024.
  18. [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. [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. [20]Kiyoshi Igusa. Solution of the Bulgarian solitaire conjecture. Math. Mag., 58(5):259–271, 1985.DOI
  21. [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. [22]Jeffrey S. Olson. Variants of Bulgarian solitaire. Integers, 16:Paper No. A8, 11, 2016.DOI
  23. [23]Nhung Pham. Limiting behavior in growth of Bulgarian solitaire orbits. Integers, 23:Paper No. A58, 25, 2023.arxiv.org/abs/2208.14496
  24. [24]Serguei Popov. Random Bulgarian solitaire. Random Structures Algorithms, 27(3):310–330, 2005.DOI
  25. [25]A. L. Toom. Problem solution M655. Kvant, 12(7):28–30, 1981.
  26. [26]Yeong Nan Yeh. A remarkable endofunction involving compositions. Stud. Appl. Math., 95(4):419–432, 1995.DOI

Paper details

vlnc:W_xx7gaxk4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents