Arndt and Carlitz Compositions

Technical Summary: Arndt and Carlitz Compositions

Problem Statement
The paper addresses the enumeration of integer compositions—ordered sequences of positive integers summing to $n$—under specific local restrictions. It seeks to unify and generalize two distinct lines of research:

1. Carlitz compositions: Introduced by Carlitz, these require that adjacent parts be unequal ($c_i \neq c_{i+1}$).
2. Arndt compositions: Initiated by Arndt, these impose restrictions on specific pairs of parts, typically $(c_{2i-1}, c_{2i})$, without restricting the relationship between $c_{2i}$ and $c_{2i+1}$.

The authors define a new class of Carlitz–Arndt compositions ($CA(n)$) that satisfy the Arndt pairing structure but enforce the Carlitz condition ($c_{2i-1} \neq c_{2i}$) on each pair. The paper further generalizes this by bounding the absolute difference between paired parts from below ($|c_{2i-1} - c_{2i}| \geq k$) and from above ($|c_{2i-1} - c_{2i}| \leq k$).

Methodology
The authors employ a dual approach combining combinatorial proofs (explicit bijections) and generating functions.

• Combinatorial Proofs: The core of the paper involves constructing bijections between the restricted compositions and other known or newly defined sets. For the lower-bound case, they map compositions to a subset of "restricted Pell compositions" ($P_{\geq k}(n)$) involving parts $\{1, 1', 2\}$. For the upper-bound case, they map to compositions $Q_{\leq k}(n)$ involving parts $\{1, 1', 2, 4, 6, \dots\}$. These bijections allow the authors to derive recurrence relations by analyzing the structure of the mapped sets.
• Generating Functions: The authors derive rational generating functions for the number of compositions in each class. These functions are constructed by treating pairs of parts as blocks and summing over possible values, then combining even and odd length cases.

Key Contributions and Results

1. Carlitz–Arndt Compositions ($CA(n)$):

   • The authors establish that the number of such compositions, $ca(n)$, satisfies the recurrence $ca(n) = ca(n-1) + ca(n-2) + ca(n-3)$ with initial values $1, 1, 3$.
   • This sequence corresponds to the "tribonacci" numbers (OEIS A000213).
   • A bijection is proven between $CA(n)$ and compositions with no adjacent parts equal to 1 ($C^c_{1,1}(n)$).

2. Generalized Lower-Bound Compositions ($CA_{\geq k}(n)$):

   • For a fixed $k$, the condition $|c_{2i-1} - c_{2i}| \geq k$ is analyzed.
   • The authors prove a recurrence relation: $ca_{\geq k}(n) = ca_{\geq k}(n-1) + ca_{\geq k}(n-2) - ca_{\geq k}(n-3) + 2ca_{\geq k}(n-k-2)$.
   • A bijection is established between $CA_{\geq k}(n)$ and restricted Pell compositions $P_{\geq k}(n)$, where runs of 1s or $1'$s have length at least $k$.
   • The generating function is derived as $\frac{1-x^2}{1-x-x^2+x^3-2x^{k+2}}$.

3. Generalized Upper-Bound Compositions ($CA_{\leq k}(n)$):

   • The condition $|c_{2i-1} - c_{2i}| \leq k$ is analyzed.
   • The authors derive a recurrence: $ca_{\leq k}(n) = ca_{\leq k}(n-1) + 2ca_{\leq k}(n-2) - 2ca_{\leq k}(n-k-3)$.
   • A bijection is established between $CA_{\leq k}(n)$ and compositions $Q_{\leq k}(n)$ with parts $\{1, 1', 2, 4, 6, \dots\}$ where runs of 1s or $1'$s have length at most $k$.
   • The generating function is derived as $\frac{1-x^2}{1-x-2x^2+2x^{k+3}}$.

Significance and Claims
The paper claims to successfully combine and generalize the notions of Carlitz and Arndt compositions. By establishing these connections, the authors provide:

• Enumeration Results: Explicit recurrence relations and generating functions for these generalized classes.
• Combinatorial Insight: The bijections to Pell-type compositions and restricted run-length compositions offer structural understanding of why these specific recurrences arise.
• Contextual Motivation: The work is motivated by its connection to gap-free compositions (studied by Hitczenko and Knopfmacher) and Rogers–Ramanujan integer partitions. The authors note that their lower-bound generalization ($CA_{\geq k}$) relates to the "super-distinct" parts in Rogers–Ramanujan partitions (parts differing by at least 2) and Schur partitions (parts differing by at least 3).

The authors explicitly state that their methods are primarily combinatorial, though they utilize generating functions to verify and provide alternative proofs for the recurrence relations. They acknowledge that Prodinger (2023) considered a more complex combination of these conditions, prompting the authors to use the notation $CA(n)$ to distinguish their specific formulation. The paper does not propose experimental applications or future implications beyond the mathematical enumeration and structural analysis presented.