Conjugating cyclic $n$-color compositions

Hopkins, Brian; Barrón, Jesús Sistos; Wang, Hua

doi:10.61091/um122-04

Abstract

References

Utilitas Mathematica

Volume 122
Pages: 53-64

Research article

Conjugating cyclic $n$ -color compositions

^¹, ^², ^³

¹Department of Mathematics and Statistics, Saint Peter’s University, Jersey City NJ 07306 USA

²Department of Mathematics, University of Georgia, Athens GA 30602 USA

³Department of Mathematical Sciences, Georgia Southern University, Statesboro GA 30458 USA

Received: 21/02/2025
Accepted: 04/03/2025
Published Online: 22/03/2025

Copyright Link
License

Abstract

MacMahon extensively studied integer compositions, including the notion of conjugation. More recently, Agarwal introduced $n$ -color compositions and their cyclic versions were considered by Gibson, Gray, and Wang. In this paper, we develop and study a conjugation rule for cyclic $n$ -color compositions. Also, for fixed $ℓ$ , we identify and enumerate the subset of self-conjugate compositions of $ℓ$ , as well as establish a bijection between these and the set of cyclic regular compositions of $ℓ$ with only odd parts.

Keywords: integer compositions, n-color compositions, cyclic compositions, conjugation, combinatorial proofs

1. Introduction

A composition is an ordered list of positive integers $υ = (p_{1}, \dots, p_{m})$ . Each of the numbers $p_{i}$ in the list is called a part of size $p_{i}$ of the composition. The sum of all the parts is called the weight of the composition, and the number of parts (denoted $| υ |$ ) is called its length. We say $υ$ is a composition of $ℓ$ (with $m$ parts) if it has weight $ℓ$ and length $m$ . For any $ℓ$ , we use $C (ℓ)$ to refer to the set of regular compositions of $ℓ$ , writing $C (ℓ, k)$ if we also want to specify the number of parts.

Agarwal [1] introduced the concept of $n$ -color compositions. An $n$ -color composition is a composition in which a part of size $s$ can be in one of $s$ different colors, which are usually represented by numbered subscripts. For example, $(3_{2}, 4_{3}, 1_{1})$ is a $n$ -color composition of $8$ with $3$ parts. We define $C C (ℓ)$ and $C C (ℓ, k)$ analogously to the sets for regular compositions.

A well-known graphical representation of compositions is through tilings. The scheme of spotted tilings for $n$ -color compositions was introduced by the first named author [8]. A part $k_{i}$ is represented by a $1 \times k$ tile with a spot marked on the $i$ th square, as shown in Figure 1. This differs from the spotless tiling that is used for regular compositions.

Figure 1 Tiling representation of the regular composition $(3, 2, 2, 1)$ , and spotted tiling representation of the $n$ -color composition $(3_{2}, 2_{1}, 2_{2}, 1_{1})$ .

For both cases, we also have the notion of cyclic compositions, in which we consider the parts as being arranged around a circle, considering two arrangements the same if one can be obtained by rotating the other. Regular cyclic compositions were introduced by Sommerville [12] in 1909, while the $n$ -color case was treated by Gibson, Gray, and the third named author [6] in 2018. If $υ$ is a composition, then the cyclic composition corresponding to it is denoted by ${[υ]}_{}$ . The sets of regular and $n$ -color cyclic compositions are denoted, respectively, by ${[C (ℓ)]}_{}$ and ${[C C (ℓ)]}_{}$ . The graphical tilings can be easily extended to represent these cyclic arrangements, as shown in Figure 2.

Figure 2 Tilings for the cyclic compositions $[(3, 2, 2, 1)]$ and $[(3_{2}, 2_{1}, 2_{2}, 1_{1})]$ .

MacMahon [10] introduced conjugation for regular compositions. We will present alternative representations of $n$ -color compositions and cyclic $n$ -color compositions that will allow us to define conjugations on the cyclic version of these compositions, and address related combinatorial questions. An equivalent transformation was recently studied by Bowman [4] as a consequence of certain bijections between different sets of compositions. Our approach builds this map from the context of conjugation and helps to better understand that transformation.

The spotted tilings will be helpful for visualizing connections between regular and $n$ -color compositions. In Section 2, we introduce three elementary transformations on compositions and study the relationships between them. In Section 3, we define the conjugation map and also count the number of self-conjugate cyclic $n$ -color compositions. In Section 4, we highlight two properties of the sequence counting these compositions and establish a connection to certain regular cyclic compositions. Section 5 briefly discusses the limitations of expanding this conjugation of cyclic $n$ -color compositions to standard $n$ -color compositions. This work is largely from the undergraduate honors thesis of the second named author [2].

2. Preliminaries

2.1. A connection with regular compositions

We associate to an $n$ -color composition $σ$ a length $2 | σ |$ regular composition which we call the expanded form of the composition. These expanded forms can be visualized through their corresponding tilings, as follows:

(a) Starting with an spotted tiling, replace every spotted cell with a pair of consecutive spotted cells.

(b) Next, in each of these pairs, remove the spots and add a barrier in the middle.

This results in the tiling of a valid regular composition. An example is given in Figure 3. To reverse this process, simply add a spot to the cells adjacent to every other barrier (starting with the second one) and then merge each pair of adjacent spotted cells into one, removing the barriers in the process.

Figure 3 The expanded form of $(3_{2}, 5_{4}, 1_{1})$ is $(2, 2, 4, 2, 1, 1)$ .

Similar representations have been studied in previous work: This a slight modification from the $c$ -blocks and tails introduced by the first and third named authors [7], but here we do not allow the tails to be empty. It is easy to see that the above map introduces a bijection between these compositions, formally stated in Lemma 2.1.

Lemma 2.1. There is a one-to-one correspondence between the $n$ -color compositions of $ℓ$ with $m$ parts and the regular compositions of $ℓ + m$ with $2 m$ parts.

Proof. The result is vacuously true when $ℓ < m$ since both sets are empty. If $ℓ \geq m$ , for any $n$ -color composition $σ \in C C (ℓ, m)$ , consider the transformation $E$ that turns each of the colored parts $s_{c}$ (where $1 \leq c \leq s$ ) into ordered pairs of numbers $(c, s + 1 - c)$ . The resulting list, obtained by concatenating each of the pairs (in the same order), is a valid regular composition, because both $c$ and $s + 1 - c$ are positive integers. Furthermore, the length of the new list is double that of the original. And since $c + (s + 1 - c) = s + 1$ , the weight of the resulting composition will be $ℓ + m$ .

The map $E$ is a bijection because it has a straightforward inverse $E^{- 1}$ : Starting with a composition $υ \in C (ℓ + m, 2 m)$ , we generate an $n$ -color composition by turning each successive pair of parts $(a, b)$ into a colored part $S_{a}$ where $S = a + b - 1$ .

It is natural to wonder about the expanded form of cyclic $n$ -color compositions. To answer this, we study another transformation on compositions.

2.2. The shifts of a composition

If $υ = (p_{1}, p_{2}, \dots, p_{k})$ we define its shift $S^{} (υ)$ , as the composition $(p_{k}, p_{1}, \dots, p_{k - 1})$ . We use exponent notation $S^{r} (υ)$ to denote repeated shifts. This map is invertible, so the notation makes sense for any integer $r$ . For example, given $σ = (2, 3, 5, 2, 2)$ , we have $S^{} (σ) = (2, 2, 3, 5, 2), S^{- 1} (σ) = (3, 5, 2, 2, 2) = S^{4} (σ), S^{3} (σ) = (5, 2, 2, 2, 3) .$ The interaction between $S^{}$ and $E$ is straightforward. Because each part in the $n$ -color composition corresponds to two parts in the expanded form, we have the following.

Proposition 2.2. Let $σ$ be an $n$ -color composition. Then $E (S^{} (σ)) = S^{2} (E (σ))$ .

Proof. Let $P_{C}$ be the last part of $σ$ and let $ω$ be the composition left after removing this last part from $σ$ , i.e., $σ = (ω, P_{C})$ and $S^{} (σ) = (P_{C}, ω)$ . The respective expansions are $E (σ) = (E (ω), C, P - C + 1) and E (S^{} (σ)) = (C, P - C + 1, E (ω)),$ thus $E (S^{} (σ)) = S^{2} (E (σ))$ .

Shifts provide a formal way to work with cyclic compositions. We consider $υ$ and $τ$ to be related (written $υ \overset{}{\sim} τ$ ) if there is an integer $r$ such that $υ = S^{r} (τ)$ . It is easy to verify that this is an equivalence relation and cyclic compositions formally correspond to equivalence classes. In a similar fashion, we say $υ \overset{2}{\sim} τ$ if there is an integer $r$ such that $υ = S^{2 r} (τ)$ (that is, if $υ$ can be obtained by shifting $τ$ an even number of times). Once again, this is an equivalence relationship. We denote the corresponding equivalence classes by $2$ -cyclic compositions, writing ${[υ]}_{2}$ for the $2$ -cyclic composition that contains $υ$ .

From Proposition 2.2 we deduce that a cyclic $n$ -color composition ${[σ]}_{}$ corresponds exactly to ${[E (σ)]}_{2}$ , a $2$ -cyclic composition of expanded forms, which we call the cyclic expanded form of ${[σ]}_{}$ .

Lemma 2.3. Let $σ, ω$ be $n$ -color compositions. Then, $σ \overset{}{\sim} ω$ if and only if $E (σ) \overset{2}{\sim} E (ω)$ .

Proof. The assertion $σ \overset{}{\sim} ω$ is true if and only if $σ = S^{r} (ω)$ for some integer $r$ , which in turn occurs if and only if $E (σ) = S^{2 r} (E (ω))$ . That is, if and only if $E (σ) \overset{2}{\sim} E (ω)$ .

Figure 4 The expanded form of a cyclic $n$ -color composition is a regular $2$ -cyclic composition.

Graphically, the cyclic expanded forms can be understood as cyclic tilings in which there are two types of alternating barriers between the parts, as shown on Figure 4. One of these types corresponds to the usual barriers, but the second type arises from the spotted squares.

2.3. On primitive compositions

In this section, we review properties of primitive compositions studied by Lothaire [9]. Primitive compositions prove to be a useful tool when studying cyclic compositions. These results are used by Flajolet and Soria [5] to obtain generating functions for general classes of cyclic compositions. Most of the statements shown here apply to both regular and $n$ -color compositions.

We say a composition is primitive if it is not the repeated self-concatenation of another composition. That is, $υ$ is primitive if and only if $υ \neq τ^{t}$ for some other composition $τ$ and an integer $t > 1$ . For example, the composition $(1, 2, 3, 2)$ is primitive, but the composition $(1, 2, 1, 2, 1, 2) = (1, 2)^{3}$ is not. For every $υ$ , there is exactly one primitive composition $τ$ such that $υ = τ^{t}$ , called the primitive of $υ$ , and denoted by $(υ)$ . In this case, we have $(1, 2, 1, 2, 1, 2) = (1, 2)$ . Notice that, while $(1, 2)$ is a composition of $3$ with $2$ parts, the list $(1, 2, 1, 2, 1, 2)$ is a composition of $9$ with $6$ parts. In general, we have the following.

Proposition 2.4. Let $υ, τ$ be compositions such that $υ = τ^{t}$ for some positive integer $t$ . The weight and length of $υ$ are, respectively, $t$ times the weight and length of $τ$ .

In particular, for any composition $υ$ , the weight and length of $(υ)$ are divisors of the respective quantities in $υ$ . Now, notice that for all $υ$ we have $S^{| υ |} (υ) = υ$ . For example, the length of $(1, 2, 3)$ is $3$ , and indeed $S^{3} ((1, 2, 3)) = (1, 2, 3)$ . We have $υ$ is primitive if and only if $| υ |$ is the smallest positive integer that satisfies this.

Proposition 2.5(Prop. 1.3.2, [9]). Let $r$ be an integer. A composition $υ$ is primitive if and only if $S^{r} (υ) = υ$ implies $r \equiv 0 (\mod | υ |)$ .

How does the map sending compositions to their primitives interact with the expanding and shifting transformations? First, if $υ, τ$ are compositions, then $υ = τ^{t}$ if and only if for any integer $r$ we have $S^{r} (υ) = (S^{r} (τ))^{t} .$ In particular, we have the following.

Proposition 2.6 (Prop. 1.3.3,[9]). If $υ = S^{r} (τ)$ , then $(υ) = S^{r} ((τ))$ .

Second, the expansion map $E$ (only defined for $n$ -color compositions) commutes with the process of self-concatenation.

Proposition 2.7. Let $σ, ω$ be $n$ -color compositions. We have $σ = ω^{t}$ if and only if $E (σ) = (E (ω))^{t}$ .

Proof. The result is trivial when $t = 1$ since then $σ = ω$ . The rest of the proof follows by induction. Namely, if this is true for a given $t$ , we must have $σ = ω^{t + 1} = (ω^{t}, ω)$ if and only if $E (σ) = (E (ω)^{t}, E (ω)) = (E (ω))^{t + 1}$ .

As a corollary, if an expanded form $E (σ)$ is primitive, then the original composition $σ$ must be primitive as well.

3. A conjugation map

From the graphical depiction of the cyclic expanded forms, we deduce a straightforward conjugation rule that works for all cyclic $n$ -color compositions. Namely, flipping the roles of the alternating types of barriers produces the diagram of another cyclic expanded form, which corresponds to a cyclic composition of the same weight.

This can also be described directly from the spotted tilings. In Figure 6, observe that the number of barriers is exactly the same as the amount of marked spots: There is exactly one marked spot between two consecutive barriers, and vice versa. Thus, interchanging the marked spots and the barriers will produce the diagram of another valid cyclic $n$ -color composition. Moreover, doing this process twice returns the original composition. This interpretation was concurrently developed by Bowman [4].

Figure 5 A conjugation on the expanded forms of cyclic $n$-color compositions extends to a conjugation on the cyclic compositions themselves.

Figure 6 The conjugate of $[1_{1}, 3_{2}, 5_{4}]$ is the composition $[2_{2}, 2_{1}, 5_{2}]$ .

Formally, this is just the map $C = E^{- 1} \circ S^{} \circ E$ that transforms cyclic $n$ -color compositions by expanding, shifting (thus inverting the roles of all barriers), and contracting the $n$ -color composition back into another of the same weight. Recall that $[C C (ℓ)]$ is the set of cyclic $n$ -color compositions of weight $ℓ$ .

Theorem 3.1. The map $C$ is an involution on $[C C (ℓ)]$ .

Proof. Notice that applying $C$ twice to an $n$ -color composition $σ$ returns the $n$ -color composition $σ^{'} = E^{- 1} \circ S^{2} \circ E (σ)$ , whose expanded form is $E (σ^{'}) = S^{2} (E (σ))$ . From here, $E (σ^{'}) \overset{2}{\sim} E (σ)$ , and thus ${[σ^{'}]}_{} = {[σ]}_{}$ as guaranteed by Lemma 2.3.

A natural question now is whether there are compositions for which the conjugation $C$ acts as the identity map. That is, whether there are self-conjugate cyclic $n$ -color compositions. In this section, we characterize and count such compositions of a fixed weight.

We begin by noting that, when fixing the weight, there is a one-to-one correspondence between $2$ -cyclic compositions and their primitives:

Proposition 3.2. Let $υ, τ$ be two compositions of equal weight. Then, $υ \overset{2}{\sim} τ$ if and only if $(υ) \overset{2}{\sim} (τ)$ .

This follows from Proposition 2.6.

We are now able to characterize the set of self-conjugate cyclic $n$ -color compositions.

Theorem 3.3. A cyclic $n$ -color composition ${[σ]}_{}$ is self-conjugate if and only if $(E (σ))$ has odd length.

Proof. Assume first that ${[σ]}_{}$ is self-conjugate. That is, $σ \overset{}{\sim} E^{- 1} \circ S^{} \circ E (σ)$ . From the relationship between $n$ -color compositions and their expanded forms given by Lemma 2.3, $E (σ) \overset{2}{\sim} S^{} (E (σ))$ . In turn, $(E (σ)) \overset{2}{\sim} (S^{} (E (σ)))$ by Proposition 3.2. But by Proposition 2.6, $(S^{} (E (σ))) = S^{} ((E (σ)))$ , so $(E (σ)) \overset{2}{\sim} S^{} ((E (σ)))$ . Thus, there is an integer $r$ such that $(E (σ)) = S^{2 r} (S^{} ((E (σ)))) = S^{2 r + 1} ((E (σ))) .$

By Proposition 2.5, $2 r + 1 \equiv 0 mod | (E (σ)) |$ since $(E (σ))$ is primitive by definition. Since $2 r + 1$ is odd, its divisor $| (E (σ)) |$ must also be odd.

For the other direction, assume $L = | (E (σ)) |$ is odd. We can “split” the shift $(E (σ)) = S^{L} ((E (σ)))$ in two: $(E (σ)) = S^{L - 1} (S^{} ((E (σ)))) .$

Because $L - 1$ is even, $(E (σ)) \overset{2}{\sim} S^{} ((E (σ)))$ . Equivalently, by Proposition 2.6, $(E (σ)) \overset{2}{\sim} (S^{} (E (σ))) .$

Finally, from Proposition 3.2, $E (σ) \overset{2}{\sim} S^{} (E (σ))$ and then Lemma 2.3 implies $σ \overset{}{\sim} E^{- 1} \circ S^{} \circ E (σ)$ , i.e., ${[σ]}_{}$ is self-conjugate.

For example, consider the cyclic $n$ -color composition $ρ = [(4_{1}, 6_{2}, 3_{3}, 5_{4}, 7_{5})]$ . Note that $E (ρ) = (1, 4, 2, 5, 3, 1, 4, 2, 5, 3) = (1, 4, 2, 5, 3)^{2} .$ Since $(ρ)$ has odd length, $ρ$ is self-conjugate by Theorem 3.3; see Figure 7.

Figure 7 An example of a self-conjugate cyclic $n$ -color composition.

By the definition of primitive composition, any $n$ -color composition $σ$ has $σ = (σ)^{s}$ for some integer $s$ . Applying Proposition 2.7 to $σ$ and $(σ)^{s}$ shows $E (σ) = E ((σ))^{t}$ for some integer $t$ . As powers of the same word, $(E (σ)) = (E ((σ))$ . We record these ideas in the following corollary.

Corollary 3.4. If ${[σ]}_{}$ is self-conjugate, then ${[(σ)]}_{}$ is also self-conjugate, and so is any composition of the form ${[(σ)^{t}]}_{}$ , where $t$ is an integer.

Our next goal is enumerating self-conjugate cyclic $n$ -color compositions. It is actually easier to count the complementary set, the compositions whose expanded form has even length (i.e., those that are not self-conjugate).

We first analyze the case of primitive compositions, and then extrapolate to non-primitive cases. In the next lemma we show that being both primitive and self-conjugate determines the behavior of the expanded form.

Lemma 3.5. Let $σ$ be a primitive $n$ -color composition. The primitive of $E (σ)$ is either $E (σ)$ itself or its exact half, that is, $E (σ) = (E (σ))^{2}$ . Moreover, the cyclic $n$ -color composition ${[σ]}_{}$ is self-conjugate if and only if it falls in the latter case.

Proof. By definition of the primitive composition, $E (σ) = (E (σ))^{t}$ for some integer $t$ . We need to show $t$ is either $1$ or $2$ . By Proposition 2.4, the length of $E (σ)$ is $t$ times that of $(E (σ))$ . There are two cases based on the parity of $t$ .

If $t$ is odd, since $| E (σ) |$ is even, $| (E (σ)) |$ is also even. But if the length of $(E (σ))$ is even, then $(E (σ))$ is the expanded form of some other $n$ -color composition $ψ$ . That is, $(E (σ)) = E (ω)$ for some other $n$ -color composition $ψ$ . By Proposition 2.7, undoing the expansion yields $σ = ψ^{t}$ which implies $t = 1$ because $σ$ is primitive.

If $t$ is even, say $t = 2 k$ for some integer $k$ , then we can define $υ = (E (σ))^{2}$ so that $E (σ) = υ^{k}$ . The length of $υ$ is even, being twice the length of $(E (σ))$ . So, as above, there is an $n$ -color composition $ω$ such that $υ = E (ω)$ . That is, $E (σ) = (E (ω))^{k}$ and by, Proposition 2.7, $σ = ω^{k}$ , therefore $k = 1$ which gives $t = 2$ .

For the second claim, note that a primitive self-conjugate cyclic $n$ -color composition ${[σ]}_{}$ cannot have $E (σ)$ also primitive, else the length of this primitive expanded form would be even, contradicting Theorem 3.3. In other words, if ${[σ]}_{}$ is self-conjugate, then $E (σ) = (E (σ))^{2}$ . We saw above that $(E (σ))$ having even length (that is, ${[σ]}_{}$ not being self-conjugate) means $E (σ) = (E (σ))$ .

In other words, for $σ$ primitive, ${[σ]}_{}$ is not self-conjugate if and only if $E (σ)$ is also primitive. We also know $E (σ)$ can only be primitive when $σ$ is also primitive. Thus, counting the number of primitive non-self-conjugate cyclic $n$ -color compositions reduces to counting the number of primitive expanded forms for a given weight $ℓ$ . Write $C_{p r i m} (ℓ, m)$ for the number of primitive (regular) compositions of $ℓ$ with $m$ parts.

Theorem 3.6. The number of self-conjugate cyclic $n$ -color compositions of $ℓ$ is ${[C C (ℓ)]}_{}_{s e l f} = {[C C (ℓ)]}_{} - \sum_{k | ℓ} \sum_{p = 1}^{k} \frac{1}{p} C_{p r i m} (k + p, 2 p) .$

Proof. Recall that the expanded form of an $n$ -color composition of weight $k$ and length $p$ is a regular composition with weight $k + p$ and length $2 p$ . For fixed $k$ , summing for possible values of $p$ (from $1$ to $k$ ) gives the number of primitive expanded forms. That is, writing $A (k)$ for the number of primitive $n$ -color compositions of $k$ whose expanded form is also primitive, $A (k) = \sum_{p = 1}^{k} C_{p r i m} (k + p, 2 p) .$

Let ${[A (k)]}_{}$ be the number of non-self-conjugate primitive cyclic $n$ -color compositions of a given weight $k$ . Primitive expanded forms in the same $2$ -cyclic composition correspond with the same non-self-conjugate cycle, but by Proposition 2.5, a primitive expanded form with length $2 p$ has exactly $p$ even shifts. Therefore, ${[A (k)]}_{} = \sum_{p = 1}^{k} \frac{1}{p} C_{p r i m} (k + p, 2 p) .$

To complete the proof, we need an expression applicable to all compositions, not just the primitive ones. Since fixing the weight $ℓ$ causes a one-to-one relationship between compositions and their primitives, we simply carry out an additional sum of primitive compositions across all divisors $k$ of $ℓ$ . Writing ${[B (ℓ)]}_{}$ for the number of non-self-conjugate cyclic $n$ -color compositions of a given weight $ℓ$ , we have ${[B (ℓ)]}_{} = \sum_{k | ℓ} {[A (k)]}_{} = \sum_{k | ℓ} \sum_{p = 1}^{k} \frac{1}{p} C_{p r i m} (k + p, 2 p) .$

The total number of self-conjugate cyclic $n$ -color compositions of $ℓ$ is then ${[C C (ℓ)]}_{} - {[B (ℓ)]}_{}$ , as discussed earlier.

Table 1 gives the first few values of ${[C C (ℓ)]}_{}_{s e l f}$ which is now listed in the OEIS [11, A365859].

\begin{array}{cccc} ℓ & [C C (ℓ)]_{self} & ℓ & [C C (ℓ)]_{self} \\ 1 & 1 & 11 & 19 \\ 2 & 1 & 12 & 2 \\ 3 & 2 & 13 & 41 \\ 4 & 1 & 14 & 5 \\ 5 & 3 & 15 & 94 \\ 6 & 2 & 16 & 1 \\ 7 & 5 & 17 & 211 \\ 8 & 1 & 18 & 10 \\ 9 & 10 & 19 & 493 \\ 10 & 3 & 20 & 3 \end{array}

4. On the sequence of self-conjugate cyclic $n$ -color compositions

The data of Table 1 suggest some general results: Through $n = 16$ , it appears that $[C C (2^{k})]_{s e l f} = 1$ . Also, it seems that $[C C (2 ℓ)]_{s e l f} = [C C (ℓ)]_{s e l f}$ for all $ℓ$ . We will prove that these results hold in general.

First, we establish a consequence of Lemma 3.5.

Corollary 4.1. For even $ℓ$ , there are no primitive self-conjugate cyclic compositions of $ℓ$ .

Proof. We show that for any primitive composition $σ$ of $ℓ$ , the corresponding cyclic composition ${[σ]}_{}$ cannot be self-conjugate. By Lemma 3.5 and Proposition 2.4, we have $| E (σ) | = k | (E (σ)) |$ where $k$ is either $1$ or $2$ . In any case, $\frac{2}{k}$ is an integer. Now, from Lemma 2.1 we have $| E (σ) | = 2 | σ |$ . Thus, $| (E (σ)) | = \frac{2}{k} | σ |$ .

Lemma 2.1 also shows that the length of $σ$ is $| E (σ) | - ℓ$ . Because $ℓ$ is even, $| σ |$ must also be even. Therefore, $| (E (σ)) |$ is also even since it is a multiple of $| σ |$ . Therefore, ${[σ]}_{}$ cannot be self-conjugate.

With this, we can establish the patterns observed in Table 1.

Theorem 4.2. Given $ℓ$ a positive integer, ${[C C (2 ℓ)]}_{}_{s e l f} = {[C C (ℓ)]}_{}_{s e l f}$ .

Proof. We establish a bijection between the two sets of self-conjugate compositions.

Let ${[σ]}_{}$ be a self-conjugate cyclic $n$ -color composition of $ℓ$ . The composition ${[σ^{2}]}_{}$ is then a cyclic $n$ -color composition of $2 ℓ$ which is also self-conjugate by Corollary 3.4. This transformation is one-to-one because $σ^{2} = ω^{2}$ if and only if $σ = ω$ .

For the reverse map, let ${[ω]}_{}$ be a self-conjugate cyclic $n$ -color composition of $2 ℓ$ . By Corollary 4.1, $ω$ cannot be primitive. However, ${[(ω)]}_{}$ is also self-conjugate by Corollary 3.4 and it has an odd weight $w$ which divides $2 ℓ$ by Proposition 2.4. Any odd divisor of $2 ℓ$ is also a divisor of $ℓ$ . Thus, there is an integer $q$ such that ${[(ω)^{q}]}_{}$ is a composition of $ℓ$ which, again by Corollary 3.4, is self-conjugate. Notice that $ω = (ω)^{2 q}$ , so this mapping is the inverse of the previous one.

The result for powers of 2 then follows from $[C C (1)]_{s e l f} = 1$ .

Another consequence of Theorem 4.2 is that the subsequence of Table 1 from odd $ℓ$ values determines the entire sequence. This bisection is also in the OEIS [11,A365858] as the number of regular cyclic compositions with only odd parts. We use expanded forms to establish a bijection between these types of compositions.

Theorem 4.3. Let $ℓ$ be an odd integer, and $m \leq ℓ$ . The number of self-conjugate cyclic $n$ -color compositions of $ℓ$ with $m$ parts is the same as the number of cyclic regular compositions of $ℓ$ with $m$ parts in which all parts are odd.

Proof. Let ${[σ]}_{}$ be a self-conjugate cyclic $n$ -color composition of $ℓ$ with $m$ parts. We know $E (σ)$ has $2 m$ parts and, since ${[σ]}_{}$ is self-conjugate, $(E (σ))$ has an odd length.

The length of $(E (σ))$ must be an odd divisor of the length of $E (σ)$ by Proposition 2.4. As in the proof of Theorem 4.2, this means we halve $E (σ)$ , i.e., there exists a regular composition $υ$ such that $E (σ) = υ^{2}$ . Since $E (σ)$ has weight $ℓ + m$ and length $2 m$ , then $υ$ must be a composition of $\frac{ℓ + m}{2}$ with $m$ parts (note that, because $ℓ$ is odd, $m$ must also be odd). Now consider the list $τ$ obtained by replacing each part $p$ of $υ$ by $2 p - 1$ . The weight of the resulting composition is $2 \cdot \frac{ℓ + m}{2} - m = ℓ$ , as claimed.

This correspondence is invertible because, starting with $τ$ , we can build the composition $υ$ , in which each part $2 p - 1$ is changed to $p$ , and then form an expanded form $υ^{2}$ corresponding to an $n$ -color composition $σ = E^{- 1} (υ^{2})$ . To see that ${[σ]}_{}$ is self-conjugate, notice that $(E (σ)) = (υ)$ . By Proposition 2.4, the length of $(υ)$ is a divisor of $| υ | = | τ |$ . But by parity, $τ$ has an odd length since it is a composition of an odd integer with only odd parts. Hence, the length of $(υ)$ is necessarily odd, which implies that ${[σ]}_{}$ is self-conjugate by Theorem 3.3.

We are left to show $σ \overset{}{\sim} ω$ if and only if $τ_{σ} \overset{}{\sim} τ_{ω}$ , so that the map sending ${[σ]}_{}$ to ${[τ_{σ}]}_{}$ is not only well-defined but also a bijection. By Lemma 2.3, $σ \overset{}{\sim} ω$ if and only if $τ_{σ} \overset{2}{\sim} τ_{ω}$ . We know $τ_{σ}$ and $τ_{ω}$ both have odd length. For compositions of odd length $m$ , even and odd shifts are equivalent: If $υ = S^{r} (τ)$ , then $υ = S^{r + m} (τ)$ . Thus, $τ_{σ} \overset{2}{\sim} τ_{ω}$ if and only if $τ_{σ} \overset{}{\sim} τ_{ω}$ .

For example, consider again the cyclic $n$ -color composition $[4_{1}, 6_{2}, 3_{3}, 5_{4}, 7_{5}]$ of Figure 7 with weight $25$ and $5$ parts which is also self-conjugate. Disregarding the cyclic structure, we can split the expanded form $(1, 4, 2, 5, 3, 1, 4, 2, 5, 3)$ into two copies of $(1, 4, 2, 5, 3)$ . Taking $1$ from each part in the second copy leaves $(1, 4, 2, 5, 3)$ and $(0, 3, 1, 4, 2)$ . Adding these lists element-wise gives $(1, 7, 3, 9, 5)$ , a regular composition of $25$ with $5$ parts; see Figure 8.

Figure 8 Bijection between self-conjugate compositions and compositions with only odd parts.

5. Connection to balanced compositions

MacMahon defined conjugation for regular compositions and here we have defined conjugation for cyclic $n$ -color compositions. The first named author offered a notion of conjugation for $n$ -color compositions that unfortunately only applies to a small subset [8]. The difference in the cyclic case is that the number of barriers equals the number of spots as described in Section 3. A definition of conjugation applicable to all $n$ -color compositions remains open.

In trying to address this problem, the second and third named authors studied balanced $n$ -color compositions which themselves have connections to many combinatorial objects [3]. The definition is based on the expanded form: An $n$ -color composition $σ$ is balanced if $s = E (σ)$ satisfies $\sum s_{2 k - 1} = \sum s_{2 k}$ . For example, $(1_{1}, 4_{3}, 2_{1}, 3_{2})$ is balanced because its expanded form $(1, 1, 3, 2, 1, 2, 2, 2)$ has $1 + 3 + 1 + 2 = 1 + 2 + 2 + 2$ .

We conclude with a connection between balanced $n$ -color compositions and the ideas studied here.

Proposition 5.1. For $σ \in C C (ℓ)$ , if ${[σ]}_{}$ is self-conjugate, then $E (σ)$ is balanced.

Proof. It suffices to show this for the primitive case. Let $E (σ) = (p_{1}, \dots, p_{2 m})$ . By Lemma 3.5, $E (σ) = (E (σ))^{2}$ and $m = | (E (σ)) |$ is odd. By Proposition 2.6, $S^{m} (E (σ)) = E (σ)$ . Hence, $p_{i} = p_{i + m}$ for $1 \leq i \leq m$ . Since $m$ is odd, this gives a natural matching between the even and odd indexed parts of $E (σ)$ so that $E (σ)$ is balanced.

Certainly the converse does not hold, as the previous example $(1_{1}, 4_{3}, 2_{1}, 3_{2})$ is balanced but one can verify that $[(1_{1}, 4_{3}, 2_{1}, 3_{2})]$ is not self-conjugate.

References:

A. Agarwal. n-colour compositions. Indian Journal of Pure and Applied Mathematics, 31:1421–1427, 2000.
J. S. Barrón. Counting conjugates of colored compositions. Georgia Southern University Honors College Theses, 985, 2024. https://digitalcommons.georgiasouthern.edu/honors-theses/985.
J. S. Barrón and H. Wang. Balanced n-color compositions. Integers, 24A:#A2, 2024.
J. Bowman. Compositions with an odd number of parts, and other congruences. Journal of Integer Sequences, 27:24.3.6, 2024.
P. Flajolet and M. Soria. The cycle construction. SIAM Journal on Discrete Mathematics, 4(1):58–60, 1991. https://doi.org/10.1137/0404006.
M. Gibson, D. Gray, and H. Wang. Combinatorics of n-color cyclic compositions. Discrete Mathematics, 341(11):3209–3226, 2018. https://doi.org/10.1016/j.disc.2018.08.001.
B. Hopkins. Spotted tilings and n-color compositions. Integers, 12B:#A6, 2012.
B. Hopkins and H. Wang. Restricted color n-color compositions. J. Comb., 12(2):355–377, 2021.

M. Lothaire. Combinatorics on Words, volume 17. Cambridge University Press, 1997.
P. MacMahon. Memoir on the compositions of numbers. Philosophical Transactions of the Royal Society A, 184:835–901, 1893.
Oeis foundation inc. The On-Line Encyclopedia of Integer Sequences, 2025. https://oeis.org.
D. Sommerville. On certain periodic properties of cyclic compositions of numbers. Proceedings of the London Mathematical Society, S2-7(1):263–313, 1909.

[1] A. Agarwal. n-colour compositions. Indian Journal of Pure and Applied Mathematics, 31:1421–1427, 2000.

[2] J. S. Barrón. Counting conjugates of colored compositions. Georgia Southern University Honors College Theses, 985, 2024. https://digitalcommons.georgiasouthern.edu/honors-theses/985.

[3] J. S. Barrón and H. Wang. Balanced n-color compositions. Integers, 24A:#A2, 2024.

[4] J. Bowman. Compositions with an odd number of parts, and other congruences. Journal of Integer Sequences, 27:24.3.6, 2024.

[5] P. Flajolet and M. Soria. The cycle construction. SIAM Journal on Discrete Mathematics, 4(1):58–60, 1991. https://doi.org/10.1137/0404006.

[6] M. Gibson, D. Gray, and H. Wang. Combinatorics of n-color cyclic compositions. Discrete Mathematics, 341(11):3209–3226, 2018. https://doi.org/10.1016/j.disc.2018.08.001.

[7] B. Hopkins. Spotted tilings and n-color compositions. Integers, 12B:#A6, 2012.

[8] B. Hopkins and H. Wang. Restricted color n-color compositions. J. Comb., 12(2):355–377, 2021.

Contents

Utilitas Mathematica