Partially Palindromic Compositions

Jia Huang Department of Mathematics and Statistics University of Nebraska at Kearney Kearney, NE 68849 USA

                        huangj2@unk.edu

Abstract

We generalize recent work of Andrews, Just, and Simay on modular palindromic compositions and anti-palindromic compositions by viewing all compositions partially (modular) palindromic or anti-palindromic. More precisely, we enumerate compositions by the extent to which they are (modular) palindromic or anti-palindromic. We obtain various closed formulas from generating functions and provide bijective proofs for many of them. We recover some known results of Andrews, Just, and Simay and discover new connections with numerous sequences in the On-Line Encyclopedia of Integer Sequences (OEIS).

1 Introduction

The concept of (integer) composition is useful and well studied in enumerative and algebraic combinatorics. A composition of n is a sequence α = (α_{1}, …, α_{ℓ}) of positive integers with |α| := α_{1} + ⋯ + α_{ℓ} = n. The parts of α are α_{1}, …, α_{ℓ} and the length of α is ℓ(α) := ℓ. We often drop the parentheses and commas in α when the parts are all single-digit numbers. We can encode α in a binary string of length n whose ith entry is 1 if

i ∈ {α_{1}, α_{1} + α_{2}, …, α_{1} + ⋯ + α_{ℓ}},

and 0 otherwise. For instance, α = 24112 is a composition of 10 corresponding to the binary string 0100011101. Thus there are exactly 2^{n−1} compositions of n, as they are in bijection with binary strings of length n whose last entry must be 1.

It is well known that the number of palindromic compositions of n is 2^{⌊n/2⌋} [3], where a composition α = (α_{1}, …, α_{ℓ}) is palindromic if α_{i} = α_{ℓ+1−i} for all i = 1, 2, …, ⌊ℓ/2⌋. Recently, Andrews and Simay [1] generalized this to parity palindromic compositions by replacing the condition α_{i} = α_{ℓ+1−i} with α_{i} ≡ α_{ℓ+1−i} (mod 2), and Just [5] further generalized it to palindromic compositions modulo m by imposing the condition α_{i} ≡ α_{ℓ−i} (mod m) for an arbitrary positive integer m. By Just [5], the generating function of the number pc(n, m) of palindromic compositions of n modulo m is

∑_{n≥1} pc(n, m)q^{n} = \frac{q + 2q^{2} − q^{m+1}}{1 − 2q^{2} − q^{m}} .

For m = 2 and n ≥ 1 we have pc(2n, 2) = pc(2n + 1, 2) = 2 · 3^{n−1} with an analytic proof by Andrews and Simay [1], a combinatorial proof by Just [5], and a recursive proof by Vatter [7]. For m = 3, Just [5] showed, both analytically and combinatorially, that pc(1, 3) = 1 and pc(n, 3) = 2F_{n−1} for all n ≥ 2, where F_{n} is the ubiquitous Fibonacci number defined by F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2. The case m > 3 was also briefly discussed by Just [5].

On the other hand, Andrews, Just, and Simay [2] defined a composition α = (α_{1}, …, α_{ℓ}) to be anti-palindromic if α_{i} ≠ α_{ℓ−i} for all i = 1, 2, …, ⌊ℓ/2⌋. They showed, among other things, that the number of anti-palindromic compositions of n is ac(n) = T_{n} + T_{n−2}, where T_{n} is a Tribonacci number defined by the recurrence T_{n} = T_{n−1} + T_{n−2} + T_{n−3} for n ≥ 3 with initial conditions T_{i} = 0 for i < 1 and T_{1} = T_{2} = 1 (\underline{A000073}).

In this paper we generalize the aforementioned work [1, 2, 3, 5] by viewing all compositions partially (modular) palindromic/anti-palindromic. More precisely, we count compositions by the extent to which they are (modular) palindromic/anti-palindromic. This is analogous to the well-known Euler partition theorem generalized to Glaisher’s theorem, and further to Franklin’s theorem (for more details and a parallel theory of compositions, see recent work [4]).

Definition 1.

(i) For n, k ≥ 0, let pc^{k}(n) := |PC^{k}(n)|, where PC^{k}(n) denotes the set of all compositions (α_{1}, …, α_{ℓ}) of n satisfying |{1 ≤ i ≤ ℓ/2 : α_{i} ≠ α_{ℓ+1−i}}| = k. Note that pc^{0}(0) = 1 and pc^{k}(0) = 0 for k ≥ 1. We further define

pc_{+}^{k}(n) := #{(α_{1}, …, α_{ℓ}) ∈ PC^{k}(n) : 2 | ℓ or 2 | α_{(ℓ+1)/2}},
pc_{−}^{k}(n) := #{(α_{1}, …, α_{ℓ}) ∈ PC^{k}(n) : 2 ∤ ℓ and 2 ∤ α_{(ℓ+1)/2}}.

In other words, pc_{+}^{k}(n) counts those compositions in PC^{k}(n) with an even middle part or no middle part, while pc_{−}^{k}(n) counts those compositions in PC^{k}(n) with an odd middle part. This leads to a refinement pc^{k}(n) = pc_{+}^{k}(n) + pc_{−}^{k}(n). For example, pc_{+}^{1}(4) = |{31, 13}| = 2, pc_{−}^{1}(4) = {211, 112}| = 2, and pc^{1}(4) = 2 + 2 = 4.

(ii) We define ac^{k}(n), ac_{+}^{k}(n), and ac_{−}^{k}(n) by replacing α_{i} ≠ α_{ℓ+1−i} with α_{i} = α_{ℓ+1−i} in (i).

(iii) For every positive integer m we define pc^{k}(n, m), pc_{+}^{k}(n, m), and pc_{−}^{k}(n, m) by replacing α_{i} ≠ α_{ℓ+1−i} with α_{i} ≢ α_{ℓ+1−i} (mod m) in (i), and define ac^{k}(n, m), ac_{+}^{k}(n, m), and ac_{−}^{k}(n, m) by using ≡ instead of ≢.

(iv) We also define pc^{k}(n, ∞) := pc^{k}(n), pc_{+}^{k}(n, ∞) := pc_{+}^{k}(n), pc_{−}^{k}(n, ∞) := pc_{−}^{k}(n), ac^{k}(n, ∞) := ac^{k}(n), ac_{+}^{k}(n, ∞) := ac_{+}^{k}(n), and ac_{−}^{k}(n, ∞) := pc_{−}^{k}(n). We often drop the superscript k when k = 0 since ac^{0}(n) and pc^{0}(n, m) agree with ac(n) [2] and pc(n, m) [5], respectively.

By Definition 1, we have pc^{k}(n, m) = pc_{+}^{k}(n, m) + pc_{−}^{k}(n, m) and pc_{−}^{k}(0, m) = 0. We also have pc_{+}^{k}(n, m) = pc_{−}^{k}(n + 1, m) since any composition α = (α_{1}, …, α_{ℓ}) counted by pc_{+}^{k}(n, m) corresponds to a composition α′ counted by counted by pc_{−}^{k}(n + 1, m), where α′ := (α_{1}, …, α_{s}, 1, α_{s+1}, …, α_{ℓ}) if ℓ = 2s, or α′ := (α_{1}, …, α_{s}, α_{s+1} + 1, α_{s+2}, …, α_{ℓ}) if ℓ = 2s + 1 and α_{s+1} is even. It follows that

pc^{k}(n, m) = pc_{+}^{k}(n, m) + pc_{+}^{k}(n − 1, m)  (1)

where pc_{+}^{k}(−1, m) := 0. Similarly, with ac_{+}^{k}(−1, m) := 0 we have

ac^{k}(n, m) = ac_{+}^{k}(n, m) + ac_{+}^{k}(n − 1, m).  (2)

To obtain closed formulas for pc^{k}(n, m) and ac^{k}(n, m), it suffices to do that for pc_{+}^{k}(n, m) and ac_{+}^{k}(n, m).

In Section 2 we obtain one closed formula for pc_{+}^{k}(n) and three for ac_{+}^{k}(n) using their generating functions. We also combinatorially prove all of these formulas except the last one for ac_{+}^{k}(n) via a bijection between compositions and certain pairs of nonnegative integer sequences.

For k = 0, our formula for pc_{+}^{k}(n) becomes pc_{+}(n) = 2^{n/2} if n is even or pc_{+}(n) = 0 if n is odd, and this implies the well-known fact that pc(n) = 2^{⌊n/2⌋} [3]. We also have pc_{+}^{1}(n) = 2 + (⌈n/2⌉ − 2)2^{⌈n/2⌉} for n ≥ 0 (\underline{A036799}). On the other hand, when k = 0 the three formulas for ac_{+}^{k}(n) all reduce to a Tribonacci number T′_{n+1} defined by the recurrence T′_{n} = T′_{n−1} + T′_{n−2} + T′_{n−3} for n ≥ 3 with initial conditions T′_{0} = 0, T′_{1} = 1, and T′_{2} = 0 (\underline{A001590}). Combining this with Eq. (2) gives ac(n) = T′_{n+1} + T′_{n}, which is different from the formula ac(n) = T_{n} + T_{n−2} obtained by Andrews, Just, and Simay [2], although they are equivalent via the relations T′_{n+1} = T_{n−1} + T_{n−2} and T′_{n} = T_{n} − T_{n−1} (\underline{A001590}).

We still have a fourth formula for ac^{k}(n), which is an alternating sum. We suspect that it has a combinatorial proof via inclusion-exclusion. For k = 0 this formula reduces to ac(n) = T_{n+1} − T_{n−1}, which is also equivalent to ac(n) = T′_{n+1} + T′_{n}. A byproduct of this is a formula for the Tribonacci number T_{n} that is not found in the entry for the OEIS sequence \underline{A000073}, but has a simple bijective proof.

In Section 3 we extend the concept of reduced anti-palindromic compositions introduced by Andrews, Just, and Simay [2] by defining rpc^{k}(n) (resp., rac^{k}(n)) as the number of equivalence classes of compositions counted by pc^{k}(n) (resp., ac^{k}(n)) under swaps of the first and last parts, the second and second last parts, and so on. We obtain closed formulas for the similarly defined rpc_{+}^{k}(n) and rac_{+}^{k}(n), which lead to formulas for rpc^{k}(n) and rac^{k}(n). It turns out that rpc^{k}(n) = pc^{k}(n)/2^{k} and rac_{+}^{k}(n) coincides with the number of compositions of n − k with exactly k parts equal to 1 (\underline{A105422}).

Now let m be a positive integer. In Section 4 we provide a positive sum formula and an alternating sum formula for pc_{+}^{k}(n, m), and thus for pc^{k}(n, m) by Eq. (1). In particular, we have a formula for pc(n, m), which implies the formulas of pc(n, 2) and pc(n, 3) as well as some properties of pc(n, m) given by Just [5]. In section 5 we provide formulas for rpc_{+}^{k}(n, m) and rpc^{k}(n, m) (defined similarly as rpc_{+}^{k}(n) and rpc^{k}(n)) and find connections to certain sequences in the OEIS [6] for special values of m and k.

In Section 6 we provide a positive sum formula and an alternating sum formula for ac_{+}^{k}(n, m) as well as a third formula for ac^{k}(n, m) which is also an alternating sum. For k = 0 we find no connection of ac_{+}(n, m) and ac(n, m) with existing sequences in the OEIS [6], but for m = 1, a signed version of ac_{+}^{k}(n, 1) is an interesting Riordan array (\underline{A158454}) and ac^{k}(n, 1) counts compositions of n with 2k or 2k + 1 parts. In Section 7 we provide formulas for rac_{+}^{k}(n, m) and rac^{k}(n, m) (defined similarly as rac_{+}^{k}(n) and rac^{k}(n)) and find connections to various integer sequences in the OEIS [6] for small values of m and k.

Below is a summary of the integer sequences in the OEIS [6] that occur in this paper.

• \underline{A036799}(n) = pc_{+}(2n + 1) = pc_{+}(2n + 2), \underline{A025192}(n) = pc_{+}(2n, 2), \underline{A008346}(n) = pc_{+}(n + 2, 3)/2.

• \underline{A001590}(n + 1) = ac_{+}(n), \underline{A000073}(n + 2)−\underline{A000073}(n) = ac(n).

• \underline{A212804}(n) = rac_{+}(n), \underline{A006367}(n) = rac_{+}^{1}(n + 2), \underline{A105423}(n) = rac_{+}^{2}(n + 4), \underline{A105422}(n, k) = rac_{+}^{k}(n + k), \underline{A324969}(n) = rac(n), \underline{A208354}(n) = rac^{1}(n + 2).

• \underline{A002620}(n) = ac_{+}^{1}(n, 1), \underline{A001752}(n) = ac_{+}^{2}(n + 4, 1), \underline{A001769}(n) = ac_{+}^{3}(n + 6, 1), \underline{A001780}(n) = ac_{+}^{4}(n + 8, 1), \underline{A001786}(n) = ac_{+}^{5}(n + 10, 1), \underline{A161680}(n) = ac^{1}(n, 1), \underline{A000332}(n) = ac^{2}(n, 1), \underline{A000579}(n) = ac^{3}(n, 1), \underline{A000581}(n) = ac^{4}(n + 8, 1).

• \underline{A052547}(n) = rpc_{+}(n, 1), \underline{A001870}(n) = rpc_{+}^{1}(2n + 3, 2), \underline{052534}(n) = rpc_{+}(2n, 4), \underline{A028495}(n) = rpc(n, 1), \underline{A094967}(n) = rpc(n, 2).

• \underline{A062200}(n) = rac_{+}(n, 2), \underline{A113435}(n) = rac(n, 3), \underline{A008805}(n) = rac_{+}^{1}(n+2, 1), \underline{A096338}(n) = rac_{+}^{2}(n+3, 1), \underline{A299336}(n) = rac_{+}^{3}(n+6, 1), \underline{A002620}(n) = rac^{1}(n, 1), \underline{A002624}(n) = rac^{2}(n + 4, 1), \underline{A060099}(n) = rac^{3}(n + 6, 1), \underline{A060100}(n) = rac^{4}(n + 8, 1), \underline{A060101}(n) = rac^{5}(n + 10, 1), \underline{A060098}(n, k) = rac^{k}(n + 2k, 1).

All of the closed formulas in this paper are derived from generating functions and they are either positive sums or alternating sums of products of binomial coefficients. To be precise, given integers a and b, we define the binomial coefficient

\binom{a}{b} := \begin{cases}\frac{a!}{b!(a−b)!}, & if a ≥ b ≥ 1; \\ 1, & if b = 0; \\ 0, & otherwise. \end{cases}

While we have bijective proofs for most of the positive sum formulas in this paper, it would be nice to see combinatorial proofs for the rest (possibly via inclusion-exclusion for the alternating sum formulas).

2 Partially (anti-)palindromic compositions

In this section we provide closed formulas for pc^{k}(n) and ac^{k}(n). By Eq. (1) and Eq. (2), it suffices to do this for pc_{+}^{k}(n) and ac_{+}^{k}(n).

Theorem 2. For all integers n, k ≥ 0 we have

pc_{+}^{k}(n) = ∑_{i+2j=n−3k} \binom{i + k − 1}{i}\binom{j + k}{j}2^{j+k},  (3)

ac_{+}^{k}(n) = ∑_{2r+i+j=n−2k} \binom{r + k}{r}\binom{r}{i}\binom{r + j − 1}{j}.  (4)

Analytic Proof. We derive pc_{+}^{k}(n) from the generating function ∑_{n, k≥0} pc_{+}^{k}(n)q^{n}t^{k}. Given a composition counted by pc_{+}^{k}(n), we pair the first part with the last part, the second part with the second last part, and so on. Each pair may or may not be equal. If the middle part exists, it must be even and is not paired with any other part. The generating function for each pair is

G(q, t) = (q^{2} + q^{4} + ⋯) + t((q + q^{2} + ⋯)^{2} − (q^{2} + q^{4} + ⋯))

where t keeps track of whether the two numbers in the pair are unequal. We can simplify G(q, t) and obtain

∑_{n, k≥0} pc_{+}^{k}(n)q^{n}t^{k} = \frac{1}{1 − G(q, t)} \frac{1}{1 − q^{2}} = \frac{1 − q}{(1 − q)(1 − 2q^{2}) − 2q^{3}t}.

Extracting the coefficient of t^{k} gives

∑_{n≥0} pc_{+}^{k}(n)q^{n} = \frac{(2q^{3})^{k}}{(1 − q)^{k}(1 − 2q^{2})^{k+1}} = (2q^{3})^{k} ∑_{i≥0} \binom{i + k − 1}{i}q^{i} ∑_{j≥0} \binom{j + k}{j}(2q^{2})^{j}.

This implies the formula (3) for pc_{+}^{k}(n). Similarly, we obtain the generating function for ac_{+}^{k}(n):

∑_{n, k≥0} ac_{+}^{k}(n)q^{n}t^{k} = \frac{1}{1 − tG(q, 1/t)} \frac{1}{1 − q^{2}} = \frac{1 − q}{1 − q − q^{2} − q^{3} − (1 − q)q^{2}t}.  (5)

Extracting the coefficient of t^{k} gives

∑_{n≥0} ac_{+}^{k}(n)q^{n} = \frac{(1 − q)^{k+1}q^{2k}}{(1 − q − q^{2} − q^{3})^{k+1}} = \frac{q^{2k}}{(1 − q^{2}(1 + q)/(1 − q))^{k+1}} .

Applying the binomial theorem to this gives the formula (4) for ac_{+}^{k}(n).

Combinatorial Proof. Let α = (α_{1}, …, α_{ℓ}) be a composition of n such that α_{(ℓ+1)/2} is even whenever ℓ is odd. Let S := {1 ≤ h ≤ ℓ/2 : α_{h} ≠ α_{ℓ+1−h}}. Define a composition β_{h} := (|α_{h} − α_{ℓ+1−h}| : h ∈ S). Subtracting the parts of β from the corresponding parts of α gives a palindromic composition γ = (γ_{1}, …, γ_{ℓ}) with |β| + |γ| = n, where γ_{h} := min{α_{h}, α_{ℓ+1−h}} for all h = 1, …, ℓ. Since γ is palindromic, we can encode it in a binary sequence of b = (b_{1}, …, b_{|γ|/2}), where b_{h} = 1 if and only if h ∈ {γ_{1}, γ_{1} + γ_{2}, …, γ_{1} + ⋯ + γ_{⌊ℓ/2⌋}}. We obtain b′ (resp., b′′) from b by adding β_{h} to b_{γ_{1}+···+γ_{h}} for all h ∈ S with α_{h} > α_{ℓ+1−h} (resp., α_{h} < α_{ℓ+1−h}). Then we have a bijection α ↔ (b′, b′′) since α can be recovered from b′ and b′′:

• Let s be the number of positive entries in b′. Then ℓ is 2s if b′ ends in 1 or 2s + 1 otherwise.

• For each h = 1, …, s, the hth positive entry of b′ (resp., b′′) plus the number of consecutive zeros immediately before it equals α_{h} (resp., α_{ℓ+1−h}).

• If ℓ = 2s + 1 then α_{s+1} equals twice the length of the rightmost string of consecutive zeros in b′.

Restrict the bijection α ↔ (b′, b′′) to those α with |S| = k. Then |β| = i + k for some i ≥ 0, |γ| = 2(j + k) for some j ≥ 0, and n = |β| + |γ| = i + 2j + 3k. We can construct all (b′, b′′) corresponding to those α with |S| = k as follows.

(i) First, let b′ and b′′ be the same binary sequence with k ones indexed by a set T and j zeros.

(ii) Let β = (β_{h} : h ∈ T) be a composition of i + k with exactly k parts indexed by T.

(iii) For each h ∈ T, add β_{h} to either b′_{h} or b′′_{h}.

(iv) For each h ∈ {1, …, j + k} \ T, let b′_{h} = b′′_{h} be either 0 or 1.

The numbers of possibilities for the above steps are \binom{j+k}{j}, \binom{i+k−1}{i}, 2^{k}, and 2^{j}, respectively. The formula (3) for pc_{+}^{k}(n) follows.

Now restrict the bijection α ↔ (b′, b′′) to those α with |S| = ⌊ℓ/2⌋ − k, where ℓ is the length of α. Let i := #{h ∈ S : α_{h} > α_{ℓ+1−h}}. Then |β| = i+j for some j ≥ 0, |γ| = 2(r+k) for some r ≥ 0, and n = |β|+|γ| = 2r+2k +i+j. We can construct all (b′, b′′) corresponding to those α with |S| = ⌊ℓ/2⌋ − k as follows.

(i) First let b′ and b′′ be the same binary sequence with r zeros indexed by a set T and k ones.

(ii) Choose i indices from T without repetition and increase the corresponding entries in b′ and b′′ by 2 and 1, respectively.

(iii) Choose j indices from T with repetition and do the following each time.

– If we pick one of the i indices chosen at the last step, add 1 to the corresponding entry in b′.

– If we pick an index not among the i indices chosen at the last step, increase the corresponding entries in b′ and b′′ by 1 and 2, respectively for the first time and increase only the corresponding entry in b′′ by 1 each time afterwards.

The numbers of ways to finish the above steps are \binom{r+k}{k}, \binom{r}{i}, and \binom{r+j−1}{j}, respectively. The formula (4) for ac_{+}^{k}(n) follows.

We provide some examples below to illustrate the above combinatorial proof.

Example 3.

(i) For n = 25 and k = 3 we have a composition α = 2141124111232 counted by pc_{+}^{k}(n) with S = {2, 3, 6}, β = 221, γ = 2121114111212, b′ = 0110311200, b′′ = 0130111100, i = 2, j = 7, and i + 2j + 3k = 25 = n. The construction of (b′, b′′) begins with b′ = b′′ = 0010100100, which has k = 3 ones indexed by T = {3, 5, 8} and j = 7 zeros. Adding the second and third parts of β = 221 to the second and third ones in b′ gives b′ = 0010300200, and adding the first part of β = 221 to the first one in b′′ gives b′′ = 0030100100. Finally, changing the zeros indexed by 2, 6, 7 to ones in both b′ and b′′ results in b′ = 0110311200 and b′′ = 0130111100.

(ii) For n = 17 and k = 1 we have a composition α = 2134115 counted by ac_{+}^{k}(n) with S = {1, 3}, β = 32, γ = 2114112, i = 1, j = 4, r = 5, b′ = 011300, b′′ = 041100, and 2r + 2k + i + j = 17 = n. The construction of (b′, b′′) is given below, with T = {1, 2, 4, 5, 6}.

001000 → 001200 → 001300 → 011300 → 011300 → 011300
001000 → 001100 → 001100 → 021100 → 031100 → 041100

(iii) For n = 6 and k = 0 we have ac_{+}(6) = 11 anti-palindromic compositions with an even middle part or no middle part:

\begin{matrix}r & i & j & α & (b, b′) \\ 1 & 0 & 4 & 15 & (1, 5) \\ 1 & 1 & 3 & 51 & (5, 1) \\ 2 & 0 & 2 & 24 & (01, 03) \\ 2 & 0 & 2 & 123 & (10, 30) \\ 2 & 0 & 2 & 1122 & (11, 22) \end{matrix}  \begin{matrix}r & i & j & α & (b, b′) \\ 2 & 1 & 1 & 42 & (03, 01) \\ 2 & 1 & 1 & 321 & (30, 10) \\ 2 & 1 & 1 & 1212 & (12, 12) \\ 2 & 1 & 1 & 2121 & (21, 21) \\ 2 & 2 & 0 & 2211 & (22, 11) \\ 3 & 0 & 0 & 6 & (000, 000) \end{matrix}

We provide two more formulas for ac_{+}^{k}(n) next.

Theorem 4. For n, k ≥ 0 we have

ac_{+}^{k}(n) = ∑_{2r+i+j=n−2k} 2^{i}\binom{r + k}{k}\binom{r}{i}\binom{i + j − 1}{j}  (6)

= ∑_{i+j+r+2s=n−2k}(−1)^{i}\binom{k + 1}{i}\binom{j + k}{j}\binom{j}{r + s}\binom{r + s}{r}.  (7)

Proof. We can rewrite the generating function (5) of ac_{+}^{k}(n) as

∑_{n, k≥0} ac_{+}^{k}(n)q^{n}t^{k} = \frac{1}{1 − q^{2}(2q/(1 − q) + 1 + t)} = ∑_{r,k≥0} q^{2(r+k)}\binom{r + k}{k}\binom{r}{i}\frac{(2q)^{i}}{(1 − q)^{i}} t^{k}.

Extracting the coefficient of q^{n}t^{k} gives the first formula (6). This formula can also be proved via the same bijection α ↔ (b′, b′′) as in the combinatorial proof of Theorem 2 but using a slightly different construction of b′ and b′′:

(i) Let b′ and b′′ be the same binary sequence with r zeros indexed by a set T and k ones.

(ii) Pick i indices from T without repetition and for each of them, add 1 to the corresponding entry in b′ and add 2 to the corresponding entry in b′′, or the other way around.

(iii) Among the 2’s in b′ and b′′, choose j of them with repetition and add 1 each time.

We also have

∑_{n, k≥0} ac_{+}^{k}(n)q^{n}t^{k} = ∑_{k≥0} \frac{(1 − q)^{k+1}q^{2k}t^{k}}{(1 − q − q^{2} − q^{3})^{k+1}}

= ∑_{k≥0} q^{2k} ∑_{i≥0} \binom{k + 1}{i}(−q)^{i} ∑_{j≥0} \binom{j + k}{j}(q + q^{2} + q^{3})^{j}t^{k},

which implies the second formula (7).

The formula (3) for pc_{+}^{k}(n) implies a formula for pc^{k}(n) = pc_{+}^{k}(n)+pc_{+}^{k}(n−1) by Eq. (1). In particular, we have pc_{+}^{0}(n) = 2^{n/2} if n is even or pc_{+}^{0}(n) = 0 otherwise, and this implies pc(n) = 2^{⌊n/2⌋}. We also have

pc_{+}^{1}(n) = ∑_{j=0}^{⌊(n−3)/2⌋}(j + 1)2^{j+1} = 2 + (⌈n/2⌉ − 2)2^{⌈n/2⌉}

for n ≥ 0, which is essentially the same as the known sequence \underline{A036799}.

On the other hand, the formulas (4), (6), (7) for ac_{+}^{k}(n) give formulas for ac^{k}(n) = ac_{+}^{k}(n) + ac_{+}^{k}(n − 1) by Eq. (2). For k = 0, we have

ac_{+}(n) = ∑_{2r+i+j=n} \binom{r}{i}\binom{r + j − 1}{j} = ∑_{2r+i+j=n} 2^{i}\binom{r}{i}\binom{i + j − 1}{j}

= ∑_{j+r+2s=n} \binom{j}{r + s}\binom{r + s}{r} − ∑_{j+r+2s=n−1} \binom{j}{r + s}\binom{r + s}{r},

which equals the Tribonacci number T′_{n+1} with initial conditions T′_{0} = 0, T′_{1} = 1, T′_{2} = 0 (\underline{A001590}). This implies ac(n) = T′_{n+1} + T′_{n} and it is different from the formula ac(n) = T_{n} + T_{n−2} obtained by Andrews, Just, and Simay [2], although they can be derived from each other via the relations T′_{n+1} = T_{n−1} + T_{n−2} and T′_{n} = T_{n} − T_{n−1} (\underline{A001590}). We provide one more formula for ac^{k}(n) below, which reduces to another formula ac(n) = T_{n+1} − T_{n−1} when k = 0.

Theorem 5. For n, k ≥ 0 we have

ac^{k}(n) = ∑_{\begin{matrix}i+j+r+s \\ =n−2k \end{matrix}}(−1)^{i}\binom{k}{i}\binom{j + k}{j}\binom{j}{r}\binom{r}{s} − ∑_{\begin{matrix}i+j+r+s \\ =n−2k−2 \end{matrix}}(−1)^{i}\binom{k}{i}\binom{j + k}{j}\binom{j}{r}\binom{r}{s}. (8)

Proof. We obtain the generating function of ac^{k}(n) from Eq. (5):

∑_{n, k≥0} ac^{k}(n)q^{n}t^{k} = \frac{1 − q^{2}}{1 − q − q^{2} − q^{3} − (1 − q)q^{2}t}

= (1 − q^{2}) ∑_{j,k≥0} \binom{j + k}{j}(q + q^{2} + q^{3})^{j}(1 − q)^{k}q^{2k}t^{k}.

Extracting the coefficient of q^{n}t^{k} gives the desired formula for ac^{k}(n).

Remark 6. There might be a combinatorial proof for the formula (8) of ac^{k}(n) via inclusionexclusion. For k = 0 this formula becomes ac(n) = T_{n+1} − T_{n−1}, giving a byproduct

T_{n+1} = ∑_{j+r+s=n} \binom{j}{r}\binom{r}{s}.

The above formula of T_{n+1} is not found in the entry for the OEIS sequence \underline{A000073}, but has a simple bijective proof. In fact, it is known that the number of compositions of n with no part greater than 3 is T_{n+1} (\underline{A000073}). Given such a composition, let j, r, s be the number of parts greater than 0, 1, 2, respectively. Then the r parts greater than 1 are among those j parts greater than 0, the s parts greater than 2 are among those r parts greater than 1, and j + r + s = n. This combinatorially proves the above formula of T_{n+1}.

3 Reduced partially (anti-)palindromic compositions

Andrews, Just, and Simay [2] found a formula for the number rac(n) of reduced antipalindromic compositions of n, where reduced anti-palindromic compositions are equivalence classes of anti-palindromic compositions under swaps of the first and last parts, the second and second last parts, and so on. We extend this definition and let rpc^{k}(n) (resp., rac^{k}(n)) denote the number of equivalence classes of compositions counted by pc^{k}(n) (resp., ac^{k}(n)) under the aforementioned swaps. Taking k = 0 gives rpc^{0}(n) = rpc(n) and rac^{0}(n) = rac(n). We define rpc_{+}^{k}(n), rpc_{−}^{k}(n), rac_{+}^{k}(n), and rac_{−}^{k}(n) similarly.

Proposition 7. For n, k ≥ 0, we have rpc_{+}^{k}(n) = pc_{+}^{k}(n)/2^{k}, rpc_{−}^{k}(n) = pc_{−}^{k}(n)/2^{k}, and rpc^{k}(n) = pc^{k}(n)/2^{k}.

Proof. This result follows immediately from the definition.

Theorem 8. For n ≥ 0, we have

rac_{+}^{k}(n) = ∑_{2r+j=n−2k} \binom{r + k}{r}\binom{r + j − 1}{j},

which is also the number of compositions of n − k with exactly k parts equal to 1 (\underline{A105422}).

Proof. Similarly to the proof of Theorem 2, the generating function for rac_{+}^{k}(n) is

∑_{n, k≥0} rac_{+}^{k}(n)q^{n}t^{k} = \frac{1}{1 − tG(q, 1/2t)} \frac{1}{1 − q^{2}} = \frac{1 − q}{1 − q − q^{2} − (1 − q)q^{2}t}.

Extracting the coefficient of t^{k} gives

∑_{n≥0} rac_{+}^{k}(n)q^{n} = \frac{(1 − q)^{k+1}q^{2k}}{(1 − q − q^{2})^{k+1}} = \frac{q^{2k}}{(1 − q^{2}/(1 − q))^{k+1}} .

This implies the desired formula of rac_{+}^{k}(n). We can also prove this formula by modifying the combinatorial proof of the formula (6) of ac_{+}^{k}(n), where the i indices picked in step (ii) correspond to the swaps of parts used to define rac_{+}^{k}(n).

Finally, comparing the generating function of rac_{+}^{k}(n) with the generating function of \underline{A105422} shows that rac_{+}^{k}(n) is also the number of compositions of n − k with exactly k parts equal to 1. This can also be proved bijectively. In fact, given a composition of n − k with k parts equal to 1 and r parts greater than 1, subtracting 1 from each part gives a composition of n − 2k − r = r + j for some j ≥ 0 with r parts. Conversely, if 2r + j = n − 2k then there are \binom{r+j−1}{j} many compositions of r + j with r parts, each corresponding to \binom{r+k}{r} many compositions of n − k with k parts equal to 1 and r parts greater than 1.

Some special cases of Theorem 8 are given below.

• We have rac_{+}^{0}(0) = 1 and rac_{+}^{0}(n) = F_{n−1} (\underline{A212804}). Consequently, rac(0) = 1 and rac(n) = F_{n} for n ≥ 1 (\underline{A324969}).

• For n ≥ 0, rac_{+}^{1}(n) = ∑_{0≤r≤(n−2)/2}(r+1)\binom{n−r−3}{n−2r−2} is the number of compositions of n−1 with exactly one part equal to 1 (\underline{A006367}), and rac^{1}(n) is the number of compositions of n − 2 with at most one even part (\underline{A208354}).

• For n ≥ 0, rac_{+}^{2}(n) = ∑_{2r+j=n−4} \binom{r+2}{2}\binom{r+j−1}{j} is the number of compositions of n − 2 with exactly two parts equal to 1 (\underline{A105423}).

Remark 9. It would be interesting to see whether rac^{1}(n) = rac_{+}^{1}(n) + rac_{+}^{1}(n − 1) can be proved bijectively using compositions with exactly one part equal to 1 and compositions with at most one even part. One may also notice that rac(n) equals the number of the number of compositions of n with no even parts. By checking the generating functions we are convinced that the connection between rac^{k}(n) and compositions of n with at most k even parts is valid only for k = 0, 1.

4 Partially palindromic compositions modulo m

Let m be a positive integer throughout the rest of the paper. In this section we obtain closed formulas for pc_{+}^{k}(n, m), which imply formulas for pc^{k}(n, m) by Eq. (1).

Theorem 10. For n, k ≥ 0 we have

pc_{+}^{k}(n, m) = ∑_{2i+mj+(m−1)r+s=n−k}(−1)^{r}2^{i}\binom{i}{k}\binom{i + j − 1}{j}\binom{k}{r}\binom{k + s − 1}{s}  (9)

= ∑_{\begin{matrix}i_{0}+i_{1}+···+i_{m−2}=k \\ 2i+mj+i_{1}+2i_{2}+···+(m−2)i_{m−2}=n−k \end{matrix}} 2^{i}\binom{i}{k}\binom{i + j − 1}{j}\binom{k}{i_{0}, i_{1}, …, i_{m−2}}. (10)

Proof. Given a composition, each part equals its least positive residue modulo m plus a nonnegative multiple of m. We pair the first part with the last part, the second part with the second last part, and so on. If the middle part exists, then it is not paired with any other part. For each pair, their smallest positive residues modulo m may be equal or unequal. Thus the generating function for each pair is

G_{m}(q, t) = (q^{2} + q^{4} + ⋯ + q^{2m} + t((q + q^{2} + ⋯ + q^{m})^{2} − q^{2} − q^{4} − ⋯ − q^{2m})(1 + q^{m} + ⋯)^{2}

and the generating function for pc_{+}^{k}(n, m) is

∑_{n,k≥0} pc_{+}^{k}(n, m)q^{n}t^{k} = \frac{1}{1 − G_{m}(q, t)} \frac{1}{1 − q^{2}}

= \frac{(1 − q)(1 − q^{m})}{(1 − q)(1 − q^{m}) − 2q^{2}(1 − q + q(1 − q^{m−1})t)}

= ∑_{i≥0} \frac{(2q^{2})^{i}}{(1 − q^{m})^{i}} (1 + \frac{q(1 − q^{m−1})t}{1 − q})^{i}

= ∑_{i≥k≥0} \binom{i}{k}\frac{(2q^{2})^{i}q^{k}(1 − q^{m−1})^{k}t^{k}}{(1 − q^{m})^{i}(1 − q)^{k}} .

Extracting the coefficient of q^{n}t^{k} gives the formula (9) for pc_{+}^{k}(n, m).

We can also write (1 − q^{m−1})^{k}/(1 − q)^{k} = (1 + q + ⋯ + q^{m−2})^{k} in the generating function of pc_{+}(n, m, k) and apply the multinomial theorem to obtain the formula (10).

Remark 11. We can rewrite Eq. (10) (and similar formulas appearing later) using symmetric functions. Let λ ⊆ (m − 2)^{k} denote that λ is an (integer) partition with at most k parts, each no more than m−2. Adding trailing zeros we can identify it with a decreasing sequence λ = (λ_{1}, …, λ_{k}) of k integers in {0, 1, …, m − 2}. For h = 0, 1, …, m − 2, let i_{h} be the number of parts of λ ⊆ (m − 2)^{k} that are equal to h. We have i_{0} + i_{1} + ⋯ + i_{m−2} = k and i_{1} + 2i_{2} + ⋯ + (m − 2)i_{m−2} = |λ|. The monomial symmetric function m_{λ}(x_{1}, …, x_{k}) is the sum of the monomials x_{1}^{a_{1}} ⋯ x_{k}^{a_{k}} for all rearrangements (a_{1}, …, a_{k}) of (λ_{1}, …, λ_{k}). The formula (10) becomes

pc_{+}^{k}(n, m) = ∑_{\begin{matrix}λ⊆(m−2)^{k} \\ 2i+mj+|λ|=n−k \end{matrix}} 2^{i}\binom{i}{k}\binom{i + j − 1}{j}m_{λ}(1^{k})

where m_{λ}(1^{k}) is the evaluation of m_{λ}(x_{1}, …, x_{k}) at the vector (1, …, 1) of length k.

Taking k = 0 in either Eq. (9) or Eq. (10) give the following:

pc_{+}(n, m) = ∑_{2i+mj=n} 2^{i}\binom{i + j − 1}{j}.  (11)

We can also obtain this by modifying the combinatorial proof of Theorem 2 with |β| = mj and |γ| = 2i. Some known results follow.

Corollary 12 ([1, 5, 7]). For n ≥ 1 we have pc(2n, 2) = pc(2n + 1, 2) = 2 · 3^{n−1} (\underline{A025192}). Proof. Taking m = 2 in Eq. (11) immediately gives pc_{+}^{0}(2n, 2) = ∑_{i≥0} 2^{i}\binom{n−1}{n−i} = 2·3^{n−1} and pc_{+}^{0}(2n + 1, 2) = 0. Corollary 13 ([5]).

(i) For n ≥ 2 we have pc(n, 3) = 2F_{n−1}.

(ii) If m is even then pc(2n, m) = pc(2n + 1, m).

(iii) If 2n + 1 < m then pc(2n, m) = pc(2n + 1, m) = 2^{n}. Proof. The proof of Theorem 10 gives the generating function

∑_{n≥0} pc_{+}^{0}(n, 3)q^{n} = \frac{(1 − q)(1 − q^{3})}{(1 − q)(1 − q^{3}) − 2q^{2}(1 − q)} = \frac{1 − q^{3}}{1 − 2q^{2} − q^{3}} .

Taking m = 3 in Eq. (11) gives pc_{+}^{0}(n, 3) = ∑_{2i+3j=n} 2^{i}\binom{i+j−1}{j}. Either way we have pc_{+}^{0}(0, 3) = 1, pc_{+}^{0}(1, 3) = 1, and pc_{+}^{0}(n, 3) = 2(F_{n−2} + (−1)^{n−2}) for n ≥ 2 (cf. the known sequence \underline{A008346}. It follows from Eq. (1) and the recursive relation of F_{n} that pc(n, 3) = pc_{+}^{0}(n, 3) + pc_{+}^{0}(n − 1, 3) = 2F_{n−1}. Thus (i) holds.

If m is even then pc_{+}^{0}(n, m) = 0 for all odd n by Eq. (11). Thus (ii) follows from Eq. (1). If 2n + 1 < m then a summand in pc_{+}^{0}(2n, m) given by Eq. (11) is nonzero only if j = 0

and i = n, and pc_{+}^{0}(2n + 1, m) = pc_{+}^{0}(2n − 1, m) = 0 for the same reason. This together with Eq. (1) gives (iii).

For m = 1 we have pc_{+}(n, 1) = ∑_{2i+j=n} 2^{i}\binom{i+j−1}{j} and pc_{+}^{k}(n, 1) = 0 for k ≥ 1 from

∑_{n,k≥0} pc_{+}^{k}(n, 1)q^{n}t^{k} = \frac{1 − q}{1 − q − 2q^{2}} = ∑_{i≥0} \frac{(2q^{2})^{i}}{(1 − q)^{i}} .

We can also use a combinatorial argument for this. In fact, since any two integers are congruent modulo m = 1, we have must pc_{+}^{k}(n, 1) = 0 for k ≥ 1, and for k = 0, the number pc_{+}(n, 1) counts compositions of n without an odd middle part. The combinatorial proof of Theorem 2 can be modified with |β| = j and |γ| = 2i to give another proof of the above formula of pc_{+}(n, 1). Analogously, we have pc(n, 1) = 2^{n−1} counts all compositions of n and pc^{k}(n, 1) = 0 for k ≥ 1. Note that pc_{+}(n, 1) coincide with the known sequence \underline{A078008}, which counts compositions of n with parts greater than one, each part colored in two possible ways. It would be interesting to have a bijection between the two families of compositions both counted by pc_{+}(n, 1).

For m = 2 we observe the following. Corollary 14. For n ≥ 0 we have pc_{+}^{k}(n, 2) = ∑_{2i+2j=n−k} 2^{i}\binom{i}{k}\binom{i+j−1}{j}, which is zero when n − k is odd. In particular, pc_{+}^{1}(2n, 2) = 0 and pc_{+}^{1}(2n + 1, 2) = ∑_{i≥0}(i + 1)2^{i+1}\binom{n−1}{i} for n ≥ 1 (\underline{A081038}). Proof. Taking m = 2 in Eq. (10) gives pc_{+}^{k}(n, 2) = ∑_{2i+2j=n−k} 2^{i}\binom{i}{k}\binom{i+j−1}{j}. This sum is empty if 2i + 2j = n − k is odd. The rest of the result follows.

5 Reduced partially palindromic compositions modulo m

Let rpc^{k}(n, m) denote the number of equivalence classes of compositions counted by pc^{k}(n, m) under swaps of the first and last parts, the second and second last parts, and so on. We define rpc_{+}^{k}(n, m) and rpc_{−}^{k}(n, m) similarly. It follows that rpc^{k}(n, m) = rpc_{+}^{k}(n, m)+rpc_{−}^{k}(n, m) = rpc_{+}^{k}(n, m) + rpc_{+}^{k}(n − 1, m) where rpc_{+}^{k}(−1, m) := 0.

Theorem 15. For n, k ≥ 0 we have

rpc_{+}^{k}(n, m) = ∑_{2i+mj+2c+(m−1)r+s=n−k}(−1)^{r}\binom{i}{k}\binom{i + j − 1}{j}\binom{i + c}{c}\binom{k}{r}\binom{k + s − 1}{s} (12)

= ∑_{\begin{matrix}i_{0}+i_{1}+···+i_{m−2}=k \\ 2i+mj+2c+i_{1}+2i_{2}+···+(m−2)i_{m−2}=n−k \end{matrix}} \binom{i}{k}\binom{i + j − 1}{j}\binom{i + c}{c}\binom{k}{i_{0}, i_{1}, …, i_{m−2}}. (13)

Proof. Similarly to the proof of Theorem 10, the generating function for each pair is

G′_{m}(q, t) =(q^{2} + q^{4} + ⋯ + q^{2m}) (1 + q^{2m} + ⋯ + \frac{1}{2}((1 + q^{m} + ⋯)^{2} − 1 − q^{2m} − ⋯))

+ \frac{t}{2}((q + q^{2} + ⋯ + q^{m})^{2} − q^{2} − q^{4} − ⋯ − q^{2m})(1 + q^{m} + ⋯)^{2},

and the generating function of rpc_{+}^{k}(n, m) is

∑_{n,k≥0} rpc_{+}^{k}(n, m)q^{n}t^{k} = \frac{1}{1 − G′_{m}(q, t)} \frac{1}{1 − q^{2}}

= \frac{(1 − q)(1 − q^{m})}{(1 − q)(1 − q^{2})(1 − q^{m}) − q^{2}(1 − q) − q^{3}(1 − q^{m−1})t}

= \frac{1}{1 − q^{2}} ∑_{i≥k≥0} \binom{i}{k}\frac{q^{2i+k}(1 − q)^{i−k}(1 − q^{m−1})^{k}t^{k}}{(1 − q)^{i}(1 − q^{2})^{i}(1 − q^{m})^{i}} .

Extracting the coefficient of q^{n}t^{k} gives the desired formulas for rpc_{+}^{k}(n, m).

For k = 0 we have the number rpc_{+}(n, m) counts compositions α = (α_{1}, …, α_{ℓ}) of n such that α_{(ℓ+1)/2} is even whenever ℓ is odd and that α_{h} − α_{ℓ+1−h} is a nonnegative multiple of m for h = 1, …, ⌊ℓ/2⌋. One can compare the following formula of rpc_{+}(n, m) with the formula (11) for pc_{+}(n, m).

Corollary 16. For n ≥ 0 we have

rpc_{+}(n, m) = ∑_{2i+mj+2r=n} \binom{i + j − 1}{j}\binom{i + r}{r}.

Proof. Setting t = 0 in the generating function of rpc_{+}^{k}(n, m) gives

∑_{n≥0} rpc_{+}(n, m)q^{n} = \frac{(1 − q^{m})}{(1 − q^{2})(1 − q^{m}) − q^{2}} = \frac{1}{1 − q^{2}} ∑_{i≥k≥0} \frac{q^{2i}}{(1 − q^{2})^{i}(1 − q^{m})^{i}} .

This implies the desired formula for rpc_{+}(n, m), which can also be obtained by modifying the combinatorial proof of Theorem 2 with |β| = mj, |γ| = 2(i + r), and ℓ(γ) = 2i.

In particular, we have rpc_{+}(n, 1) coincides with the known sequence \underline{A052547}, and rpc(n, 1) = ∑_{2i+j+2r=n} \binom{i+j}{j}\binom{i+r−1}{r} agrees with another sequence, \underline{A028495}, which also counts compositions of n with increments appearing only at every second position (such compositions are in bijection with the compositions counted by rpc(n, 1) by reordering parts appropriately). Next, the generating function of rpc_{+}(n, 2) can be written as (F (q) − F (−q))/2q, where F (q) = q/(1 − q − q^{2}) is the generating function of the Fibonacci numbers. Thus rpc_{+}(2n, 2) = F_{2n+1} and rpc_{+}(2n + 1, 2) = 0. Consequently, rpc(n, 2) agrees with \underline{A094967}: rpc(2n, 2) = rpc(2n + 1, 2) = F_{2n+1}. Moreover, rpc_{+}(2n, 4) is the same as \underline{A052534} and rpc_{+}(2n + 1, 4) = 0.

On the other hand, for m = 1 and k ≥ 1 we have rpc_{+}^{k}(n, 1) = 0, which follows from either its definition or its generating function. For m = 2 we have rpc_{+}^{k}(n, 2) = ∑_{2i+2j=n−k} \binom{i}{k}\binom{2i+j}{j} from its generating function

∑_{n,k≥0} rpc_{+}^{k}(n, 2)q^{n}t^{k} = \frac{(1 − q^{2})}{(1 − q^{2})^{2} − q^{2} − q^{3}t} = \frac{1}{1 − q^{2}} ∑_{i≥0} \frac{q^{2i}(1 + qt)^{i}}{(1 − q^{2})^{2i}} .

Thus rpc_{+}^{1}(2n, 2) = 0, rpc_{+}^{1}(2n + 1, 2) = ∑_{0≤i≤n} i\binom{n+i}{2i} (\underline{A001870}), and rpc^{1}(2n + 1, 2) = rpc^{1}(2n + 2, 2) = rpc_{+}^{1}(2n + 1, 2).

6 Partially anti-palindromic compositions modulo m

In this section we provide closed formulas for ac_{+}^{k}(n, m) and ac^{k}(n, m), where m is a positive integer.

Theorem 17. For n, k ≥ 0 we have

ac_{+}^{k}(n, m) = ∑_{\begin{matrix}2i+j+r(m−1)+s \\ +mc+md=n−2k \end{matrix}}(−1)^{r}2^{j}\binom{i + k}{k}\binom{i}{j}\binom{j}{r}\binom{j + s − 1}{s}\binom{k}{c}\binom{k + j + d − 1}{d}

= ∑_{\begin{matrix}i_{0}+i_{1}+···+i_{m−2}=j \\ 2i+j+i_{1}+2i_{2}+···+(m−2)i_{m−2} \\ +mc+md=n−2k \end{matrix}} 2^{j}\binom{i + k}{k}\binom{i}{j}\binom{j}{i_{0}, …, i_{m−2}}\binom{k}{c}\binom{k + j + d − 1}{d}.

Proof. Similarly as the proof of Theorem 10, we have

∑_{n, k≥0} ac_{+}^{k}(n, m)q^{n}t^{k} = \frac{1}{1 − tG_{m}(q, 1/t)} \frac{1}{1 − q^{2}}

= \frac{(1 − q)(1 − q^{m})}{(1 − q)(1 − q^{m}) − q^{2}(1 − q)(1 − q^{m}) − 2q^{3}(1 − q^{m−1}) − q^{2}(1 − q)(1 + q^{m})t}

= ∑_{i≥0} q^{2i} (1 + \frac{2q(1 − q^{m−1})}{(1 − q)(1 − q^{m})} + \frac{(1 + q^{m})t}{1 − q^{m}})^{i}

= ∑_{i,k≥0} q^{2(i+k)}\binom{i + k}{k} (1 + \frac{2q(1 − q^{m−1})}{(1 − q)(1 − q^{m})})^{i} \frac{(1 + q^{m})^{k}t^{k}}{(1 − q^{m})^{k}}

= ∑_{i,j,k≥0} q^{2(i+k)}\binom{i + k}{k}\binom{i}{j}\frac{(2q)^{j}(1 − q^{m−1})^{j}}{(1 − q)^{j}(1 − q^{m})^{j}} \frac{(1 + q^{m})^{k}t^{k}}{(1 − q^{m})^{k}} .

Extracting the coefficient of q^{n}t^{k} gives the first formula for ac_{+}^{k}(n, m).

We can also write (1 − q^{m−1})^{j}/(1 − q)^{j} = (1 + q + ⋯ + q^{m−2})^{j} in the generating function of ac_{+}(n, m, k) and apply the multinomial theorem to obtain the second formula.

Combining Theorem 17 and Eq. (2), we obtain two formulas for ac^{k}(n, m). We also directly provide another formula for ac^{k}(n, m) below.

Theorem 18. For n, k ≥ 0 we have

ac^{k}(n, m) = ∑_{\begin{matrix}3i+j+r(m−1)+2s \\ +cm+dm=n−2k \end{matrix}}(−1)^{r}2^{i}\binom{i + k}{k}\binom{i + j}{j}\binom{i}{r}\binom{i + k + s − 1}{s}\binom{k}{c}\binom{i + k + d − 1}{d}.

Proof. Similarly to the proof of Theorem 10, we have

∑_{n, k≥0} ac^{k}(n, m)q^{n}t^{k} = \frac{1}{1 − tG_{m}(q, 1/t)} \frac{1}{1 − q}

= \frac{(1 − q^{2})(1 − q^{m})}{(1 − q)(1 − q^{2})(1 − q^{m}) − 2q^{3}(1 − q^{m−1}) − q^{2}(1 − q)(1 + q^{m})t}

= \frac{1}{1 − q} ∑_{i≥0} (\frac{2q^{3}(1 − q^{m−1})}{(1 − q)(1 − q^{2})(1 − q^{m})} + \frac{q^{2}(1 − q)(1 + q^{m})t}{(1 − q)(1 − q^{2})(1 − q^{m})})^{i}

= \frac{1}{1 − q} ∑_{i,k≥0} \binom{i + k}{k}\frac{(2q^{3})^{i}(1 − q^{m−1})^{i}}{(1 − q)^{i}(1 − q^{2})^{i}(1 − q^{m})^{i}} · \frac{q^{2k}(1 + q^{m})^{k}t^{k}}{(1 − q^{2})^{k}(1 − q^{m})^{k}}

= ∑_{i,k≥0} \binom{i + k}{k}\frac{2^{i}q^{3i+2k}(1 − q^{m−1})^{i}(1 + q^{m})^{k}t^{k}}{(1 − q)^{i+1}(1 − q^{2})^{i+k}(1 − q^{m})^{i+k}} .

Extracting the coefficient of q^{n}t^{k} from this gives the desired formula for ac^{k}(n, m).

Taking k = 0 in Theorem 17 and Theorem 18 immediately give closed formulas for ac_{+}(n, m) and ac(n, m). We cannot find any connection of ac_{+}(n, m) and ac(n, m) with existing sequences in the OEIS [6].

Another interesting specialization is at m = 1. Since any two integers are congruent modulo m = 1, the number ac_{+}^{k}(n, 1) counts compositions of n with 2k parts or with 2k + 1 parts, the middle one of which is even. The generating function of ac_{+}^{k}(n, m) specializes to

∑_{n,k≥0} ac_{+}^{k}(n, 1)q^{n}t^{k} = \frac{1}{1 − q^{2} − q^{2}(1 + q)t/(1 − q)} = ∑_{i,k≥0} q^{2(i+k)}\binom{i + k}{k}\frac{(1 + q)^{k}t^{k}}{(1 − q)^{k}} ,

which implies

ac_{+}^{k}(n, 1) = ∑_{2i+c+d=n−2k} \binom{i + k}{k}\binom{k}{c}\binom{k + d − 1}{d}.

A signed version of ac_{+}^{k}(n, 1) gives a Riordan array that is the coefficient table of the square of Chebyshev S-polynomials and also sends the Catalan numbers to ones (\underline{A158454}). We also find some special cases: ac_{+}(n, 1) = (1 + (−1)^{n})/2, ac_{+}^{1}(n, 1) = ⌊n^{2}/4⌋ (\underline{A002620}), ac_{+}^{2}(n, 1) (\underline{A001752}), ac_{+}^{3}(n, 1) (\underline{A001769}), ac_{+}^{4}(n, 1) (\underline{A001780}), and ac_{+}^{5}(n, 1) (\underline{A001786}).

Similarly, the number ac^{k}(n, 1) counts all compositions of n with 2k or 2k + 1 parts, and

∑_{n, k≥0} ac^{k}(n, 1)q^{n}t^{k} = \frac{1 − q}{(1 − q)^{2} − q^{2}t} = ∑_{k≥0} \frac{q^{2k}t^{k}}{(1 − q)^{2k+1}} ,

which implies ac^{k}(n, 1) = \binom{2k+1+n−2k−1}{n−2k} = \binom{n}{2k}. This formula can also be proved combinatorially as compositions of n with 2k or 2k + 1 parts are in bijection with binary sequences of length n with exactly 2k ones (if the last digit is zero, change it to one to get a composition with 2k + 1 parts).

For m = 2, 3 and k = 0, 1, 2 we list some initial terms of ac^{k}(n, m) below.

• ac^{0}(n, 2) : 1, 1, 1, 3, 3, 7, 11, 17, 33, 49, 89, 147, 243, 423, 691, 1185, …

• ac^{1}(n, 2) : 0, 0, 1, 1, 4, 8, 13, 33, 52, 108, 201, 353, 688, 1196, 2213, 3985, …

• ac^{2}(n, 2) : 0, 0, 0, 0, 1, 1, 7, 13, 32, 80, 148, 352, 677, 1381, 2799, 5313, …

• ac^{0}(n, 3) : 1, 1, 1, 3, 5, 7, 15, 27, 43, 81, 147, 249, 449, 809, 1409, 2507, …

• ac^{1}(n, 3) : 0, 0, 1, 1, 2, 8, 13, 23, 58, 108, 195, 411, 786, 1446, 2831, 5387, …

• ac^{2}(n, 3) : 0, 0, 0, 0, 1, 1, 3, 13, 22, 48, 132, 258, 525, 1197, 2409, 4797, …

The OEIS [6] does not contain any of the above sequences.

7 Reduced partially anti-palindromic compositions modulo m

Let rac^{k}(n, m) denote the number of equivalence classes of compositions counted by ac^{k}(n, m) under swaps of the first and last parts, the second and second last parts, and so on. Define rac_{+}^{k}(n, m) and rac_{−}^{k}(n, m) similarly. It follows that rac^{k}(n, m) = rac_{+}^{k}(n, m) + rac_{−}^{k}(n, m) = rac_{+}^{k}(n, m) + rac_{+}^{k}(n − 1, m) where rac_{+}^{k}(−1, m) := 0. We give two closed formulas for rac_{+}^{k}(n, m) and a third formula directly for rac^{k}(n, m).

Theorem 19. For n, k ≥ 0 we have

rac_{+}^{k}(n, m) = ∑_{2i+j+r(m−1)+s+md=n−2k}(−1)^{r}\binom{i + k}{k}\binom{i}{j}\binom{j}{r}\binom{j + s − 1}{s}\binom{k + j + d − 1}{d}

= ∑_{\begin{matrix}i_{0}+i_{1}+···+i_{m−2}=j \\ 2i+j+i_{1}+2i_{2}+···+(m−2)i_{m−2}+md=n−2k \end{matrix}} \binom{i + k}{k}\binom{i}{j}\binom{j}{i_{0}, …, i_{m−2}}\binom{k + j + d − 1}{d},

rac^{k}(n, m) = ∑_{3i+j+r(m−1)+2s+dm=n−2k}(−1)^{r}\binom{i + k}{k}\binom{i + j}{j}\binom{i}{r}\binom{i + k + s − 1}{s}\binom{i + k + d − 1}{d}.

Proof. Similarly to the proof of Theorem 15, the generating function for rac_{+}^{k}(n, m) is

∑_{n, k≥0} rac_{+}^{k}(n, m)q^{n}t^{k} = \frac{1}{1 − tG′_{m}(q, 1/t)} \frac{1}{1 − q^{2}}

= \frac{(1 − q)(1 − q^{m})}{(1 − q)(1 − q^{m}) − q^{2}(1 − 2q^{m} + q^{m+1}) − q^{2}(1 − q)t}

= ∑_{i≥0} q^{2i} (1 + \frac{q(1 − q^{m−1})}{(1 − q)(1 − q^{m})} + \frac{t}{1 − q^{m}} )^{i}

= ∑_{i,k≥0} q^{2(i+k)}\binom{i + k}{k} (1 + \frac{q(1 − q^{m−1})}{(1 − q)(1 − q^{m})})^{i} \frac{t^{k}}{(1 − q^{m})^{k}}

= ∑_{i,j,k≥0} q^{2(i+k)}\binom{i + k}{k}\binom{i}{j}\frac{q^{j}(1 − q^{m−1})^{j}}{(1 − q)^{j}(1 − q^{m})^{j}} \frac{t^{k}}{(1 − q^{m})^{k}} .

Extracting the coefficient of q^{n}t^{k} gives the desired formulas for rac_{+}^{k}(n, m). We also have

∑_{n, k≥0} rac^{k}(n, m)q^{n}t^{k} = \frac{1}{1 − tG′_{m}(q, 1/t)} \frac{1}{1 − q}

= \frac{(1 − q^{2})(1 − q^{m})}{(1 − q)(1 − q^{2})(1 − q^{m}) − q^{3}(1 − q^{m−1}) − q^{2}(1 − q)t}

= \frac{1}{1 − q} ∑_{i≥0} (\frac{q^{3}(1 − q^{m−1})}{(1 − q)(1 − q^{2})(1 − q^{m})} + \frac{q^{2}(1 − q)t}{(1 − q)(1 − q^{2})(1 − q^{m})})^{i}

= ∑_{i,k≥0} \binom{i + k}{k}\frac{q^{3i+2k}(1 − q^{m−1})^{i}t^{k}}{(1 − q)^{i+1}(1 − q^{2})^{i+k}(1 − q^{m})^{i+k}} .

Extracting the coefficient of q^{n}t^{k} from this gives the desired formula for rac^{k}(n, m).

Taking k = 0 in Theorem 19 immediately gives formulas for rac_{+}(n, m) and rac(n, m). Although ac_{+}(n, m) and ac(n, m) are not related to any sequences in the OEIS (see Section 6), we find the following special cases of rac_{+}(n, m) and rac(n, m):

• We have rac_{+}(2n, 1) = 1, rac_{+}(2n + 1, 1) = 0, rac(n, 1) = 1 for n ≥ 0.

• We have rac_{+}(0, 2) = 1, rac_{+}(1, 2) = 0 and for n ≥ 2 the number rac_{+}(n, 2) counts compositions of n − 2 with no two adjacent parts of the same parity (\underline{A062200}).

• The sequence rac(n, 3) for n ≥ 0 agrees with the known sequence \underline{A113435}, which currently does not contain any combinatorial interpretation.

For m = 1 we obtain rac_{+}^{k}(n, 1) = ∑_{2i+j=n−2k} \binom{i+k}{k}\binom{j+k−1}{j} from the generating function

∑_{n, k≥0} rac_{+}^{k}(n, 1)q^{n}t^{k} = \frac{1 − q}{(1 − q) − q^{2}(1 − q) − q^{2}t} = ∑_{i,k≥0} q^{2(i+k)}\binom{i + k}{k}\frac{t^{k}}{(1 − q)^{k}} .

Since every two integers are congruent modulo m = 1, the number rac_{+}^{k}(n, 1) counts all compositions α = (α_{1}, …, α_{ℓ}) of n such that α_{(ℓ+1)/2} is even whenever ℓ is odd and that α_{h} ≥ α_{ℓ+1−h} for h = 1, …, ⌊ℓ/2⌋. Thus the above formula for rac_{+}^{k}(n, 1) can also be obtained by modifying the combinatorial proof of Theorem 2 with |β| = j, |γ| = 2(i + k), and ⌊ℓ(γ)/2⌋ = k. We have rac_{+}^{1}(2n, 1) = rac_{+}^{1}(2n + 1, 1) = ∑_{0≤i≤n−1}(i + 1) = n(n + 1)/2, giving a new interpretation of the sequence of repeated triangular numbers (\underline{A008805}). We also have rac_{+}^{2}(n, 1) = ∑_{2i+j=n−4} \binom{i+2}{2}(j + 1) (\underline{A096338}).

Similarly, we obtain rac^{k}(n, 1) = ∑_{2i+j=n−2k} \binom{i+k−1}{i}\binom{j+k}{j} from the generating function

∑_{n, k≥0} rac^{k}(n, 1)q^{n}t^{k} = \frac{1 − q^{2}}{(1 − q)(1 − q^{2}) − q^{2}t} = \frac{1}{1 − q} ∑_{i,k≥0} \frac{q^{2k}t^{k}}{(1 − q)^{k}(1 − q^{2})^{k}} .

The number rac^{k}(n, 1) counts compositions α = (α_{1}, …, α_{ℓ}) of n such that α_{h} ≥ α_{ℓ+1−h} for h = 1, …, ⌊ℓ/2⌋. This gives a new interpretation of a triangular array of integers \underline{A060098}. Some special cases include rac^{1}(n, 1) = ∑_{0≤i≤⌊n/2⌋−1}(n − 2i − 1) = ⌊\frac{n}{2}⌋⌈\frac{n}{2}⌉, which coincides with both ac_{+}^{1}(n, 1) and the known sequence \underline{A002620}, rac^{2}(n, 1) = ∑_{2i+j=n−4}(i + 1)\binom{j+2}{2} (\underline{A002624}), rac^{3}(n, 1) (\underline{A060099}), rac^{4}(n, 1) (\underline{A060100}), and rac^{5}(n, 1) (\underline{A060101}). A combinatorial explanation for rac^{1}(n, 1) = ac_{+}^{1}(n, 1) would be interesting.

For m ≥ 2 we cannot find any connection of rac_{+}^{k}(n, 1) or rac^{k}(n, 1) with existing sequences in the OEIS [6].

8 Acknowledgment

The author uses SageMath to help discover and verify the closed formulas in this paper. He also thanks the anonymous referees for helpful comments and suggestions.

References

[1] G. E. Andrews and G. Simay, Parity palindrome compositions, Integers 21 (2021), Paper No. A85.

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

[3] V. E. Hoggatt, Jr. and M. Bicknell, Palindromic compositions, Fibonacci Quart. 13 (1975), 350–356.

[4] J. Huang, Compositions with restricted parts, Discrete Math. 343 (2020), 111875.

[5] M. Just, Compositions that are palindromic modulo m, arxiv preprint arXiv:2102.00996

   [math.CO], 2021. Available at https://arxiv.org/abs/2102.00996.

[6] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available

   at https://oeis.org.

[7] V. Vatter, Counting parity palindrome compositions, arxiv preprint arXiv:2109.13155

   [math.CO], 2021. Available at https://arxiv.org/abs/2109.13155.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: composition, palindrome.

(Concerned with sequences \underline{A000073}, \underline{A000332}, \underline{A000579}, \underline{A000581}, \underline{A001590}, \underline{A001752}, \underline{A001769}, \underline{A001780}, \underline{A001786}, \underline{A001870}, \underline{A002620}, \underline{A002624}, \underline{A006367}, \underline{A008346}, \underline{A008805}, \underline{A025192}, \underline{A028495}, \underline{A036799}, \underline{A052534}, \underline{A052547}, \underline{A060098}, \underline{A060099}, \underline{A060100}, \underline{A060101}, \underline{A062200}, \underline{A078008}, \underline{A081038}, \underline{A094967}, \underline{A096338}, \underline{A105422}, \underline{A105423}, \underline{A113435}, \underline{A158454}, \underline{A161680}, \underline{A208354}, \underline{A212804}, \underline{A299336}, and \underline{A324969}.)

Received March 11 2023; revised versions received April 4 2023; April 5 2023. Published in Journal of Integer Sequences, April 7 2023.

Return to Journal of Integer Sequences home page.