Arndt Compositions with Restricted Parts, Palindromes, and Colored Variants

Mohammed L. Nadji

LMAM Laboratory and RECITS Laboratory

Faculty of Mathematics

University of Science and Technology Houari Boumediene Algiers Algeria

m.nadji@usthb.dz

Moussa Ahmia LMAM Laboratory

Department of Mathematics University of Mohamed Seddik Benyahia

BP 98 Ouled Aissa Jijel 18000 Algeria

moussa.ahmia@univ-jijel.dz

Daniel F. Checa and José L. Ramírez

Departamento de Matemáticas Universidad Nacional de Colombia

Bogotá Colombia

dcheca@unal.edu.co
jlramirezr@unal.edu.co

Abstract An Arndt composition of a positive integer is one where there is a descent from each odd-indexed part to its successor. In 2013, Jörg Arndt noted that this family of compositions is enumerated by the Fibonacci numbers. In this paper, we study Arndt compositions with restricted parts. We derive generating functions to count parameters such as the weight and the number of parts. We establish connections with the Padovan and Narayana’s cows sequences. Additionally, we enumerate the palindromic Arndt compositions. Finally, we introduce the concept of n-color Arndt compositions and proceed to enumerate them with respect to the weight and the number of parts.

1 Introduction

A composition of a positive integer n is a sequence of positive integers σ = (σ_{1}, σ_{2}, …, σ_{ℓ}) such that σ_{1} + σ_{2} + ⋯ + σ_{ℓ} = n. The integers σ_{i} are called parts of the composition, and n is referred to as the weight of σ and is denoted by |σ|. For example, the compositions of 3 are (3), (2, 1), (1, 2), (1, 1, 1). It is well-known that the number of compositions of n is 2^{n−1} for all n ≥ 1. The enumeration of compositions with respect to some parameters, such as the number of parts, the last part, the number of peaks, the number of fixed points, etc., is a classical problem in enumerative combinatorics. For more information on the combinatorics of compositions, we refer the reader to the book of Heubach and Mansour [12].

In this paper, we study a new family of integer compositions defined from a restriction on pairwise descending components. Specifically, an Arndt composition of a positive integer n is defined as a composition σ = (σ_{1}, σ_{2}, …, σ_{ℓ}) with a total weight of n, wherein the condition σ_{2i−1} > σ_{2i} is satisfied for each positive integer i, 2i ≤ ℓ. The name of this family of compositions honors Jörg Arndt, who observed that the number of these compositions is given by the well-known Fibonacci sequence F_{n}; see the comments of the sequence \underline{A000045} in the On-Line Encyclopedia of Integer Sequences (OEIS) [18]. Recall that Fibonacci sequence is defined by F_{n} = F_{n−1} + F_{n−2} for n ≥ 2, with the initial conditions F_{0} = 0 and F_{1} = 1.

The first combinatorial results on Arndt compositions come from the work of Hopkins and Tangboonduangjit [14, 15], where the authors provided the proof of the observation made by Arndt. Recently, Checa and Ramírez [8] conducted a detailed study of Arndt compositions through the use of generating functions. They also establish connections with the reduced anti-palindromic compositions introduced in 2022 by Andrews, Just, and Simay [5]. Continuing along this line, Prodinger [19] merged the concepts of Arndt compositions and Carlitz compositions, determining the associated generating function for the counting sequence of this new family of compositions.

In Section 2, we obtain the bivariate generating function for Arndt compositions with parts contained in a set S ⊆ ℕ with respect to the length and number of parts. It is noted that under certain restrictions, the number of Arndt compositions coincides with the Padovan and Narayana’s cows numbers. We provide algorithms to prove these coincidences. Additionally, we introduce a new combinatorial expression to calculate the number of Arndt compositions of length n with an even/odd number of parts.

In Section 3, we obtain the generating function for the number of palindromic Arndt compositions. We employ Flajolet and Prodinger’s adding-a-new slice technique (cf. [11]) to derive the generating function with respect to the length.

Finally, in Section 4, we introduce an n-color version of Arndt compositions following Agarwal [3].

2 Arndt compositions with restricted parts

Let A(n) denote the set of Arndt compositions of weight n, and let A = ⋃_{n≥0} A(n). We set A(0) = {ϵ}, where ϵ denotes the empty composition (weight zero). Hopkins and Tangboonduangjit [14] proved that |A(n)| = F_{n} for all n ≥ 0. For example, the Arndt compositions of 6 are

(6), (5, 1), (4, 2), (4, 1, 1), (3, 2, 1), (3, 1, 2), (2, 1, 3), (2, 1, 2, 1). (1)

We let parts(σ) denote the number of parts in a composition σ. Let a(n) and a(n, m) denote the number of Arndt compositions of n and the number of Arndt compositions of n with exactly m parts, respectively. It is clear that a(n) = ∑_{m≥1} a(n, m). We introduce a bivariate generating function to count the number of Arndt compositions with respect to the weight and number of parts:

A(x, y) := ∑_{σ∈A} x^{|σ|}y^{parts(σ)} = ∑_{n,m≥0} a(n, m)x^{n}y^{m}.

Checa and Ramírez [8, Theorem 1] derived the following generating function

A(x, y) = \frac{1 − x − x^{2} + x^{3} + xy − x^{3}y}{1 − x − x^{2} + x^{3} − x^{3}y^{2}}
= 1 + yx + yx^{2} + (y + y^{2})x^{3} + (y + y^{2} + y^{3})x^{4}
+ (y + 2y^{2} + 2y^{3})x^{5} + (y + 2y^{2} + 4y^{3} + y^{4})x^{6} + O(x^{7}).

The bold summand in the above series means that a(6, 1) = 1, a(6, 2) = 2, a(6, 3) = 4, and a(6, 4) = 1, consistent with the list (1).

2.1 Arndt compositions with parts from a set

In Theorem 1, we extend this result to Arndt compositions with parts from a non-empty given set S ⊆ ℕ. Let A_{S}(n) denote the set of Arndt compositions of n with parts in S, and let A_{S} = ⋃_{n≥0} A_{S}(n). We let a_{S}(n, m) denote the number of Arndt compositions of n with m parts in S and let a_{S}(n) := ∑_{m≥1} a_{S}(n, m). Analogously, we introduce the bivariate generating function

A_{S}(x, y) = ∑_{σ∈A_{S}} x^{|σ|}y^{parts(σ)} = ∑_{\begin{matrix}n∈S, \\ m≥0 \end{matrix}} a_{S}(n, m)x^{n}y^{m}.

Theorem 1. For S ⊆ ℕ, we have

A_{S}(x, y) = (1 + y ∑_{i∈S} x^{i}) ∑_{m≥0} ( ∑_{\begin{matrix}i,j∈S, \\ j<i \end{matrix}} x^{i+j})^{m} y^{2m}.  (2)

Proof. Let σ = (σ_{1}, σ_{2}) be an Arndt composition with two parts, such that σ_{1}, σ_{2} ∈ S and σ_{1} > σ_{2} ≥ min S. Let us suppose that σ_{1} = i ∈ S, then the bivariate generating function for this case is x^{i}y^{2} ∑_{j∈S,j<i} x^{j}. Summing over i ∈ S we have the series

∑_{\begin{matrix}i,j∈S, \\ j<i \end{matrix}} x^{i+j}y^{2}.

Finally, the generating function follows from the fact that Arndt compositions can be regarded as the concatenation of m pairs of parts (m ≥ 0), whose generating function is

∑_{m≥0} ( ∑_{\begin{matrix}i,j∈S, \\ j<i \end{matrix}} x^{i+j})^{m} y^{2m},

along with an additional part (which may be empty). This last part has generating function (1 + y ∑_{i∈S} x^{i}). Multiplying these two expressions yields the desired result.

For example, for S = {1, 2} we obtain the generating function of Arndt compositions in A_{{1,2}} with respect to the weight and number of parts:

A_{\{1,2\}}(x, y) = \frac{1 + (x + x^{2})y}{1 − x^{3}y^{2}}
= 1 + yx + yx^{2} + ⋯ + y^{2i}x^{3i} + y^{2i+1}x^{3i+1} + y^{2i+1}x^{3i+2} + · · · .

It is clear that a_{{1,2}}(n) = 1 for all n ≥ 1, because we have only one Arndt composition of each weight, that is,

A_{{1,2}} = {ϵ, (1), (2), (2, 1), (2, 1, 1), (2, 1, 2), (2, 1, 2, 1), (2, 1, 2, 1, 1), … }.

Similarly, for S = {1, 2, 3} we have

A_{{1,2,3}}(x, y) = (1 + y(x + x^{2} + x^{3})) ∑_{m≥0}(x^{3} + x^{4} + x^{5})^{m}y^{2m}

= \frac{1 + (x + x^{2} + x^{3})y}{1 − x^{3}y^{2} − x^{4}y^{2} − x^{5}y^{2}} .

As a series expansion, the generating function A_{{1,2,3}}(x, y) begins with

A_{{1,2,3}}(x, y) = 1 + yx + yx^{2} + (y + y^{2})x^{3} + (y^{2} + y^{3})x^{4} + (y^{2} + 2y^{3})x^{5} + (3y^{3} + y^{4})x^{6} + (2y^{3} + 2y^{4} + y^{5})x^{7} + (y^{3} + 3y^{4} + 3y^{5})x^{8} + O(x^{9}).

For example, Arndt compositions corresponding to the bold coefficient in the above series are

(3, 1, 3), (3, 2, 2), (3, 1, 2, 1), (2, 1, 3, 1), (2, 1, 2, 1, 1).

By letting y = 1, we see that the sequence a_{{1,2,3}}(n) begins 1, 1, 1, 2, 2, 3, 4, 5, 7. This appears to match the Padovan sequence defined by the recurrence relation P (n) = P (n−2)+P (n−3) for all n ≥ 3, with initial values P (0) = P (1) = P (2) = 1 (see [18, \underline{A000931}]). We establish this connection in the next theorem, giving what we believe to be a new combinational interpretation of the Padovan numbers.

Theorem 2. For all n ≥ 0,

a_{{1,2,3}}(n) = P (n).

Proof. We will define a bijection to establish the equality

A_{{1,2,3}}(n) = A_{{1,2,3}}(n − 2) ∪ A_{{1,2,3}}(n − 3).

Let σ = (σ_{1}, σ_{2}, …, σ_{k}) be an Arndt composition in the set A_{{1,2,3}}(n − 2), with n ≥ 2. We now associate σ with a composition in A_{{1,2,3}}(n) as follows:

σ → \begin{cases}(σ_{1}, σ_{2}, …, σ_{k}, 2), & if k is even; \\ (σ_{1}, σ_{2}, …, σ_{k}, 2), & if k is odd and σ_{k} = 3; \\ (σ_{1}, σ_{2}, …, σ_{k} + 1, 1), & if k is odd and σ_{k} ∈ \{1, 2\}. \end{cases}

Similarly, given a composition σ = (σ_{1}, σ_{2}, …, σ_{k}) ∈ A_{{1,2,3}}(n − 3), we associate σ with a composition in A_{{1,2,3}}(n) as follows:

σ → \begin{cases}(σ_{1}, σ_{2}, …, σ_{k}, 3), & if k is even; \\ (σ_{1}, σ_{2}, …, σ_{k}, 2, 1), & if k is odd and σ_{k} = 3; \\ (σ_{1}, σ_{2}, …, σ_{k} + 1, 1, 1), & if k is odd and σ_{k} ∈ \{1, 2\}. \end{cases}

This process is reversible, establishing a one-to-one correspondence between the sets. Therefore, a_{{1,2,3}}(n) satisfies the same recurrence relation of the Padovan sequence with the same initial values.

In Table 1, we provide an example of the algorithm described in the preceding proof.

A_{{1,2,3}}(10)  A_{{1,2,3}}(8) A_{{1,2,3}}(7)
(3, 2, 2, 1, 2)  (3, 2, 2, 1)
(3, 1, 3, 1, 2)  (3, 1, 3, 1)
(2, 1, 3, 2, 2)  (2, 1, 3, 2)
(3, 2, 3, 2)  (3, 2, 3)
(3, 1, 2, 1, 2, 1) (3, 1, 2, 1, 1)
(2, 1, 3, 1, 2, 1) (2, 1, 3, 1, 1)
(3, 1, 3, 2, 1)  (3, 1, 3)
(3, 2, 3, 1, 1)  (3, 2, 2)
(3, 1, 2, 1, 3)  (3, 1, 2, 1)
(2, 1, 3, 1, 3)  (2, 1, 3, 1)
(2, 1, 2, 1, 2, 1, 1)  (2, 1, 2, 1, 1)

Table 1: The n = 10 case of the bijection established in Theorem 2.

Open Problem 3. From a known identity for Padovan numbers, we have the equality

a_{\{1,2,3\}}(n) = ∑_{k=0}^{⌊(n+2)/2⌋} \binom{k}{n + 2 − 2k}, n ≥ 0.

As an open problem for the readers, we invite them to provide a combinatorial proof of this equality.

For S = {1, 2, 3, 4} we obtain the generating function

A_{\{1,2,3,4\}}(x, y) = \frac{1 + x(1 + x)(1 + x^{2})y}{1 − x^{3}(1 + x^{2})(1 + x + x^{2})y^{2}} .

As a series expansion, the generating function A_{{1,2,3,4}}(x, y) begins with

A_{{1,2,3,4}}(x, y) = 1 + yx + yx^{2} + (y + y^{2})x^{3} + (y + y^{2} + y^{3})x^{4} + (2y^{2} + 2y^{3})x^{5} + (y^{2} + 4y^{3} + y^{4})x^{6} + (y^{2} + 5y^{3} + 2y^{4} + y^{5})x^{7} + (5y^{3} + 5y^{4} + 3y^{5})x^{8} + O(x^{9}).

For example, Arndt compositions corresponding to the bold coefficient in the above series are

(4, 3), (4, 2, 1), (4, 1, 2), (2, 1, 4), (3, 1, 3), (3, 2, 2),
(3, 1, 2, 1), (2, 1, 3, 1), (2, 1, 2, 1, 1).

By letting y = 1, we see that the sequence a_{{1,2,3,4}}(n) begins 1, 1, 1, 2, 3, 4, 6, 9, 13, 19. This appears to match the Narayana’s cows sequence defined by the recurrence relation N(n) = N(n − 1) + N(n − 3) for all n ≥ 3, with the initial values N(0) = N(1) = N(2) = 1 (see [18, \underline{A000930}]). We establish this connection in the next theorem, giving what we believe to be a new combinational interpretation of the Narayana’s cows numbers.

Theorem 4. For all n ≥ 0,

a_{{1,2,3,4}}(n) = N(n).

Proof. We will define a bijection to establish the equality

A_{{1,2,3,4}}(n) = A_{{1,2,3,4}}(n − 1) ∪ A_{{1,2,3,4}}(n − 3).

Let σ = (σ_{1}, σ_{2}, …, σ_{k}) be an Arndt composition in the set A_{{1,2,3,4}}(n − 1), with n ≥ 1. We associate σ with a composition in A_{{1,2,3,4}}(n) as follows:

σ → \begin{cases}(σ_{1}, σ_{2}, …, σ_{k}, 1), & if k is even; \\ (σ_{1}, σ_{2}, …, σ_{k} + 1), & if k is odd and σ_{k} = 1; \\ (σ_{1}, σ_{2}, …, σ_{k}, 1), & if k is odd and σ_{k} ∈ \{2, 3, 4\}. \end{cases}

Similarly, given a composition σ = (σ_{1}, σ_{2}, …, σ_{k}) ∈ A_{{1,2,3,4}}(n − 3), we associate σ with a composition in A_{{1,2,3,4}}(n) as follows:

σ → \begin{cases}(σ_{1}, σ_{2}, …, σ_{k}, 3), & if k is even; \\ (σ_{1}, σ_{2}, …, σ_{k} + 3), & if k is odd and σ_{k} = 1; \\ (σ_{1}, σ_{2}, …, σ_{k} + 1, 2), & if k is odd and σ_{k} ∈ \{2, 3\}; \\ (σ_{1}, σ_{2}, …, σ_{k}, 3), & if k is odd and σ_{k} = 4. \end{cases}

This process is reversible, establishing a one-to-one correspondence between the sets. Therefore, a_{{1,2,3,4}}(n) satisfies the same recurrence relation of the Narayana’s cows sequence with the same initial values.

In Table 2, we provide an example of the algorithm described in the proof of Theorem 4.

Let ℓ be a positive integer. We let A_{ℓ} denote the set of Arndt compositions with largest part at most ℓ. Let A(x, y; ℓ) denote the bivariate generating function for compositions in A_{ℓ} respect to the number of parts and weight. From (2), by setting S = {1, 2, …, ℓ}, we obtain the following corollary.

Corollary 5. For ℓ ≥ 2 we have

A(x, y; ℓ) = \frac{(1 − x^{2})(1 − x + x(1 − x^{ℓ})y)}{1 − x^{2+2ℓ}y^{2} + x^{2+ℓ}(1 + x)y^{2} − x(1 + x + x^{2}(−1 + y^{2}))}.

Let a_{ℓ}(n) be the n-th coefficient of A(x, 1; ℓ). We have

A_{ℓ}(x) := A(x, 1; ℓ) = ∑_{n≥0} a_{ℓ}(n)x^{n} = \frac{1 − x^{2}}{1 − x − x^{2} + x^{ℓ+1}} .

In Table 3 we show the first few values of this sequence for ℓ = 3, 4, 5, 6. We provide the first combinatorial interpretations for the sequences with ℓ = 5 and ℓ = 6.

A_{{1,2,3,4}}(8) A_{{1,2,3,4}}(7) A_{{1,2,3,4}}(5)
(3, 1, 2, 1, 1) (3, 1, 2, 1)
(2, 1, 2, 1, 2) (2, 1, 2, 1, 1)
(4, 1, 2, 1)  (4, 1, 2)
(3, 2, 2, 1)  (3, 2, 2)
(4, 2, 2)  (4, 2, 1)
(2, 1, 3, 1, 1) (2, 1, 3, 1)
(3, 1, 3, 1)  (3, 1, 3)
(2, 1, 4, 1)  (2, 1, 4)
(4, 3, 1)  (4, 3)
(3, 1, 4)  (3, 1, 1)
(2, 1, 3, 2)  (2, 1, 2)
(4, 1, 3)  (4, 1)
(3, 2, 3)  (3, 2)

Table 2: The n = 8 case of the bijection established in Theorem 4.

Sequence n 1 2 3 4 5 6 7 8 9 10  name
a_{3}(n)  1 1 2 2 3 4 5 7 9 12 \underline{A000931} (Padovan Seq.)
a_{4}(n)  1 1 2 3 4 6 9 13 19 28 \underline{A000930} (Narayana Seq.)
a_{5}(n)  1 1 2 3 5 7 11 17 26 40  \underline{A204631}
a_{6}(n)  1 1 2 3 5 8 12 19 30 47  \underline{A225393}
Table 3: Sequence a_{ℓ}(n), for ℓ = 3, 4, 5 and 1 ≤ n ≤ 10.

We let A_{≥ℓ} denote the set of Arndt compositions with smallest part is at least ℓ. Let B(x, y; ℓ) denote the bivariate generating function for compositions in A_{≥ℓ} respect to the weight and number of parts. From (2), by setting S = {ℓ, ℓ + 1, … }, we obtain the following corollary.

Corollary 6. For ℓ ≥ 1 we have

B(x, y; ℓ) = \frac{(1 − x^{2})(1 − x + x^{ℓ}y)}{1 − x − x^{2} + x^{3} − x^{2ℓ+1}y^{2}} .

Let b_{ℓ}(n) be the n-th coefficient of B(x, 1; ℓ). We have

B_{ℓ}(x) := B(x, 1; ℓ) = ∑_{n≥0} b_{ℓ}(n)x^{n} = \frac{(1 − x^{2})(1 − x + x^{ℓ})}{1 − x(1 + x − x^{2} + x^{2ℓ})}.

In Table 4 we show the first few values of this sequence for ℓ = 2, 3, 4, 5. The sequences b_{ℓ}(n) are new in the OEIS.

Sequence n 2 3 4 5 6 7 8 9 10 11 12 13
b_{2}(n)  1 1 1 2 2 4 5 8 11 16 23 33
b_{3}(n)  0 1 1 1 1 2 2 3 4 6 8 11
b_{4}(n)  0 0 1 1 1 1 1 2 2 3 3 5
Table 4: Sequence b_{ℓ}(n), for ℓ = 2, 3, 4 and 2 ≤ n ≤ 13.

2.2 Arndt compositions with an odd or even number of parts

Another interesting example are Arndt compositions using only even (odd) parts. Let A_{E}(x, y) (resp., A_{O}(x, y)) be the bivariate generating function of Arndt compositions using only even (odd) parts with respect to the weight and number of parts. From (2), by setting E = {2, 4, 6, … } and O = {1, 3, 5, … }, we obtain the following corollary.

Corollary 7. We have

A_{E}(x, y) = \frac{(1 − x^{4})(1 − x^{2}(1 − y))}{1 − x^{2} − x^{4} + x^{6}(1 − y^{2})} and A_{O}(x, y) = \frac{(1 − x^{4})(1 − x^{2} + xy)}{1 − x^{2} + x^{6} − x^{4}(1 + y^{2})}.

Let a_{E}(n) be the n-th coefficient of A_{E}(x, 1). We have

A_{E}(x) := A_{E}(x, 1) = ∑_{n≥0} a_{E}(n)x^{n} = \frac{1 − x^{4}}{1 − x^{2} − x^{4}} .

Note that for all n ≥ 1,

a_{E}(n) = \begin{cases}F_{n/2}, & if n ≡ 0 (mod 2); \\ 0, & if n ≡ 1 (mod 2). \end{cases}

Let a_{O}(n) be the n-th coefficient of A_{O}(x, 1). We have

A_{O}(x) := A_{O}(x, 1) = ∑_{n≥0} a_{O}(n)x^{n} = \frac{1 + x − x^{2} − x^{4} − x^{5} + x^{6}}{1 − x^{2} − 2x^{4} + x^{6}}
= 1 + x + x^{3} + x^{4} + 2x^{5} + x^{6} + 3x^{7} + 3x^{8} + 6x^{9} + 4x^{10} + O(x^{11}).

While the sequence of coefficients is not in the OEIS, it appears that a_{O}(2n) matches with the sequence \underline{A006053} and a_{O}(2n + 1) matches with \underline{A028495}.

Open Problem 8. Find bijections between the different restrictions of Arndt compositions and the objects enumerated by the sequences \underline{A006053} and \underline{A028495}.

2.3 Arnd compositions in terms of q-series

In Theorem 9, we present an alternative expression for A(x, y) in terms of q-series notation. This expression is derived from the generating functions of partitions of n into exactly k distinct parts. Here and throughout we will use the standard q-series notation (cf. [4]) :

(a; q)_{n} = \begin{cases}∏_{k=0}^{n−1}(1 − aq^{k}), & if n > 0; \\ 1, & if n = 0. \end{cases}

Moreover, (a; q)_{∞} = lim_{n⟶∞}(a; q)_{n}, for |q| < 1. Let q(n, k) denote the number of partitions of n into k ≥ 1 distinct parts. The generating function of the sequence q(n, k) is given by

∑_{n,k≥0} q(n, k)x^{n}y^{k} = \frac{y^{k}x^{\binom{k+1}{2}}}{(x; x)_{k}} .

Theorem 9. The generating function for Arndt compositions with respect to the weight and the number of parts is given by

A(x, y) = (1 + \frac{xy}{1 − x}) ∑_{m≥0} \frac{y^{2m}x^{3m}}{(x; x)_{2}^{m}} .

Proof. Let σ be an Arndt composition. If σ has two parts, then it can be considered as a partition into two distinct parts. The generating function for this case is given by y^{2}x^{3}/(x; x)_{2}. The generating function follows from the fact that Arndt compositions can be regarded as the concatenation of partitions with two distinct parts, along with an additional part (which may be empty).

Let A_{2k}(x, y) denote the bivariate generating function for the number of Arndt compositions with exactly 2k parts, where k ≥ 1. Then A_{2k}(x, y) = y^{2k}x^{3k}/(x; x)_{2}^{k}. Analogously, let A_{2k+1}(x, y) be the bivariate generating function for the number of Arndt compositions with exactly 2k + 1 parts, where k ≥ 0. Then A_{2k+1}(x, y) = y^{2k+1}x^{3k+1}/((1 − x)(x; x)_{2}^{k}).

2.4 Arndt compositions with a fixed number of parts

Checa and Ramírez [8] obtained the following combinatorial expressions for the number of Arndt compositions with a fixed number of parts. For all n, m ≥ 0 we have

a(n, m) = ∑_{ℓ=0}^{n−m−⌊ \frac{m}{2} ⌋} \binom{m + ℓ − 1}{ℓ}\binom{n − m − ℓ − 1}{n − m − ⌊\frac{m}{2}⌋ − ℓ}(−1)^{n−m−⌊ \frac{m}{2} ⌋−ℓ}

= ∑_{ℓ=0}^{⌊(n−m−⌊ \frac{m}{2} ⌋)/2⌋} \binom{⌊\frac{m}{2}⌋ + ℓ − 1}{ℓ}\binom{n − 2⌊\frac{m}{2}⌋ − 2ℓ − 1}{⌊\frac{m−1}{2}⌋}.

We use ⌊x⌋ to denote the integer part of x, which is the greatest integer less than or equal to x.

In the following theorem, we give an additional formula for the number of Arndt compositions into k parts.

Theorem 10. The number of Arndt compositions into 2ℓ parts is given by

a(n, 2ℓ) = ∑_{\begin{matrix}a_{1}+a_{2}+···+a_{ℓ}=n; \\ a_{i}≥3,i=1,...,ℓ \end{matrix}} ∏_{i=1}^{ℓ} ⌊\frac{a_{i} − 1}{2}⌋ .

The number of Arndt compositions into 2ℓ + 1 parts is given by

a(n, 2ℓ + 1) = ∑_{\begin{matrix}a_{1}+a_{2}+···+a_{ℓ}+a_{ℓ+1}=n; \\ a_{i}≥3(1≤i≤ℓ),a_{ℓ+1}≥1 \end{matrix}} ∏_{i=1}^{ℓ} ⌊\frac{a_{i} − 1}{2}⌋ .

Proof. Let σ = (σ_{1}, σ_{2}, …, σ_{2ℓ}) be an Arndt composition into 2ℓ parts. This composition is composed by ℓ compositions with exactly two distinct parts. If a_{i} = σ_{2i−1} +σ_{2i} (i = 1, …, ℓ), then it is clear that a_{1} + ⋯ + a_{ℓ} = n and a_{i} ≥ 3. Since the number of compositions of n into exactly 2 parts is given by ⌊(n − 1)/2⌋, we obtain the desired result. If the number of parts is odd, the result follows in a similar manner.

For example, if ℓ = 1 we have

a(n, 3) = ∑_{3≤a+b≤n−1} ⌊\frac{a + b − 1}{2}⌋ = ∑_{i=3}^{n−1} ⌊\frac{i − 1}{2}⌋ .

By considering the parity of n we obtain

a(n, 3) = \begin{cases}n^{2}/4 − n + 1, & if n is even; \\ (n^{2} − 4n + 3)/4, & if n is odd. \end{cases}

The sequence a(n, 3) corresponds to the sequence \underline{A002620} in the OEIS. Similarly, we have

a(n, 4) = ∑_{\begin{matrix}a_{1}+a_{2}=n; \\ a_{1},a_{2}≥3 \end{matrix}} ∏_{i=1}^{2} ⌊\frac{a_{i} − 1}{2}⌋ = ∑_{i=3}^{n−3} ⌊\frac{(n − i) − 1}{2}⌋ ⌊\frac{i − 1}{2}⌋ .

Note that a(n, 4) is the sequence \underline{A006918} in the OEIS.

Open Problem 11. Find bijections between the different restrictions of Arndt compositions and the objects enumerated by the sequences \underline{A002620} and \underline{A006918}.

3 Palindromic Arndt compositions

A palindromic composition is one whose sequence of parts is the same when read from left to right or from right to left. For example, the palindromic Arndt compositions of 11 are

(11), (5, 1, 5), (2, 1, 5, 1, 2), (4, 3, 4), (3, 1, 3, 1, 3), (2, 1, 2, 1, 2, 1, 2). (3)

It is well known that the number of palindromic compositions of n is 2^{⌊n/2⌋}. To enumerate palindromic Arndt compositions, we must impose the original constraint σ_{2i−1} > σ_{2i} with σ_{i} = σ_{k−i+1}, where k is the number of parts. Let PA be the set of palindromic Arndt compositions. Note that the number of parts cannot be even since the middle summands cannot simultaneously satisfy both conditions. On the other hand, observe that the second summand must be between two adjacent greater summands since its reflection at the other end of the composition must satisfy σ_{3} = σ_{k−2} > σ_{k−1} = σ_{2}. The same reasoning applies to the fourth summand, the sixth, and so on. This means that the parts preceding the summand σ_{⌈k/2⌉} must form a composition with the constraint

σ_{1} > σ_{2} < σ_{3} > σ_{4} < σ_{5} > · · · .

These compositions are known as descending wiggly sums or down/up compositions, which are alternating compositions beginning with a descent. They are enumerated by the OEIS sequence \underline{A025049}, and we denote the set of such compositions by W.

A composition σ in PA with k parts can be decomposed as the concatenation of a composition μ in W, its reflection, and a part in the middle. Depending on the parity of the length of μ, the middle part must be greater or less than the summand immediately preceding σ_{⌈k/2⌉}. Therefore, we will focus first on enumerating the compositions of W.

3.1 Alternating compositions

Alternating compositions have been extensively studied by Bender and Canfield [6], but since we must distinguish them by the parity of their length, we will employ the procedure from Prodinger [19]; both authors utilize the adding-a-new slice technique (see Flajolet and Prodinger [11] for more details about this method).

Let us first examine the even case. Let a_{k}(x, z) be the generating function of those compositions in W with 2k summands; the variable x tracks the weight of the composition and z the size of the last summand. Likewise, we will track the number of parts with y. We define F (x, y, z) := ∑_{k≥0} a_{k}(x, z)y^{2k}.

Theorem 12. We have

F (x, y, z) = α(x, y, z) + \frac{α(x, y, x)}{1 − β(x, y, x)}β(x, y, z).  (4)

where

α(x, y, z) = ∑_{n≥0} \frac{(−1)^{n}x^{n^{2}+n}y^{2n}z^{n}}{(xz; x)_{2n}} and β(x, y, z) = ∑_{n≥1} \frac{(−1)^{n+1}x^{n^{2}+n}y^{2n}z^{n}}{(1 − x)(xz; x)_{2n−1}} . (5)

Proof. To apply the adding-a-new slice technique, we need to employ the substitution

z^{j} ⟶ ∑_{i>j} ∑_{k<i} x^{i+k}z^{k} = \frac{x^{j+2}z}{(1 − x)(1 − xz)} − \frac{x^{2j+2}z^{j+1}}{(1 − xz)(1 − x^{2}z)}.

This leads us to, for k ≥ 0,

a_{k+1}(x, z) = \frac{x^{2}z}{(1 − x)(1 − xz)}a_{k}(x, x) − \frac{x^{2}z}{(1 − xz)(1 − x^{2}z)}a_{k}(x, x^{2}z),

and a_{0}(x, z) = 1. When multiplying a_{k}(x, z) by y^{2k} and summing over all k ≥ 0, we obtain

F (x, y, z) = a_{0}(x, z) + ∑_{k≥0} a_{k+1}(x, z)y^{2k+2}

= 1 + \frac{x^{2}y^{2}z}{(1 − x)(1 − xz)}F (x, y, x) − \frac{x^{2}y^{2}z}{(1 − xz)(1 − x^{2}z)}F (x, y, x^{2}z).

Let |x|, |y|, |z| < 1. By iterating this equation infinitely many times, we have

F (x, y, z) = α(x, y, z) + F (x, y, x)β(x, y, z),

where α(x, y, z) and β(x, y, z) are defined as in (5). By substituting z → x, we have F (x, y, x) = α(x, y, x) + F (x, y, x)β(x, y, x). Solving this equation we obtain the desired result.

Let G(x, y, z) be the generating function of those compositions in W with an odd number of summands.

Theorem 13. We have

G(x, y, z) = \frac{xyz}{1 − xz} F (x, y, xz).

Proof. We just need to employ the substitution

z^{j} ⟶ ∑_{i>j} x^{i}yz^{i} = \frac{xyz}{1 − xz} x^{j}z^{j},

for the last summand of each composition enumerated by F (x, y, z). From this, we obtain the result.

3.2 Generating function of the palindromic Arndt compositions

We are now in a position to give an expression for the generating function of palindromic Arndt compositions.

Theorem 14. The generating function of palindromic Arndt compositions with respect to the weight, the number of parts and the size of the middle summand is given by

P A(x, y, z) = \frac{xyz}{1 − xz} F (x^{2}, y^{2}, xz) + \frac{x^{3}y^{3}z}{(1 − x^{2}) (1 − xz)}F (x^{2}, y^{2}, x^{2})

− \frac{x^{3}y^{3}z}{(1 − xz) (1 − x^{3}z)}F (x^{2}, y^{2}, x^{3}z),

where F (x, y, z) is given by expression (4).

Proof. Let P A_{1}(x, y, z) and P A_{3}(x, y, z) be the generating functions of compositions in PA whose length modulo 4 is 1 and 3, respectively; but in these two particular cases, z will no longer track the last summand but rather the middle one.

When the length of a composition σ in PA with k parts is of the form 4ℓ+1, the summand σ_{⌈k/2⌉} must be greater than the two immediately to the right and left. Therefore, we use again the substitution

z^{j} ⟶ ∑_{i>j} x^{i}yz^{i} = \frac{xyz}{1 − xz} x^{j}z^{j},

and evaluate F (x, y, z) at x → x^{2} and y → y^{2}. Therefore

P A_{1}(x, y, z) = \frac{xyz}{1 − xz} F (x^{2}, y^{2}, xz).

Similarly, when the length of an element in PA is 4ℓ + 3, the middle summand must be smaller than the adjacent ones. Therefore, we employ the substitution

z^{j} ⟶ ∑_{1≤i<j} x^{i}yz^{i} = \frac{xyz − x^{j}yz^{j}}{1 − xz} ,

and obtain

P A_{3}(x, y, z) = \frac{xyz}{1 − xz} G(x^{2}, y^{2}, 1) − \frac{y}{1 − xz} G(x^{2}, y^{2}, xz).

Finally, we obtain F (x, y, z) by summing and simplifying the expression P A_{1}(x, y, z) + P A_{3}(x, y, z).

As a series expansion, the generating function P A(x, y, 1) begins with

P A(x, y, 1) = yx + yx^{2} + yx^{3} + yx^{4} + (y + y^{3})x^{5} + yx^{6} + (y + y^{3})x^{7} + (y + y^{3} + y^{5})x^{8} + (y + y^{3} + y^{5})x^{9} + (y + y^{3} + 2y^{5})x^{10} + (y + 2y^{3} + 2y^{5} + y^{7})x^{11} + O(x^{12}).

The bold summand in the above series means that there are exactly 6 palindromic Arndt compositions of 11, consistent with the list (3).

Let a_{P} (n) be the number of palindromic Arndt compositions of weight n, that is a_{P} (n) = [x^{n}]P A(x, 1, 1). The first few values of this sequence are

1, 1, 1, 1, 2, 1, 2, 3, 3, 4, 6, 5, 9, 10, 13, 15, 22, 23, 34.

To estimate asymptotically this sequence, we proceed as Flajolet and Prodinger [11], where basically they extend Theorem 4.1 of Sedgewick and Flajolet [20] to non-rational functions. Let f(x) and g(x) be, respectively, the numerator and denominator of P A(x, 1, 1) when we substitute backward in terms of α(x, y, z) and β(x, y, z). For convenience, we omit f(x), but g(x) is simply

g(x) = (1 − x^{2})(1 + x)(1 + x + x^{2}) (1 − β(x^{2}, 1, x^{2})) .

Numerically, the dominant zeros of g(x) correspond to ρ ≈ 0.7976727085788669 and −ρ, both are simple. Whence the following formula.

Corollary 15. The number of palindromic Arndt compositions of n is asymptotically

a_{P} (n) ∼ −\frac{f(ρ)}{ρg′(ρ)}ρ^{−n} + \frac{f(−ρ)}{ρg′(−ρ)}(−ρ)^{−n}

≈ (0.436296840800465 + (−1)^{n+1}0.0291927761747376) (1.2536470023922461)^{n}.

3.3 Palindromic Arndt compositions with a fixed number of parts

Let a_{P} (n, k) be the number of palindromic Arndt compositions of n with k parts. It is clear that a_{P} (n, 2k) = 0 for all n ≥ 0. From Theorem 14, and using computer algebra system, specifically Mathematica, we can derive explicit rational generating functions for the sequence {a_{P} (n, k)}_{n} with k fixed. The combinatorial sums obtained during the proof of the results are well within the reach of modern computer algebra, in particular we used Mathematica

For example, for k = 1, 3, 5, and k = 9 we have the rational generating functions

∑_{n≥0} a_{P} (n, 1)x^{n} = \frac{x}{1 − x} = x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6} + x^{7} + x^{8} + x^{9} + O(x^{10}),

∑_{n≥0} a_{P} (n, 3)x^{n} = \frac{x^{5}}{1 − x^{2} − x^{3} + x^{5}}

= x^{5} + x^{7} + x^{8} + x^{9} + x^{10} + 2x^{11} + x^{12} + 2x^{13} + 2x^{14} + 2x^{15} + 2x^{16} + 3x^{17}

+ 2x^{18} + 3x^{19} + 3x^{20} + 3x^{21} + O (x^{22}) ,
∑_{n≥0} a_{P} (n, 5)x^{n} = \frac{x^{8}}{(1 − x)^{3}(1 + x)(1 + x + x^{2} + x^{3} + x^{4})}
= x^{8} + x^{9} + 2x^{10} + 2x^{11} + 3x^{12} + 4x^{13} + 5x^{14} + 6x^{15} + 7x^{16} + 8x^{17}
+ 10x^{18} + 11x^{19} + 13x^{20} + O(x^{21}),
∑_{n≥0} a_{P} (n, 9)x^{n} = \frac{x^{14}(1 + x + x^{2}(1 + x + x^{2})(1 + x^{3} + x^{6}))}{(1 − x)^{5}(1 + x)^{3}(1 − x + x^{2})(1 + x + x^{2})^{2}(1 + x + x^{2} + x^{3} + x^{4})(1 + x^{3} + x^{6})}
= x^{14} + x^{15} + 3x^{16} + 3x^{17} + 6x^{18} + 7x^{19} + 12x^{20} + O (x^{21}) .

For example, a_{P} (16, 5) = 7 and a_{P} (16, 7) = 3. The corresponding palindromic Arndt compositions are

(2, 1, 10, 1, 2), (3, 1, 8, 1, 3), (6, 1, 2, 1, 6), (4, 1, 6, 1, 4),
(3, 2, 6, 2, 3), (5, 1, 4, 1, 5), (4, 2, 4, 2, 4)

and

(2, 1, 2, 1, 4, 1, 2, 1, 2), (3, 1, 2, 1, 2, 1, 2, 1, 3), (2, 1, 3, 1, 2, 1, 3, 1, 2).

Except for a shift, the sequences a_{P} (n, k) for k = 3, 5 correspond to the sequences \underline{A103221} and \underline{A000115}, respectively.

Open Problem 16. Find bijections between the palindromic Arndt compositions and the objects enumerated by the sequences \underline{A006053} and \underline{A028495}.

4 Colored Arndt compositions

Agarwal [3] introduced a generalization of compositions known as n-color compositions, where a part of size m ≥ 1 can come in one of m different colors. The colors of the part m are denoted by subscripts m_{1}, m_{2}, …, m_{m}. For instance, the n-color compositions of 4 are

{4_{1}}, {4_{2}}, {4_{3}}, {4_{4}}, {3_{1}, 1_{1}}, {3_{2}, 1_{1}}, {3_{3}, 1_{1}}, {1_{1}, 3_{1}}, {1_{1}, 3_{2}}, {1_{1}, 3_{3}}, {2_{1}, 2_{1}},

   {2_{1}, 2_{2}}, {2_{2}, 2_{1}}, {2_{2}, 2_{2}}, {2_{1}, 1_{1}, 1_{1}}, {2_{2}, 1_{1}, 1_{1}}, {1_{1}, 2_{1}, 1_{1}}, {1_{1}, 2_{2}, 1_{1}}, {1_{1}, 1_{1}, 2_{1}},
   {1_{1}, 1_{1}, 2_{2}}, {1_{1}, 1_{1}, 1_{1}, 1_{1}}.

From this point, we will refer to these n-color compositions simply as colored compositions. The number of colored compositions of weight n is given by the Fibonacci number F_{2n}. Moreover, the number of colored compositions of n with exactly m parts is given by the binomial coefficient \binom{n+m−1}{2m−1}. For further information on n-color compositions, we refer the reader to see [1, 2, 7, 9, 10, 13, 17].

In analogy with these compositions, we introduce the colored version of Arndt compositions. Specifically, a colored Arndt composition of a positive integer n is a colored composition of n where the parts of size m can be colored with one of m different colors. For instance, the colored Arndt compositions of 4 are

{4_{1}}, {4_{2}}, {4_{3}}, {4_{4}}, {3_{1}, 1_{1}}, {3_{2}, 1_{1}}, {3_{3}, 1_{1}}, {2_{1}, 1_{1}, 1_{1}}, {2_{2}, 1_{1}, 1_{1}}. (6)

Let C(n) denote the set of colored Arndt compositions of weight n, and let C = ⋃_{n≥0} C(n). We set C(0) = {ϵ}, where ϵ denotes the empty colored composition (weight zero). Let c(n) and c(n, m) denote the number of colored Arndt compositions of n and the number of colored Arndt compositions of n with exactly m parts, respectively. We introduce a bivariate generating function to count the number of colored Arndt compositions with respect to the weight and number of parts:

C(x, y) := ∑_{σ∈C} x^{|σ|}y^{parts(σ)} = ∑_{n,m≥0} c(n, m)x^{n}y^{m}.

Theorem 17. The generating function for colored Arndt compositions with respect to the number of parts and weight is given by

C(x, y) = \frac{(1 − x)^{2}(1 + x)^{3}(1 + x^{2} + x(y − 2))}{1 − x − 3x^{2} − x^{3}(2y^{2} − 3) − x^{4}(y^{2} − 3) − x^{5}(3 + y^{2}) − x^{6} + x^{7}} .

Proof. Let w = (u_{a}, v_{b}) be a colored Arndt composition with two parts. Then 1 ≤ v_{b} < u_{a}, 1 ≤ a ≤ u, and 1 ≤ b ≤ v. If u_{a} = j ≥ 2, then the bivariate generating function for this case is

∑_{j≥2} jx^{j}y (x + 2x^{2} + ⋯ + (j − 1)x^{j−1}) y

= y^{2} ∑_{j≥2} jx^{j} \frac{x − jx^{j} + (j − 1)x^{j+1}}{(1 − x)^{2}} = \frac{x^{3}(2 + x + x^{2})y^{2}}{(1 − x)^{4}(1 + x)^{3}} .

Colored Arndt compositions are the concatenation of pairs of colored parts. Therefore the generating function for colored Arndt compositions with an even number of parts is given by

∑_{m≥0} (\frac{x^{3}}{(1 − x)^{3}(1 + x)^{2}} )^{m} y^{2m}

= \frac{(1 − x)^{4}(1 + x)^{3}}{1 − x − 3x^{2} + (3 − 2y^{2})x^{3} + (3 − y^{2})x^{4} − (3 + y^{2})x^{5} − x^{6} + x^{7}} .

Analogously, if the number of parts is odd, then generating functions is given by

∑_{m≥0} (\frac{x^{3}}{(1 − x)^{3}(1 + x)^{2}} )^{m} y^{2m} \frac{xy}{(1 − x)^{2}}

= \frac{(1 − x)^{2}x(1 + x)^{3}y}{1 − x − 3x^{2} − x^{6} + x^{7} − x^{4}(−3 + y^{2}) − x^{5}(3 + y^{2}) − x^{3}(−3 + 2y^{2})}.

Note that the generating function xy/(1 − x^{2}) = y ∑_{j≥1} jx^{j} corresponds to the last part. Adding the last two equations, we obtain the desired result.

As a series expansion, the generating function C(x, y) begins with

C(x, y) = 1 + yx + 2yx^{2} + (3y + 2y^{2})x^{3} + (4y + 3y^{2} + 2y^{3})x^{4} + (5y + 10y^{2} + 7y^{3})x^{5} + (6y + 13y^{2} + 22y^{3} + 4y^{4})x^{6} + O(x^{7}).

The bold summand in the above series means that there are exactly 9 colored Arndt compositions of 4, consistent with the list (6).

Corollary 18. The generating function of the number of colored Arndt compositions is

C(x, 1) = ∑_{n≥0} c(n)x^{n} = \frac{(1 − x)^{2}(1 + x)^{3}(1 − x + x^{2})}{1 − x − 3x^{2} + x^{3} + 2x^{4} − 4x^{5} − x^{6} + x^{7}} .

The number of colored Arndt compositions for 1 ≤ n ≤ 11:

1, 1, 2, 5, 9, 22, 45, 101, 217, 470, 1022.

Theorem 19. The generating function for the number of colored Arndt compositions with k parts is given by

C_{k}(x) = \frac{x^{k+⌊k/2⌋}(x^{2} + x + 2)^{⌊k/2⌋}}{(1 − x)^{2k}(1 + x)^{3⌊k/2⌋}} .

Proof. By definition, it is clear that for all ℓ ≥ 0

C_{2ℓ+1}(x) = (C_{2}(x))^{ℓ}C_{1}(x) and C_{2ℓ}(x) = (C_{2}(x))^{ℓ}.

On the other hand, from Theorem 17, we already know that

C_{1}(x) = \frac{x}{(1 − x)^{2}} and C_{2}(x) = \frac{x^{3}(x^{2} + x + 2)}{(1 − x)^{4}(1 + x)^{3}} .

Therefore

C_{2ℓ+1}(x) = \frac{x^{3ℓ+1}(x^{2} + x + 2)^{ℓ}}{(1 − x)^{4ℓ+2}(1 + x)^{3ℓ}} and C_{2ℓ}(x) = \frac{x^{3ℓ}(x^{2} + x + 2)^{ℓ}}{(1 − x)^{4ℓ}(1 + x)^{3ℓ}} .

Proceeding inductively yields the stated formula for C_{k}(x).

From Theorem 19 a closed formula for c(n, k) can be obtained, however, it may not be as straightforward to manipulate. Instead, we can also provide an asymptotic approximation.

Corollary 20. For a fixed positive integer k, we have

c(n, k) ∼ \frac{n^{2k−1}}{2^{⌊k/2⌋}(2k − 1)!}.

Proof. This is a direct application of the transfer theorem; see Sedgewick and Flajolet [20, Thm. 5.5].

5 Acknowledgments

We thank the referee for the careful reading of the manuscript and valuable comments that greatly improved the presentation of the paper. The first and second authors were supported by DG-RSDT (Algeria), PRFU Project, No. C00L03UN180120220002. The last two authors were partially supported by Universidad Nacional de Colombia, Project No. 57340.

References

[1] J. R. Acosta, Y. Caicedo, J. P. Poveda, J. L. Ramírez, and M. Shattuck, Some new restricted n-color composition functions, J. Integer Sequences 22 (2019), Article 19.6.4.

[2] A. K. Agarwal, An analogue of Euler’s identity and new combinatorial properties of n-colour compositions, J. Computer. Appl. Math. 160 (2003), 9–15.

[3] A. K. Agarwal, n-Colour compositions, Indian J. Pure Appl. Math. 31 (2000), 1421– 1427.

[4] G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1998.

[5] G. E. Andrews, M. Just, and G. Simay, Anti-palindromic compositions, Fibonacci Quart. 60 (2022), 164–176.

[6] E. A. Bender and E. R. Canfield, Locally restricted compositions I. Restricted adjacent differences, Elec. J. Combin. 12 (2005), #R57.

[7] J. J. Bravo, J. L. Herrera, J. L. Ramírez, and M. Shattuck, n-Color palindromic compositions with restricted subscripts, Proc. Indian Acad. Sci. Math. Sci. 131 (2021), 1–13.

[8] D. Checa and J. L. Ramírez, Arndt compositions: a generating functions approach, Integers 24 (2024), #A35.

[9] M. M. Gibson, D. Gary, and H. Wang, Combinatorics of n-color cyclic compositions, Discrete Math. 341 (2018), 3209–3226.

[10] Y.-H. Guo, n-Color odd self-inverse compositions, J. Integer Sequences 17 (2014), Article 14.10.5.

[11] P. Flajolet and H. Prodinger, Level number sequences for trees, Discrete Math. 65 (1987), 149–156.

[12] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, CRC Press, 2017.

[13] B. Hopkins, Spotted tilings and n-color compositions, Integers 12B (2013), Paper A6.

[14] B. Hopkins and A. Tangboonduangjit, Verifying and generalizing Arndt’s compositions, Fibonacci Quart. 60 (2022), 181–186.

[15] B. Hopkins and A. Tangboonduangjit, Arndt and De Morgan integer compositions, arxiv preprint arXiv:2307.12434 [math.CO], July 23 2023. Available at https://arxiv.org/

abs/2307.12434.

[16] B. Hopkins and H. Wang, Restricted color n-color compositions, J. Combin. 12 (2021), 355–377.

[17] T. Mansour and M. Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. Math. Sci. 124 (2014), 127–140.

[18] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, Published electronically at https://oeis.org, 2024.

[19] H. Prodinger, Arndt-Carlitz compositions, arxiv preprint arXiv:2312.05081 [math.CO],

December 8 2023. Available at https://arxiv.org/abs/2312.05081.

[20] R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, 2nd Edition, Addison-Wesley, 2013.

2020 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: composition, generating function, Fibonacci number.

(Concerned with sequences \underline{A000045}, \underline{A000115}, \underline{A000930}, \underline{A000931}, \underline{A002620}, \underline{A006053}, \underline{A006918}, \underline{A025049}, \underline{A028495}, \underline{A103221}, \underline{A204631}, and \underline{A225393}.)

Received April 24 2024; revised versions received April 25 2024; April 21 2025. Published in Journal of Integer Sequences, April 21 2025.

Return to Journal of Integer Sequences home page.