Cyclic, Dihedral and Symmetrical Carlitz Compositions of a Positive Integer

Petros Hadjicostas 9 Ikarou Str. Larnaka 6050 Cyprus

                 peterhadji1@gmail.com

Abstract

A linear composition of a positive integer N is a list of positive integers (called parts) whose sum equals N. We distinguish two kinds of cyclic compositions, which we call C-type and CR-type. A CR-type cyclic composition of N is an equivalence class of all linear compositions of N that can be obtained from each other by a cyclic shift, while a dihedral composition is an equivalence class of all linear compositions of N that can be obtained from each other by a cyclic shift or a reversal of order. A linear Carlitz composition is one where adjacent parts are distinct. A C-type cyclic Carlitz composition is a linear Carlitz composition whose first and last parts are distinct, whereas a CR-type cyclic Carlitz composition is an equivalence class of C-type Carlitz compositions that can be obtained from each other by a cyclic shift. We distinguish two kinds of linear palindromic compositions (type I and type II). We derive generating functions for the number of type II linear palindromic Carlitz compositions, and we provide a new proof of a result by J. Taylor about C-type Carlitz compositions. Using these results, we derive formulas about CR-type Carlitz compositions, symmetrical CR-type compositions, and dihedral Carlitz compositions.

1 Introduction and main results

A linear composition (or just, a composition, as it is known by other authors) of a positive integer N of length K is a K-tuple (λ_{1}, λ_{2}, …, λ_{K}) ∈ ℤ_{>0}^{K} such that

N = λ_{1} + λ_{2} + ⋯ + λ_{K};  (1)

see MacMahon [18, 19]. Here, the numbers λ_{1}, λ_{2}, …, λ_{K} are called the parts of the composition. We denote the number of linear compositions of N with K parts in the set A ⊆ ℤ_{>0} by c_{A}^{L}(N; K). It is proven in Beck and Robbins [1], Heubach and Mansour [12], Hoggatt and Lind [14], and Moser and Whitney [20], that the bivariate generating function for c_{A}^{L}(N; K) is

∑_{N,K≥0} c_{A}^{L}(N; K) x^{N}y^{K} = 1 + ∑_{N,K≥1} c_{A}^{L}(N; K) x^{N}y^{K} = \frac{1}{1 − y ∑_{a∈A} x^{a}} .

(Here we assume c_{A}^{L}(N; 0) = 0 if N > 0, and c_{A}^{L}(0; 0) = 1.) We let c_{A}^{L}(N) = ∑_{K=1}^{N} c_{A}^{L}(N; K), and in general, if T_{A}(N; K) denotes the total number of compositions of some kind (or the total number of equivalence classes of compositions of some kind) of N with length K and parts in A, then we let T_{A}(N) = ∑_{K=1}^{N} T_{A}(N; K). In addition, throughout the paper we assume

T_{A}(N; K) = 0 when N < K.

In the literature, there are two kinds of cyclic compositions, and following Zhang and Hadjicostas [25], in this paper, we call them C-type and CR-type. (For linear compositions, i.e., ordinary compositions, following Zhang and Hadjicostas [25] again, we use the term L-type.)

A CR-type cyclic composition of N of length K is an equivalence class consisting of all linear compositions of N with length K that can be obtained from each other by a cyclic shift; see Sommerville [22], Knopfmacher and Robbins [16], and Razen, Seberry and Wehrhahn [21]. We denote the number of all such CR-type cyclic compositions of N with K parts in A ⊆ ℤ_{>0} by c_{A}^{CR}(N; K). On the other hand, a dihedral composition is an equivalence class of all linear compositions that can be obtained from each other either by a cyclic shift or a reversal of order; see Knopfmacher and Robbins [17] and Zagaglia Salvi [24]. We denote the number of all dihedral compositions of N with K parts in A ⊆ ℤ_{>0} by c_{A}^{D}(N; K). If (λ_{1}, …, λ_{K}) is a representative of a CR-type cyclic composition, we denote its equivalence class by [(λ_{1}, …, λ_{K})]_{CR}, while if it is a representative of a dihedral composition, we denote its equivalence class by [(λ_{1}, …, λ_{K})]_{D}.

Hadjicostas [10] proved that the bivariate generating function for the number of CR-type cyclic compositions of N with K parts in A is

∑_{N,K≥1} c_{A}^{CR}(N; K) x^{N}y^{K} = ∑_{s≥1} \frac{ϕ(s)}{s} log \frac{1}{1 − y^{s} ∑_{a∈A} x^{as}} .

(There is an obvious typo in the corresponding formula in Section 2.2 in Hadjicostas and Zhang [11].) Here, ϕ(n) is Euler’s totient function at positive integer n, i.e., the number of positive integers less than or equal to n that are co-prime to n.

An L-type Carlitz composition of N with length K is a linear composition (λ_{1}, λ_{2}, …, λ_{K}) such that ∑_{i=1}^{K} λ_{i} = N and λ_{i} ≠ λ_{i+1} for i = 1, 2, …, K − 1; see Carlitz [6], Corteel and Hitczenko [7], and Knopfmacher and Prodinger [15]. On the other hand, a C-type (cyclic) Carlitz composition of N with length K is a linear composition (λ_{1}, λ_{2}, …, λ_{K}) such that ∑_{i=1}^{K} λ_{i} = N and λ_{i} ≠ λ_{i+1} for i = 1, 2, …, K − 1, K, where we define λ_{K+1} := λ_{1}. In other words, it is an L-type Carlitz composition of N with length K with the additional restriction λ_{K} ≠ λ_{1}. We denote the number of L-type Carlitz compositions of N with K parts in A ⊆ ℤ_{>0} by E_{A}^{L}(N; K) and the number of C-type (cyclic) Carlitz compositions of N with K parts in A by E_{A}^{C}(N; K). It is proven in Heubach and Mansour [12] that the bivariate generating function of E_{A}^{L}(N; K) is

∑_{N,K≥0} E_{A}^{L}(N; K) x^{N}y^{K} = 1 + ∑_{N,K≥1} E_{A}^{L}(N; K) x^{N}y^{K} = \frac{1}{1 − ∑_{a∈A} \frac{x^{a}y}{1+x^{a}y}} .  (2)

(We define E_{A}^{L}(N; 0) = 0 for N > 0 and E_{A}^{L}(0, 0) = 1.) The bivariate generating function of E_{A}^{C}(N; K) is discussed in Theorem 4 below.

Following Hadjicostas and Zhang [11], we define two kinds of linear palindromic compositions, which we call type I and type II. A type I linear palindromic composition of N with length K is a linear composition (λ_{1}, …, λ_{K}) of N such that

(λ_{1}, λ_{2}, …, λ_{K}) = (λ_{K}, λ_{K−1}, …, λ_{1}),

i.e., λ_{i} = λ_{K+1−i} for i = 1, …, K; see MacMahon [18]. A type II linear palindromic composition of N with length K is a linear composition (λ_{1}, …, λ_{K}) of N such that

(λ_{1}, λ_{2}, …, λ_{K}) = (λ_{1}, λ_{K}, …, λ_{2}),

i.e, λ_{i} = λ_{K+2−i} for i = 2, …, K. For K = 1, we assume that (λ_{1}) = (N) is a linear palindromic composition of both types. We denote the number of type I linear palindromic compositions of N with K parts in A by P_{A}^{L_{1}}(N; K) and those of type II by P_{A}^{L_{2}}(N; K). We also denote by F_{A}^{L_{1}}(N; K) and F_{A}^{L_{2}}(N; K) the numbers of type I and type II Carlitz linear palindromic compositions of N with K parts in A, respectively.

Heubach and Mansour [12] proved that the bivariate generating function of P_{A}^{L_{1}}(N; K) is

∑_{N,K≥0} P_{A}^{L_{1}}(N; K) x^{N}y^{K} = 1 + ∑_{N,K≥1} P_{A}^{L_{1}}(N; K) x^{N}y^{K} = \frac{1 + ∑_{a∈A} x^{a}y}{1 − ∑_{a∈A} x^{2a}y^{2}} ,  (3)

while the bivariate generating function of F_{A}^{L_{1}}(N; K) is

∑_{N,K≥1} F_{A}^{L_{1}}(N; K) x^{N}y^{K} = \frac{∑a∈A \frac{x^{a}y}{1+x^{2a}y^{2}}}{1 − ∑_{a∈A} \frac{x^{2a}y^{2}}{1+x^{2a}y^{2}}} .  (4)

It is clear that, if K is even, then F_{A}^{L_{1}}(N; K) = 0. (We assume that P_{A}^{L_{1}}(0; 0) = F_{A}^{L_{1}}(0; 0) = 1 and P_{A}^{L_{1}}(N; 0) = F_{A}^{L_{1}}(N; 0) = 0 for N ≠ 0.)

Hadjicostas and Zhang [11] also proved that the bivariate generating function of the numbers P_{A}^{L_{2}}(N; K) is given by

∑_{N,K≥1} P_{A}^{L_{2}}(N; K) x^{N}y^{K} = \frac{(∑_{a∈A} x^{a}) y + (∑_{a∈A} x^{a})^{2} y^{2}}{1 − y^{2} ∑_{a∈A} x^{2a}} .  (5)

The bivariate generating function of F_{A}^{L_{2}}(N; K) is given in Theorem 3 later in this section.

Sommerville [22, pp. 301–304] examined symmetrical CR-type cyclic compositions of N with length K. In the terminology of Hadjicostas and Zhang [11], a CR-type cyclic composition of N with length K is called symmetrical if and only if its equivalence class contains at least one type I or II linear palindromic composition. Hadjicostas and Zhang [11] proved that, if N, K > 1, then the equivalence class of every symmetrical cyclic composition of N with length K (but excluding the one with all the parts being equal when K divides N) contains exactly two linear palindromic compositions of type I or II. As a result, after including the trivial case K = 1, the number of symmetrical CR-type cyclic compositions of N with K parts in A ⊆ ℤ_{>0} is

P_{A}^{CR}(N; K) = \frac{P_{A}^{L_{1}}(N; K) + P_{A}^{L_{2}}(N; K)}{2} for 1 ≤ K ≤ N.  (6)

As Hadjicostas and Zhang [11] have shown, equations (3), (5) and (6) imply that the bivariate generating function of P_{A}^{CR}(N, K) is

∑_{N,K≥1} P_{A}^{CR}(N, K) x^{N}y^{K} = \frac{(1 + y ∑_{a∈A} x^{a})^{2}}{2 (1 − y^{2} ∑_{a∈A} x^{2a})} − \frac{1}{2}.

Hadjicostas and Zhang [11] also observed that the number of dihedral compositions of N with K parts in A is

c_{A}^{D}(N; K) = \frac{c_{A}^{CR}(N; K) − P_{A}^{CR}(N; K)}{2} + P_{A}^{CR}(N; K)  (7)
= \frac{c_{A}^{CR}(N; K) + P_{A}^{CR}(N; K)}{2}
= \frac{2c_{A}^{CR}(N; K) + P_{A}^{L_{1}}(N; K) + P_{A}^{L_{2}}(N; K)}{4}.

It follows that the bivariate generating function of c_{A}^{D}(N; K) is

∑_{N,K≥1} c_{A}^{D}(N; K) x^{N}y^{K} = \frac{1}{2} ∑_{s≥1} \frac{ϕ(s)}{s} log \frac{1}{1 − y^{s} ∑_{a∈A} x^{as}} + \frac{(1 + y ∑_{a∈A} x^{a})^{2}}{4 (1 − y^{2} ∑_{a∈A} x^{2a})} − \frac{1}{4}.

In this paper, we prove a number of new results and give new proofs to some others found in the literature about generating functions of numbers of Carlitz compositions of special kinds. The first result gives the univariate generating function of the number of L-type Carlitz compositions with fixed length K and parts in a set A. The proofs of all the results can be found in Section 3.

Theorem 1. Let K ∈ ℤ_{>0} and A ⊆ ℤ_{>0}. Then

∑_{N≥1} E_{A}^{L}(N; K) x^{N} = ∑ \frac{(ℓ_{1} + ⋯ + ℓ_{K})!(−1)^{ℓ_{1}+···+ℓ_{K}+K}}{ℓ_{1}! ⋯ ℓ_{K}!} ∏_{i=1}^{K} (∑_{a∈A} x^{ia})^{ℓ_{i}} ,  (8)

where the sum ranges over the set

L_{K} = {(ℓ_{1}, ℓ_{2}, …, ℓ_{K}) ∈ ℤ_{≥0}^{K} : ∑_{i=1}^{K} iℓ_{i} = K}

of all integer partitions of K.

The second result gives the univariate generating function of the number of type I linear palindromic Carlitz compositions with fixed length K and parts in a set A.

Theorem 2. Let K = 2ρ + 1 with ρ ∈ ℤ_{≥0} and A ⊆ ℤ_{>0}. Then

∑_{N≥1} F_{A}^{L_{1}}(N; K) x^{N} = ∑_{N≥1} F_{A}^{L_{1}}(N; 2ρ + 1) x^{N}

= ∑ \frac{(α_{1} + ⋯ + α_{ρ})! (−1)^{α_{1}+···+α_{ρ}+ρ}}{α_{1}! ⋯ α_{ρ}!} (∑_{a∈A} x^{(2ρ+1−2 ∑_{i=1}^{ρ} iα_{i})a}) ∏_{i=1}^{ρ} (∑_{a∈A} x^{2ia})^{α_{i}} , (9)

where the sum ranges over the set

M_{ρ} = {(α_{1}, α_{2}, …, α_{ρ}) ∈ ℤ_{≥0}^{ρ} : ∑_{i=1}^{ρ} iα_{i} ≤ ρ}.  (10)

(Here, M_{0} = {()} (set with the empty list), ∑_{i=1}^{0} α_{i} = 0 and ∏_{i=1}^{0} β_{i} = 1.)

For ρ ∈ ℤ_{>0}, the number of elements, #M_{ρ}, of the set M_{ρ} above is given by the sequence \underline{A000070}. It can be easily shown that #M_{ρ} = 1 + ∑_{s=1}^{ρ} #L_{s}.

The next result gives the bivariate generating function of F_{A}^{L_{2}}(N; K).

Theorem 3. The bivariate generating function of the number of type-II linear palindromic Carlitz compositions of positive integer N with K parts in set A ⊆ ℤ_{>0} is

∑_{N,K≥1} F_{A}^{L_{2}}(N; K) x^{N}y^{K} = \frac{(∑a∈A \frac{x^{a}y}{1+x^{2a}y^{2}} )2}{1 − ∑_{a∈A} \frac{x^{2a}y^{2}}{1+x^{2a}y^{2}}} − ∑_{a∈A} \frac{x^{2a}y^{2}}{1 + x^{2a}y^{2}} + ∑_{a∈A} x^{a}y.

If K is an odd integer ≥ 3, then F_{A}^{L_{2}}(N; K) = 0.

Next we state a result about the number of C-type cyclic Carlitz compositions of N with K parts in the set A ⊆ ℤ_{>0}. The result follows from Corollary 5.3 in Taylor [23], who has used a general theory involving Laguerre series to prove it. In this paper, we provide another (independent) proof of the result in Section 3.

Theorem 4. If A ⊆ ℤ_{>0}, then

∑_{N,K≥1} E_{A}^{C}(N; K) x^{N}y^{K} = ∑_{a∈A} \frac{x^{2a}y^{2}}{1 + x^{a}y} + \frac{∑a∈A \frac{x^{a}y}{(1+x^{a}y)^{2}}}{1 − ∑_{a∈A} \frac{x^{a}y}{1+x^{a}y}} .  (11)

Letting y = 1 in equation (11) of Theorem 4 above, we get the generating function of the total number of C-type cyclic compositions of N with parts in the set A ⊆ ℤ_{>0}. This is Corollary 5.4 in Taylor [23], which is an answer to a research question posed by Heubach and Mansour [13, pp. 87–88].

Corollary 5. If A ⊆ ℤ_{>0}, then

∑_{N≥1} E_{A}^{C}(N) x^{N} = ∑_{a∈A} \frac{x^{2a}}{1 + x^{a}} + \frac{∑a∈A \frac{x^{a}}{(1+x^{a})^{2}}}{1 − ∑_{a∈A} \frac{x^{a}}{1+x^{a}}} .  (12)

We would like to use the methodology in Hadjicostas [10] (and that in Zhang and Hadjicostas [25]) to derive a relationship between the numbers of CR-type cyclic Carlitz compositions of positive integers with parts in a set A and the numbers of C-type cyclic Carlitz compositions of positive integers with parts in A. Such formulas would help us derive generating functions for the numbers of CR-type cyclic Carlitz compositions of positive integers with parts in A and such results would be reminiscent of the theory in Flajolet and Sedgewick [8] and Flajolet and Soria [9]. The problem, however, is that we cannot use this theory directly without modifying the definitions of E_{A}^{C}(N; K) and E_{A}^{CR}(N; K). To understand why, let us define the period h of a circular (CR-type cyclic) composition [(λ_{1}, …, λ_{K})]_{CR} of N with length K to be the length of the shortest subsequence of λ_{i}’s with consecutive indices that is able to reproduce (λ_{1}, …, λ_{K}) by repeating itself K/h times. If we denote by E_{A}^{CR}(N; K; h) the number of all CR-type cyclic Carlitz compositions of N with length K, period h, and parts in A, a key desirable formula we would like to hold is that, for 1 ≤ K ≤ N,

E_{A}^{CR} (N; K; \frac{K}{d} ) = E_{A}^{CR} (\frac{N}{d}; \frac{K}{d}; \frac{K}{d} ) for all positive divisors d of gcd(N, K). (13)

The last formula would follow from the following fact (if it were true): every CR-type cyclic Carlitz composition of N with length K, period K/d, and parts in A can be partitioned into d identical CR-type cyclic Carlitz compositions of N/d with length K/d, period K/d and parts in A.

The above claim is always true except when K|N, d = K > 1 and N/d ∈ A. In this case, we get

E_{A}^{CR} (N; K; \frac{K}{d} = 1) = 0 ≠ 1 = E_{A}^{CR} (\frac{N}{d}; \frac{K}{d} = 1; \frac{K}{d} = 1)

because in this paper, following Taylor [23], we make the convention that [(n)]_{CR} is a (CRtype cyclic) Carlitz composition for each n ∈ ℤ_{>0}.

To fix the problem, we define Ẽ_{A}^{C}(N; K) = E_{A}^{C}(N; K) if 2 ≤ K ≤ N, and 0 if K = 1. Similarly, we let Ẽ_{A}^{CR}(N; K) = E_{A}^{CR}(N; K) if 2 ≤ K ≤ N, and 0 if K = 1. In such a case, equalities (13) hold when E_{A}^{CR} is replaced with Ẽ_{A}^{CR}. Note that

E_{A}^{C}(N) = Ẽ_{A}^{C}(N) + I(N ∈ A) and E_{A}^{CR}(N) = Ẽ_{A}^{CR}(N) + I(N ∈ A).

(Here, I(x ∈ A) = 1 if x ∈ A, and 0 otherwise.)

Equations (14) and (15) below express numbers of (modified) CR-type cyclic Carlitz compositions in terms of numbers of (modified) C-type cyclic Carlitz compositions.

Theorem 6. Let N, K ∈ ℤ_{>0} with 1 ≤ K ≤ N. The (modified) number of CR-type cyclic Carlitz compositions of N of length K with parts in A ⊆ ℤ_{>0} is given by

Ẽ_{A}^{CR}(N; K) = \frac{1}{K} ∑_{s| gcd(N,K)} ϕ(s) Ẽ_{A}^{C} (\frac{N}{s}; \frac{K}{s} ) .  (14)

Also, the total number of cyclic compositions (of any length) of N with parts in A is

Ẽ_{A}^{CR}(N) = \frac{1}{N} ∑_{d|N} ϕ(d)g_{A} (\frac{N}{d} ) ,  (15)

where

g_{A}(s) = s ∑_{k=1}^{s} \frac{Ẽ_{A}^{C}(s; k)}{k} for s ∈ ℤ_{>0}.  (16)

The generating function of Ẽ_{A}^{CR}(N; K) is given by

∑_{N,K≥1} Ẽ_{A}^{CR}(N; K) x^{N}y^{K} = ∑_{s≥1} \frac{ϕ(s)}{s}G_{A}(x^{s}, y^{s}),

where

G_{A}(x, y) = − ∑_{a∈A} log(1 + x^{a}y) − log (1 − ∑_{a∈A} \frac{x^{a}y}{1 + x^{a}y} ) .  (17)

We let F_{A}^{CR}(N; K) denote the number of symmetrical CR-type cyclic Carlitz compositions of N with K parts in the set A ⊆ ℤ_{>0}. The following result gives a formula and the bivariate generating function for these numbers. To derive the latter, we need to use Theorem 3 above that gives the bivariate generating function of the number of type-II linear palindromic Carlitz compositions.

Theorem 7. Let N, K ∈ ℤ_{>0} with 1 ≤ K ≤ N. Then the number of symmetrical CR-type cyclic Carlitz compositions of N with K parts in the set A ⊆ ℤ_{>0} is given by the formula

F_{A}^{CR}(N; K) = \begin{cases}\frac{F_{A}^{L_{2}}(N;K)}{2}, & if 2 ≤ K ≤ N; \\ I(N ∈ A), & if K = 1. \end{cases}

(Thus, if K is an odd integer ≥ 3, then F_{A}^{CR}(N; K) = 0.) The corresponding generating function is

∑_{N,K≥1} F_{A}^{CR}(N; K) x^{N}y^{K} = \frac{(∑a∈A \frac{x^{a}y}{1+x^{2a}y^{2}} )2}{2(1 − ∑_{a∈A} \frac{x^{2a}y^{2}}{1+x^{2a}y^{2}} )} − \frac{1}{2} ∑_{a∈A} \frac{x^{2a}y^{2}}{1 + x^{2a}y^{2}} + ∑_{a∈A} x^{a}y.  (18)

Letting y = 1 in the above bivariate generating function (18), we get the following corollary.

Corollary 8. Let A ⊆ ℤ_{>0}. Then the total number of symmetrical CR-type cyclic Carlitz compositions of N ∈ ℤ_{>0} with parts in the set A is given by the formula

F_{A}^{CR}(N) = \frac{F_{A}^{L_{2}}(N) + I(N ∈ A)}{2},

while the corresponding generating function is

∑_{N≥1} F_{A}^{CR}(N) x^{N} = \frac{(∑a∈A \frac{x^{a}}{1+x^{2a}} )2}{2(1 − ∑_{a∈A} \frac{x^{2a}}{1+x^{2a}})} − \frac{1}{2} ∑_{a∈A} \frac{x^{2a}}{1 + x^{2a}} + ∑_{a∈A} x^{a}.

Finally, we let E_{A}^{D}(N; K) denote the number of dihedral Carlitz compositions of N with length K and parts in A ⊆ ℤ_{>0}. We then have the following result.

Theorem 9. If N, K ∈ ℤ_{>0}, with 1 ≤ K ≤ N, and A ⊆ ℤ_{>0}, then

E_{A}^{D}(N; K) = \frac{E_{A}^{CR}(N; K) + F_{A}^{CR}(N; K)}{2} = \begin{cases}\frac{2E_{A}^{CR}(N;K)+F_{A}^{L_{2}}(N;K)}{4}, & if 2 ≤ K ≤ N; \\ I(N ∈ A), & if K = 1. \end{cases}

It is possible to write down the bivariate generating function of E_{A}^{D}(N; K) by using Theorems 6–9. We omit it because it is too complicated.

Corollary 10. If N ∈ ℤ_{>0} and A ⊆ ℤ_{>0}, then

E_{A}^{D}(N) = \frac{E_{A}^{CR}(N) + F_{A}^{CR}(N)}{2} = \frac{2E_{A}^{CR}(N) + F_{A}^{L_{2}}(N) + I(N ∈ A)}{4}.

The organization of the paper is as follows. In Section 2 we give examples that illustrate the definitions and results of the paper, while in Section 3 we give the proofs of the results of the paper. Finally, in Section 4, we discuss some future research proposals related to the papers by Bender and Canfield [2, 3, 4] and Bender, Canfield, and Gao [5].

Description  Compositions (or equivalence classes of compositions)
with length 1  [(5)]_{CR}
with length 2  [(1, 4)]_{CR} = [(4, 1)]_{CR}, [(2, 3)]_{CR} = [(3, 2)]_{CR}
with length 3  [(1, 1, 3)]_{CR} = [(3, 1, 1)]_{CR} = [(1, 3, 1)]_{CR},
[(1, 2, 2)]_{CR} = [(2, 1, 2)]_{CR} = [(2, 2, 1)]_{CR}
with length 4  [(1, 1, 1, 2)]_{CR} = [(2, 1, 1, 1)]_{CR} = [(1, 2, 1, 1)]_{CR} = [(1, 1, 2, 1)]_{CR}
with length 5  [(1, 1, 1, 1, 1)]_{CR}
c_{ℤ_{>0}}^{L}(N = 5) = 16 see above
c_{ℤ_{>0}}^{CR}(N = 5) = 7 see above
P_{ℤ_{>0}}^{L_{1}}(N = 5) = 4 (5), (1,3,1), (2,1,2), (1,1,1,1,1)
P_{ℤ_{>0}}^{L_{2}}(N = 5) = 10 (5), (1, 4), (4, 1), (2, 3), (3, 2), (3, 1, 1), (1, 2, 2),
(2, 1, 1, 1), (1, 1, 2, 1), (1, 1, 1, 1, 1)
P_{ℤ_{>0}}^{CR}(N = 5) = 7 [(5)]_{CR}, [(1, 4)]_{CR}, [(2, 3)]_{CR}, [(1, 3, 1)]_{CR}, [(2, 1, 2)]_{CR},
[(2, 1, 1, 1)]_{CR}, [(1, 1, 1, 1, 1)]_{CR}
c_{ℤ_{>0}}^{D}(N = 5) = 7 same as above for P_{ℤ_{>0}}^{CR}(N = 5) with ‘CR’ replaced with ‘D’
E_{ℤ_{>0}}^{L}(N = 5) = 7 (5), (1, 4), (4, 1), (2, 3), (3, 2), (1, 3, 1), (2, 1, 2)
E_{ℤ_{>0}}^{C}(N = 5) = 5 (5), (1, 4), (4, 1), (2, 3), (3, 2)
E_{ℤ_{>0}}^{CR}(N = 5) = 3 [(5)]_{CR}, [(1, 4)]_{CR}, [(2, 3)]_{CR}
E_{ℤ_{>0}}^{D}(N = 5) = 3 [(5)]_{D}, [(1, 4)]_{D}, [(2, 3)]_{D}
F_{ℤ_{>0}}^{L_{1}}(N = 5) = 3 (5), (1, 3, 1), (2, 1, 2)
F_{ℤ_{>0}}^{L_{2}}(N = 5) = 5 (5), (1, 4), (4, 1), (2, 3), (3, 2)
F_{ℤ_{>0}}^{CR}(N = 5) = 3 [(5)]_{CR}, [(1, 4)]_{CR}, [(2, 3)]_{CR}

Table 1: Various kinds of compositions when N = 5 and A = ℤ_{>0}

2 Examples

In this section, we illustrate the different definitions and results from Section 1 of the paper. In Table 1, we enumerate all the compositions of N = 5 with parts in A = ℤ_{>0}, and we categorize them on whether they are palindromic (of either type), Carlitz, etc. In addition, we categorize equivalence classes of these compositions on whether they are cyclic, dihedral, symmetrical, etc.

Note that, by coincidence, all dihedral compositions of N = 5 are also symmetrical CRtype cyclic as well. (Note that c_{ℤ_{>0}}^{D}(N = 5) = 7 = P_{ℤ_{>0}}^{CR}(N = 5).) In general, however, that is not the case. For example, if N = 6, then

[(1, 2, 3)]_{CR} = {(1, 2, 3), (2, 3, 1), (3, 1, 2)},

while

[(1, 2, 3)]_{D} = {(1, 2, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1), (1, 3, 2), (2, 1, 3)}.

\begin{matrix}N & F_{ℤ_{>0}}^{L_{1}}(N) & F_{ℤ_{>0}}^{L_{2}}(N) & F_{ℤ_{>0}}^{CR}(N) & E_{ℤ_{>0}}^{C}(N) & E_{ℤ_{>0}}^{CR}(N) & E_{ℤ_{>0}}^{D}(N) \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 1 & 1 & 1 & 1 & 1 \\ 3 & 1 & 3 & 2 & 3 & 2 & 2 \\ 4 & 2 & 3 & 2 & 3 & 2 & 2 \\ 5 & 3 & 5 & 3 & 5 & 3 & 3 \\ 6 & 2 & 7 & 4 & 13 & 6 & 5 \\ 7 & 5 & 9 & 5 & 17 & 7 & 6 \\ 8 & 5 & 13 & 7 & 29 & 11 & 9 \\ 9 & 7 & 19 & 10 & 55 & 18 & 14 \\ 10 & 10 & 21 & 11 & 99 & 29 & 20 \\ 11 & 14 & 31 & 16 & 161 & 42 & 29 \\ 12 & 14 & 45 & 23 & 293 & 73 & 48 \\ 13 & 25 & 53 & 27 & 507 & 111 & 69 \\ 14 & 26 & 73 & 37 & 881 & 183 & 110 \\ 15 & 42 & 101 & 51 & 1561 & 299 & 175 \\ 16 & 48 & 129 & 65 & 2727 & 491 & 278 \\ 17 & 75 & 171 & 86 & 4743 & 796 & 441 \\ 18 & 79 & 233 & 117 & 8337 & 1333 & 725 \\ 19 & 132 & 295 & 148 & 14579 & 2188 & 1168 \\ 20 & 142 & 407 & 204 & 25497 & 3652 & 1928 \end{matrix}

Table 2: Evaluations of F_{A}^{L_{1}}(N), F_{A}^{L_{2}}(N), F_{A}^{CR}(N) (numbers of palindromic/symmetric Carlitz compositions) and E_{A}^{C}(N), E_{A}^{CR}(N) and E_{A}^{D}(N) (numbers of cyclic/dihedral Carlitz compositions) for N = 1(1)20 when A = ℤ_{>0}

In Table 2, we evaluate the following quantities from N = 1 to N = 20 when A = ℤ_{>0}:

• F_{A}^{L_{1}}(N) = total number of type I palindromic Carlitz compositions of N (this is sequence \underline{A239327} in OEIS);

• F_{A}^{L_{2}}(N) = total number of type II palindromic Carlitz compositions of N;

• F_{A}^{CR}(N) = total number of symmetrical CR-type cyclic Carlitz compositions of N;

• E_{A}^{C}(N) = total number of C-type cyclic Carlitz compositions of N (this is sequence \underline{A212322} in OEIS);

• E_{A}^{CR}(N) = total number of CR-type cyclic Carlitz compositions of N (this is sequence \underline{A106369} in OEIS);

• E_{A}^{D}(N) = total number of dihedral Carlitz compositions of N.

Next we illustrate Theorems 1 and 2. Theorem 1 implies that

∑_{N≥1} E_{A}^{L}(N; K = 1) x^{N} = ∑_{a∈A} x^{a} with L_{1} = {(1)};
∑_{N≥1} E_{A}^{L}(N; K = 2) x^{N} = (∑_{a∈A} x^{a})^{2} − ∑_{a∈A} x^{2a} with L_{2} = {(2, 0), (0, 1)};
∑_{N≥1} E_{A}^{L}(N; K = 3) x^{N} = (∑_{a∈A} x^{a})^{3} − 2 (∑_{a∈A} x^{a}) (∑_{a∈A} x^{2a}) + ∑_{a∈A} x^{3a}

with L_{3} = {(3, 0, 0), (1, 1, 0), (0, 0, 1)};

∑_{N≥1} E_{A}^{L}(N; K = 4) x^{N} = (∑_{a∈A} x^{a})^{4} − 3 (∑_{a∈A} x^{a})^{2} (∑_{a∈A} x^{2a})

+2 (∑_{a∈A} x^{a}) (∑_{a∈A} x^{3a}) + (∑_{a∈A} x^{2a})^{2} − ∑_{a∈A} x^{4a}

with L_{4} = {(4, 0, 0, 0), (2, 1, 0, 0), (1, 0, 1, 0), (0, 2, 0, 0), (0, 0, 0, 1)}.

Finally, Theorem 2 implies

∑_{N≥1} F_{A}^{L_{1}}(N; K = 1) x^{N} = ∑_{a∈A} x^{a} with ρ = 0 and M_{0} = {()};
∑_{N≥1} F_{A}^{L_{1}}(N; K = 3) x^{N} = − ∑_{a∈A} x^{3a} + (∑_{a∈A} x^{a}) (∑_{a∈A} x^{2a}) with ρ = 1 and M_{1} = {(0), (1)};
∑_{N≥1} F_{A}^{L_{1}}(N; K = 5) x^{N} = ∑_{a∈A} x^{5a} − (∑_{a∈A} x^{3a}) (∑_{a∈A} x^{2a}) + (∑_{a∈A} x^{a}) (∑_{a∈A} x^{2a})^{2}

− (∑_{a∈A} x^{a}) (∑_{a∈A} x^{4a})

with ρ = 2 and M_{2} = {(0, 0), (1, 0), (2, 0), (0, 1)}.

3 Proofs

If K, b_{1}, …, b_{K} ∈ ℤ_{>0}, define the multinomial coefficient

\binom{b_{1} + ⋯ + b_{K}}{b_{1}, …, b_{K}} = \frac{(b_{1} + ⋯ + b_{K})!}{b_{1}! ⋯ b_{K}!}.

We recall a result about multinomial coefficients that is used in the proofs of Theorems 1 and 2 later in the paper. If K, β_{1}, …, β_{K} ∈ ℤ_{>0} and N = ∑_{s=1}^{K} β_{s}, then

\binom{N}{β_{1}, …, β_{K}} = ∑_{s=1}^{K} \binom{N − 1}{β_{1}, …, β_{s−1}, β_{s} − 1, β_{s+1}, …, β_{K}}.  (19)

Proof of Theorem 1. We proceed by induction on K. For K = 1, equation (8) holds because

∑_{N≥1} E_{A}^{L}(N; K = 1) x^{N} = ∑_{a∈A} x^{a} = \frac{1!(−1)^{1+1}}{1!} (∑_{a∈A} x^{1a})^{1} .

Let M ≥ 2, and assume equation (8) holds for all positive integers K < M. Define

B_{K}(x) = ∑_{N≥1} E_{A}^{L}(N; K) x^{N}.

It follows from equation (2) that

(1 + ∑_{K≥1} B_{K}(x) y^{K}) (1 + ∑_{a∈A} ∑_{s=1}^{∞}(−1)^{s}x^{sa}y^{s}) = 1,

and hence,

∑_{K=1}^{∞} B_{K}(x) y^{K} + ∑_{s=1}^{∞}(−1)^{s} (∑_{a∈A} x^{sa}) y^{s} + (∑_{K=1}^{∞} B_{K}(x) y^{K}) (∑_{s=1}^{∞}(−1)^{s} (∑_{a∈A} x^{sa}) y^{s}) = 0.

It follows that, for K = M,

B_{M}(x) = (−1)^{M+1} ∑_{a∈A} x^{Ma} + ∑_{ℓ=1}^{M−1} B_{ℓ}(x)(−1)^{M−ℓ+1} (∑_{a∈A} x^{(M−ℓ)a}) .  (20)

We conclude from equation (8) that, for ℓ = 1, …, M − 1,

B_{ℓ}(x) = ∑_{L_{ℓ}} \frac{(∑_{s=1}^{ℓ} α_{ℓ,s})!}{α_{ℓ,1}! ⋯ α_{ℓ,ℓ}!}(−1)^{∑_{s=1}^{ℓ} α_{ℓ,s}+ℓ} ∏_{i=1}^{ℓ} (∑_{a∈A} x^{ia})^{α_{ℓ,i}} ,  (21)

where L_{ℓ} = {(α_{ℓ,1}, …, α_{ℓ,ℓ}) ∈ ℤ_{≥0}^{ℓ} : ∑_{s=1}^{ℓ} sα_{ℓ,s} = ℓ}. Assume

α_{ℓ,s} = 0 for ℓ + 1 ≤ s ≤ M,

and define

L̃_{ℓ} = {(α_{ℓ,1}, …, α_{ℓ,ℓ}, 0, …, 0) ∈ ℤ_{≥0}^{M} : ∑_{s=1}^{ℓ} sα_{ℓ,s} = ℓ}.

Then, equations (20) and (21) imply

B_{M}(x) = ∑_{ℓ=1}^{M−1} ∑ ; L̃_{ℓ} \frac{(∑_{s=1}^{M} α_{ℓ,s})!}{α_{ℓ,1}! ⋯ α_{ℓ,M}!}(−1)^{∑_{s=1}^{M} α_{ℓ,s}+M+1} ∏_{{i=1 \atop i≠M−ℓ}}^{M} (∑_{a∈A} x^{ia})^{α_{ℓ,i}} (∑_{a∈A} x^{(M−ℓ)a})^{α_{ℓ,M−ℓ}+1}

+(−1)^{M+1} ∑_{a∈A} x^{Ma}.  (22)

We seek to prove that

B_{M}(x) = ∑_{L_{M}} \frac{(∑_{s=1}^{M} α_{M,s})!}{α_{M,1}! ⋯ α_{M,M}!}(−1)^{∑_{s=1}^{M} α_{M,s}+M} ∏_{i=1}^{M} (∑_{a∈A} x^{ia})^{α_{M,i}} .  (23)

The term (−1)^{M+1} ∑_{a∈A} x^{Ma} in equation (22) corresponds to the case

α_{M,1} = ⋯ = α_{M,M−1} = 0 and α_{M,M} = 1.

Hence, for all other elements (cases) in L_{M} we have α_{M,M} = 0.

For α = (α_{M,1}, …, α_{M,M−1}, 0) ∈ L_{M}, for which of course we have ∑_{s=1}^{M−1} sα_{M,s} = M, in the double sum in equation (22), we need to find the sum of the coefficients that correspond to the product (term) ∏_{s=1}^{M−1} (∑_{a∈A} x^{sa})^{α_{M,s}} . We prove below that this sum of coefficients equals the coefficient of this term given in equation (23) above.

We define

D(α) = {ℓ ∈ {1, 2, …, M − 1} : α_{M,M−ℓ} ≥ 1}.

By equation (19),

\frac{(∑_{s=1}^{M−1} α_{M,s})!}{∏_{s=1}^{M−1} α_{M,s}!} = ∑_{ℓ∈D(α)} (\frac{(∑_{s=1}^{M−1}α_{M,s} − 1)!}{( ∏_{{s=1 \atop s≠M−ℓ}}^{M−1}α_{M,s}!) (α_{M,M−ℓ} − 1)!}) .  (24)

If ℓ ∈ D(α), then

∑_{{s=1 \atop s≠M−ℓ}}^{M−1} sα_{M,s} + (M − ℓ)(α_{M,M−ℓ} − 1) = ℓ,

which implies α_{M,ℓ+1} = ⋯ = α_{M,M−1} = 0; i.e.,

α^{(ℓ)} = (α_{M,1}, …, α_{M,M−ℓ−1}, α_{M,M−ℓ} − 1, α_{M,M−ℓ+1}, …, α_{M,M−1}, 0) ∈ L̃_{ℓ}.

On the other hand, let ℓ ∈ {1, 2, …, M − 1} and β^{(ℓ)} = (β_{ℓ,1}, …, β_{ℓ,ℓ}, 0, …, 0) ∈ L̃_{ℓ} with β_{ℓ,s} = 0 for ℓ + 1 ≤ s ≤ M, and assume that, in (22),

∏_{{i=1 \atop i≠M−ℓ}}^{M} (∑_{a∈A} x^{ia})^{β_{ℓ,i}} (∑_{a∈A} x^{(M−ℓ)a})^{β_{ℓ,M−ℓ}+1} = ∏_{s=1}^{M−1} (∑_{a∈A} x^{sa})^{α_{M,s}} .

Hence, β_{ℓ,s} = α_{M,s} for 1 ≤ s ≠ M − ℓ ≤ M − 1, β_{ℓ,M−ℓ} + 1 = α_{M,M−ℓ} ≥ 1, β_{ℓ,M} = α_{M,M} = 0, and ℓ ∈ D(α). In addition,

∑_{s=1}^{M} β_{ℓ,s} + M + 1 = ∑_{s=1}^{M} α_{M,s} + M.  (25)

We conclude from equations (24) and (25) that the sum of the coefficients that corre-

spond to the product ∏_{s=1}^{M−1} (∑_{a∈A} x^{sa})^{α_{M,s}} in equation (22) is equal to \frac{(∑_{s=1}^{M−1} α_{M,s})!}{∏_{s=1}^{M−1} α_{M,s}!}. This establishes equation (23) and the induction step is complete.

Proof of Theorem 2. We prove (9) by induction on ρ. For ρ = 0, equation (9) holds with M_{0} = {()} (set with the empty list), ∑_{i=1}^{0} β_{i} = 0 (an empty sum equals 0) and ∏_{i=1}^{0} γ_{i} = 1 (an empty product equals 1):

∑_{N≥1} F_{A}^{L_{1}}(N; 1) x^{N} = ∑_{a∈A} x^{a} = \frac{0!(−1)^{0+0}}{1} (∑_{a∈A} x^{(2·0+1−0)a}) · 1.

Let r ≥ 1, and assume equation (9) holds for all nonnegative integers ρ < r. Let

C_{ρ}(x) = ∑_{N≥1} F_{A}^{L_{1}}(N; 2ρ + 1) x^{N}.

It follows from equation (4) that

(∑_{ρ=0}^{∞} C_{ρ}(x) y^{2ρ+1}) (1 + ∑_{a∈A} ∑_{s=1}^{∞}(−1)^{s}x^{2as}y^{2s}) = ∑_{a∈A} ∑_{s=0}^{∞}(−1)^{s}x^{(2s+1)a}y^{2s+1}.

Therefore,

∑_{s=0}^{∞}(−1)^{s} (∑_{a∈A} x^{(2s+1)a}) y^{2s+1} = (∑_{ρ=0}^{∞} C_{ρ}(x) y^{2ρ+1}) (∑_{s=1}^{∞}(−1)^{s} (∑_{a∈A} x^{2sa}) y^{2s})

+ ∑_{ρ=0}^{∞} C_{ρ}(x) y^{2ρ+1}.

Hence, when ρ = r,

C_{r}(x) = ∑_{σ=0}^{r−1} C_{σ}(x)(−1)^{r−σ+1} (∑_{a∈A} x^{2(r−σ)a}) + (−1)^{r} ∑_{a∈A} x^{(2r+1)a}.  (26)

We let D_{1} and D_{2} denote the two terms on the right-hand side of the above equation, i.e., C_{r}(x) = D_{1} + D_{2}. Next, note that the set M_{ρ}, defined by equation (10), can be written as

M_{ρ} = ⋃_{k=0}^{ρ} K_{ρ,k}, where K_{ℓ,k} = {(α_{ℓ,1}, …, α_{ℓ,ℓ}) ∈ ℤ_{≥0}^{ℓ} : ∑_{s=1}^{ℓ} sα_{ℓ,s} = k}.

If 0 ≤ k ≤ ℓ, then

K_{ℓ,k} = {(α_{ℓ,1}, …, α_{ℓ,k}, 0, …, 0) ∈ ℤ_{≥0}^{ℓ} : ∑_{s=1}^{k} sα_{ℓ,s} = k}.

In particular, K_{ℓ,0} = {(0, …, 0)}, where the list inside the set has ℓ zeros.

By the induction hypothesis, we conclude from equation (9) that, for ρ = 0, 1, …, r − 1,

C_{ρ}(x) = ∑_{k=0}^{ρ} (∑_{a∈A} x^{(2ρ+1−2k)a}) ∑_{K_{ρ,k}} \frac{(∑_{s=1}^{ρ} α_{ρ,s})!(−1)^{∑_{s=1}^{ρ} α_{ρ,s}+ρ}}{∏_{s=1}^{ρ} α_{ρ,s}!} ∏_{s=1}^{ρ} (∑_{a∈A} x^{2sa})^{α_{ρ,s}} . (27)

In equation (27), we may replace the sum ∑_{K_{ρ,k}} with ∑ ; K̃_{ρ,k}, where

K̃_{ρ,k} = {(α_{ρ,1}, …, α_{ρ,k}, 0, …, 0) ∈ ℤ_{≥0}^{r} : ∑_{s=1}^{k} sα_{ρ,s} = k};

i.e., we assume α_{ρ,s} = 0 for 0 ≤ ρ ≤ r − 1 and ρ + 1 ≤ s ≤ r. (Of course, for 0 ≤ k ≤ ρ, we also have α_{ρ,s} = 0 for k + 1 ≤ s ≤ ρ.) Also, we may replace ∑_{s=1}^{ρ} α_{ρ,s} with ∑_{s=1}^{r} α_{ρ,s} and ∏_{s=1}^{ρ} with ∏_{s=1}^{r}.

We wish to prove that

C_{r}(x) = ∑_{m=0}^{r} (∑_{a∈A} x^{(2r+1−2m)a}) ∑_{K_{r,m}} \frac{(∑_{s=1}^{r} α_{r,s})!(−1)^{∑_{s=1}^{r} α_{r,s}+r}}{∏_{s=1}^{r} α_{r,s}!} ∏_{s=1}^{r} (∑_{a∈A} x^{2sa})^{α_{r,s}} (28)

= ∑_{m=1}^{r} (∑_{a∈A} x^{(2r+1−2m)a}) ∑_{K_{r,m}} \frac{(∑_{s=1}^{r} α_{r,s})!(−1)^{∑_{s=1}^{r} α_{r,s}+r}}{∏_{s=1}^{r} α_{r,s}!} ∏_{s=1}^{r} (∑_{a∈A} x^{2sa})^{α_{r,s}}
+(−1)^{r} ∑_{a∈A} x^{(2r+1)a}.  (29)

We let D_{3} and D_{2} denote the two terms on the right-hand side of equation (29). (Term D_{2} appears in equation (26) as well). Equations (26) and (27) yield

D_{1} = ∑_{σ=0}^{r−1} ∑_{k=0}^{σ} (∑_{a∈A} x^{(2σ+1−2k)a}) L(σ, k, r),  (30)

where

L(σ, k, r) = ∑ ; K̃_{σ,k} \frac{(∑_{s=1}^{r} α_{σ,s})!(−1)^{∑_{s=1}^{r} α_{σ,s}+r+1}}{∏_{s=1}^{r} α_{σ,s}!} ∏_{{s=1 \atop s≠r−σ}}^{r} (∑_{a∈A} x^{2sa})^{α_{σ,s}} (∑_{a∈A} x^{2(r−σ)a})^{α_{σ,r−s}+1} .

(31)

To finish the inductive step, we need to prove that D_{1} = D_{3}. To achieve that, we need to prove that the coefficient of the term

(∑_{a∈A} x^{(2r+1−2m)a}) ∏_{s=1}^{r} (∑_{a∈A} x^{2sa})^{α_{r,s}} , for fixed m ∈ {1, …, r} and (α_{r,1}, …, α_{r,r}) ∈ K_{r,m},

in the quantity D_{3} in equation (29), equals the sum of the coefficients of the same term in quantity D_{1} in equations (30) and (31).

By matching coefficients, one can see from equations (29)-(31) that we need to prove that

\frac{(∑_{s=1}^{r} α_{r,s})!(−1)^{∑_{s=1}^{r} α_{r,s}+r}}{∏_{s=1}^{r} α_{r,s}!} = ∑_{k=0}^{r−1} (\frac{(∑_{s=1}^{r} α_{σ(k),s})!(−1)^{∑_{s=1}^{r} α_{σ(k),s}+r+1}}{∏_{s=1}^{r} α_{σ(k),s}!} ) ,  (32)

for σ(k) = k + r − m with 0 ≤ k ≤ σ(k) ≤ r − 1 and

α_{r,s} = \begin{cases}α_{σ(k),s} = α_{k+r−m,s}, & if s ≠ r − σ(k) = m − k; \\ α_{σ(k),s} + 1 = α_{k+r−m,s} + 1, & if s = r − σ(k) = m − k \end{cases}

with ∑_{s=1}^{r} sα_{r,s} = m and ∑_{s=1}^{r} sα_{σ(k),s} = ∑_{s=1}^{r} sα_{k+r−m,s} = k. Note also that 0 ≤ k ≤ m−1. In addition, α_{r,s} = 0 for m + 1 ≤ s ≤ r. Let

α = (α_{r,1}, …, α_{r,r}).

Similarly to the proof of Theorem 1, we define

E(α) = {k ∈ {0, 1, …, m − 1} : α_{r,m−k} ≥ 1}.

Since 0! = 1 and

∑_{s=1}^{r} α_{r,s} + r = ∑_{s=1}^{r} α_{σ(k),s} + r + 1,

equation (32) is equivalent to

\frac{(∑_{s=1}^{r} α_{r,s})!}{∏_{s=1}^{r} α_{r,s}!} = ∑_{k∈E(α)} (\frac{(∑_{s=1}^{m}α_{r,s} − 1)!}{( ∏_{{s=1 \atop s≠m−k}}^{m}α_{r,s}!) (α_{r,m−k} − 1)!}) .  (33)

Equation (33) follows from equation (19), and the inductive step is complete.

The following lemma is needed in the proof of Theorem 3.

Lemma 11. Let N, K, ρ ∈ ℤ_{≥0} with 1 ≤ K = 2ρ + 2 ≤ N and A ⊆ ℤ_{>0} be given. Then

F_{A}^{L_{2}}(N; K = 2ρ + 2) = ∑_{a∈A} ∑_{ℓ=0}^{ρ}(−1)^{ℓ}F_{A}^{L_{1}}(N − (2ℓ + 1)a; K − (2ℓ + 1))
+ ∑_{a∈A}(−1)^{ρ+1}I(N = (2ρ + 2)a)  (34)

under the convention that F_{A}^{L_{2}}(n; k) = 0 for any n, k ∈ ℤ with n < k.

Proof. For a ∈ A and m ∈ {1, …, ρ + 1}, let F_{A}^{L_{1}}(N; K; a; m) be the set of all type II palindromic compositions (λ_{1}, …, λ_{K}) of N with length K and parts in the set A that satisfy

λ_{1} = ⋯ = λ_{m} = λ_{K−m+2} = ⋯ = λ_{K} = a  (35)

and are such that (λ_{m+1}, …, λ_{K−m+1}) is a type I palindromic Carlitz composition of N − (2m − 1)a with length K − (2m − 1) = 2ρ − 2m + 3 and parts in A. (If m = 1, equation (35) becomes λ_{1} = a.) Let also F_{A}^{L_{2}}(N; K; a; m) be the set of all compositions (λ_{1}, …, λ_{K}) in F_{A}^{L_{1}}(N; K; a; m) that satisfy

λ_{m+1} = λ_{K−m+1} ≠ a.

Then

F_{A}^{L_{2}}(N; K; a; m) ⋃ F_{A}^{L_{2}}(N; K; a; m + 1) = F_{A}^{L_{1}}(N; K; a; m)  (36)

and

F_{A}^{L_{2}}(N; K; a; m) ⋂ F_{A}^{L_{2}}(N; K; a; m + 1) = ∅.  (37)

Equations (36) and (37) are true even for m = ρ + 1 provided we define

F_{A}^{L_{2}}(N; K; a; ρ + 2) = \begin{cases}∅, & if N ≠ (2ρ + 2)a; \\ \{(a, …, a)\} ∈ A^{2ρ+2}, & if N = (2ρ + 2)a. \end{cases}

If 1 ≤ m ≤ ρ + 1, then we note that #F_{A}^{L_{1}}(N; K; a; m) is equal to the number of type I palindromic Carlitz compositions of N − (2m − 1)a with length K − (2m − 1) = 2ρ − 2m + 3 and parts in A, whereas #F_{A}^{L_{2}}(N; K; a; m) is equal to the number of type II palindromic Carlitz compositions of N − (2m − 2)a with length K − (2m − 2) and parts in A that start with a.

Let α(m) = #F_{A}^{L_{1}}(N; K; a; m) and β(m) = #F_{A}^{L_{2}}(N; K; a; m). Equations (36) and (37) imply

β(m) + β(m + 1) = α(m) for m = 1, …, ρ + 1.

We can then easily prove that

β(1) = ∑_{ℓ=1}^{ρ+1}(−1)^{ℓ+1}α(ℓ) + (−1)^{ρ+1}β(ρ + 2).

Then (with K = 2ρ + 2)

#F_{A}^{L_{2}}(N; K; a; m = 1) = ∑_{ℓ=1}^{ρ+1}(−1)^{ℓ+1} #F_{A}^{L_{1}}(N; K; a; m = ℓ) + (−1)^{ρ+1}I(N = Ka).

Summing over a ∈ A, we can easily prove equation (34) in the lemma.

Proof of Theorem 3. If K = 1, then F_{A}^{L_{2}}(N; K = 1) = I(N ∈ A), while for K odd integer ≥ 3, it is impossible to have any type II palindromic Carlitz composition (λ_{1}, …, λ_{K}) of N with length K because, if this were the case, then we would have λ_{(K+1)/2} = λ_{(K+3)/2}.

Let ρ ∈ ℤ_{≥0}. Then F_{A}^{L_{2}}(N; K = 2ρ + 2) is given by equation (34) in Lemma 11. Hence,

∑_{N,K≥1} F_{A}^{L_{2}}(N; K) x^{N} y^{K} = ∑_{N≥1} F_{A}^{L_{2}}(N; K = 1) x^{N} y + ∑_{N≥1} ∑_{ρ=0}^{∞} F_{A}^{L_{2}}(N; K = 2ρ + 2) x^{N}y^{2ρ+2} (38)

= ∑_{N=1}^{∞} ∑_{ρ=0}^{∞} ∑_{a∈A} ∑_{ℓ=0}^{ρ}(−1)^{ℓ}F_{A}^{L_{1}}(N − (2ℓ + 1)a; K − (2ℓ + 1)) x^{N}y^{2ρ+2}

+ ∑_{N=1}^{∞} ∑_{ρ=0}^{∞} ∑_{a∈A}(−1)^{ρ+1}I(N = (2ρ + 2)a) x^{N}y^{2ρ+2}

+ ∑_{N=1}^{∞} I(N ∈ A) x^{N}y.  (39)

We denote the three terms in the right-hand side of equation (39) by D_{1}, D_{2}, D_{3}. Clearly, D_{3} = ∑_{a∈A} x^{a}y, while

D_{2} = ∑_{a∈A} ∑_{ρ=0}^{∞}(−1)^{ρ+1}x^{(2ρ+2)a}y^{2ρ+2} = − ∑_{a∈A} \frac{x^{2a}y^{2}}{1 + x^{2a}y^{2}} .

Finally,

D_{1} = ∑_{N=1}^{∞} ∑_{ℓ=0}^{∞} ∑_{a∈A}(−1)^{ℓ}x^{(2ℓ+1)a}y^{2ℓ+1} ∑_{ρ=ℓ}^{∞} F_{A}^{L_{1}}(N − (2ℓ + 1)a; 2(ρ − ℓ) + 1) x^{N−(2ℓ+1)a}y^{2(ρ−ℓ)+1}.

Letting n = N − (2ℓ + 1)a and r = ρ − ℓ and using equation (4), we get

D_{1} = ∑_{a∈A} (∑_{ℓ=0}^{∞}(−1)^{ℓ}x^{(2ℓ+1)a}y^{2ℓ+1}) ( ∑_{n,r≥0} F_{A}^{L_{1}}(n; 2r + 1) x^{n}y^{2r+1})

= (∑_{a∈A} \frac{x^{a}y}{1 + x^{2a}y^{2}} ) (\frac{∑a∈A \frac{x^{a}y}{1+x^{2a}y^{2}}}{1 − ∑_{a∈A} \frac{x^{2a}y^{2}}{1+x^{2a}y^{2}}} ) = \frac{(∑a∈A \frac{x^{a}y}{1+x^{2a}y^{2}} )2}{1 − ∑_{a∈A} \frac{x^{2a}y^{2}}{1+x^{2a}y^{2}}} .

This completes the proof of Theorem 3.

If a ∈ A, we let E\overline{C} ; A(N; K; a) denote the number of linear Carlitz compositions of N with length K and parts in A that start and end with a. We also let E_{A}^{L}(N; K; a) denote the number of linear Carlitz compositions of N with length K and parts in A that start with a. By symmetry, it is also the number of linear Carlitz compositions of N with length K and parts in A that end with a. Note that E_{A}^{L}(N; K = 0; a) = 0 for any N ∈ ℤ_{≥0}.

For fixed K ∈ ℤ_{>0}, let

E\overline{C} ; A(K; a; x) = ∑_{N≥1} E\overline{C} ; A(N; K; a) x^{N} and E_{A}^{L}(K; a; x) = ∑_{N≥0} E_{A}^{L}(N; K; a) x^{N}.  (40)

Again, note that E_{A}^{L}(K = 0; a; x) = 0. For K ∈ ℤ_{>0}, let also

E\overline{C} ; A(K; x) = ∑_{a∈A} E\overline{C} ; A(K; a; x) and E_{A}^{L}(K; x) = ∑_{a∈A} E_{A}^{L}(K; a; x).  (41)

For K ∈ ℤ_{>0}, E\overline{C} ; A(K; x) = ∑_{N≥1} E\overline{C} ; A(N; K) x^{N} and E_{A}^{L}(K; x) = ∑_{N≥1} E_{A}^{L}(N; K) x^{N}. We

also have E_{A}^{L}(K = 0; x) = E_{A}^{L}(N = 0, K = 0) x^{0} = 1. The following lemma is needed in the proof of Theorem 4.

Lemma 12. Let K ∈ ℤ_{>0}, A ⊆ ℤ_{>0}, and a ∈ A.

1. For K = 2m with m ∈ ℤ_{>0}, we have

E\overline{C} ; A(K = 2m; a; x) = ∑_{ℓ=1}^{m−1} x^{2ℓa}E_{A}^{L}(2m − 2ℓ; x) − 2 ∑_{ℓ=1}^{m−1} x^{2ℓa}E_{A}^{L}(2m − 2ℓ; a; x). (42)

2. For K = 2m + 1 with m ∈ ℤ_{>0}, we have

E\overline{C} ; A(K = 2m+1; a; x) = ∑_{ℓ=1}^{m} x^{2ℓa}E_{A}^{L}(2m−2ℓ+1; x)−2 ∑_{ℓ=1}^{m} x^{2ℓa}E_{A}^{L}(2m−2ℓ+1; a; x)+x^{(2m+1)a}.

(43)

Proof. 1. We proceed by induction on m. For m = 1, equation (42) is true because E\overline{C} ; A(N; K = 2; a) = 0 for any N ∈ ℤ_{>0} and an empty sum is zero.

Assume equation (42) holds for m = M ∈ ℤ_{>0}. Following the methodology of Heubach and Mansour [12], we create \overline{C}-type Carlitz compositions by adding a ∈ A to the left and to the right of any Carlitz composition of N − 2a (provided N − 2a ≥ 1) with length K = 2M and parts in A, except for those Carlitz compositions of N − 2a (with length K = 2M and parts in A) that

(i) start with a, but do not end with a;

(ii) end with a, but do not start with a;

(iii) start and end with a.

The numbers in cases (i) and (ii) are the same, and each equals

E_{A}^{L}(N − 2a; K = 2M; a) − E\overline{C} ; A(N − 2a; K = 2M; a),

while the number in case (iii) is E\overline{C} ; A(N − 2a; K = 2M; a). It follows that

E\overline{C} ; A(N; K = 2M + 2; a) = E_{A}^{L}(N − 2a; K = 2M) − 2E_{A}^{L}(N − 2a; K = 2M; a)

+E\overline{C} ; A(N − 2a; K = 2M; a).

Multiplying both sides of the above equation by x^{N} and summing over N, we get

E\overline{C} ; A(K = 2M + 2; a; x) = x^{2a}E_{A}^{L}(2M; x) − 2x^{2a}E_{A}^{L}(2M; a; x) + x^{2a}E\overline{C} ; A(2M; a; x).

Using the induction hypothesis for m = M, we get

E\overline{C} ; A(K = 2M + 2; a; x) = x^{2a}E_{A}^{L}(2M; x) − 2x^{2a}E_{A}^{L}(2M; a; x)

+ ∑_{ℓ=1}^{M−1} x^{2(ℓ+1)a}E_{A}^{L}(2M − 2ℓ; x) − 2 ∑_{ℓ=1}^{M−1} x^{2(ℓ+1)a}E_{A}^{L}(2M − 2ℓ; a; x)

= x^{2a}E_{A}^{L}(2M; x) − 2x^{2a}E_{A}^{L}(2M; a; x)

+ ∑_{s=2}^{M} x^{2sa}E_{A}^{L}(2M + 2 − 2s; x) − 2 ∑_{s=2}^{M} x^{2sa}E_{A}^{L}(2M + 2 − 2s; a; x).

Hence,

E\overline{C} ; A(K = 2M + 2; a; x) = ∑_{s=1}^{M} x^{2sa}E_{A}^{L}(2M + 2 − 2s; x) − 2 ∑_{s=1}^{M} x^{2sa}E_{A}^{L}(2M + 2 − 2s; a; x),

and the induction step is complete.

2. We again proceed by induction on m. For m = 1, equation (43) is true because, for N ∈ ℤ_{>0},

E\overline{C} ; A(N; K = 3; a) = ∑_{N≥1} I(N − 2a ∈ A) x^{N} − x^{3a}
= x^{2a} ∑_{N≥1} I(N − 2a ∈ A) x^{N−2a} − x^{3a}

= x^{2a} (∑_{b∈A} x^{b}) − x^{3a}

= ∑_{ℓ=1}^{1} x^{2ℓa}E_{A}^{L}(2 − 2ℓ + 1; x) − 2 ∑_{ℓ=1}^{1} x^{2ℓa}E_{A}^{L}(2 − 2ℓ + 1; a; x) + x^{(2+1)a}.

The rest of the proof is similar to the proof of Part 1 of the lemma. We assume equation (43) holds for m = M ∈ ℤ_{>0}, and following the methodology of Heubach and Mansour [12], we prove it for m = M + 1. The details are omitted.

Before proving Theorem 4, we need the lemma below. For a ∈ A, let

E_{A}^{L}(a; x, y) = ∑_{N,K≥0} E_{A}^{L}(N; K; a) x^{N} y^{K} = ∑_{K≥0} E_{A}^{L}(K; a; x) y^{K}  (44)

and

E_{A}^{L}(x, y) = ∑_{N,K≥0} E_{A}^{L}(N; K) x^{N}y^{K} = 1 + ∑_{a∈A} E_{A}^{L}(a; x, y).  (45)

Lemma 13. Let A ⊆ ℤ_{>0} and a ∈ A. Then

E_{A}^{L}(a; x, y) = \frac{x^{a}y}{1 + x^{a}y} E_{A}^{L}(x, y).  (46)

Proof. Using the methodology and results of Heubach and Mansour [12] (see also the proof of Lemma 12 above), we have, for each K ∈ ℤ_{>0},

E_{A}^{L}(K; a; x) = x^{a}E_{A}^{L}(K − 1; x) − x^{a}E_{A}^{L}(K − 1; a; x),

with E_{A}^{L}(K = 0; a; x) = 0 and E_{A}^{L}(K = 1; a; x) = x^{a}. Using the above equality and equations (40) and (41), we can then prove by induction on K that

E_{A}^{L}(K; a; x) = ∑_{ℓ=1}^{K}(−1)^{ℓ−1}x^{ℓa}E_{A}^{L}(K − ℓ; x).  (47)

Using equations (44)–(47) and the fact E_{A}^{L}(K = 0; a; x) = 0, we then have

E_{A}^{L}(a; x, y) = ∑_{K=1}^{∞} ∑_{ℓ=1}^{K}(−1)^{ℓ−1}x^{ℓa}E_{A}^{L}(K − ℓ; x) y^{K}

= ∑_{ℓ=1}^{∞}(−1)^{ℓ−1}x^{ℓa}y^{ℓ} ∑_{K=ℓ}^{∞} E_{A}^{L}(K − ℓ; x) y^{K−ℓ}

= ∑_{ℓ=1}^{∞}(−1)^{ℓ−1}x^{ℓa}y^{ℓ} ∑_{s=0}^{∞} E_{A}^{L}(s; x) y^{s} = \frac{x^{a}y}{1 + x^{a}y} E_{A}^{L}(x, y).

This completes the proof of the lemma.

Proof of Theorem 4. Let a ∈ A and

E\overline{C} ; A(a; x, y) := ∑_{K≥1} E\overline{C} ; A(K; a; x) y^{K},

where E\overline{C} ; A(K; a; x) is defined by one of the equations (40). Note that E\overline{C} ; A(K = 1; a; x) = 0. Then

E\overline{C} ; A(a; x, y) = ∑_{m=1}^{∞} E\overline{C} ; A(K = 2m; a; x) y^{2m} + ∑_{m=1}^{∞} E\overline{C} ; A(K = 2m + 1; a; x) y^{2m+1}. (48)

Substituting equations (42) and (43) (from Lemma 12) in equation (48) and changing the order of summation in the four double sums we get, we obtain

E\overline{C} ; A(a; x, y) = ∑_{ℓ=1}^{∞} x^{2ℓa} ∑_{m=ℓ+1}^{∞} E_{A}^{L}(2m − 2ℓ; x) y^{2m} + ∑_{ℓ=1}^{∞} x^{2ℓa} ∑_{m=ℓ}^{∞} E_{A}^{L}(2m − 2ℓ + 1; x) y^{2m+1}

−2 ∑_{ℓ=1}^{∞} x^{2ℓa} ∑_{m=ℓ+1}^{∞} E_{A}^{L}(2m − 2ℓ; a; x) y^{2m}

−2 ∑_{ℓ=1}^{∞} x^{2ℓa} ∑_{m=ℓ}^{∞} E_{A}^{L}(2m − 2ℓ + 1; a; x) y^{2m+1} + \frac{x^{3a}y^{3}}{1 − x^{2a}y^{2}} .

Combining the first two double sums and doing the same for the next two double sums on the right-hand side of the above equation, we get

E\overline{C} ; A(a; x, y) = ∑_{ℓ=1}^{∞} x^{2ℓa}y^{2ℓ} ∑_{M=2ℓ+1}^{∞} E_{A}^{L}(M − 2ℓ; x) y^{M−2ℓ}

−2 ∑_{ℓ=1}^{∞} x^{2ℓa}y^{2ℓ} ∑_{M=2ℓ+1}^{∞} E_{A}^{L}(M − 2ℓ; a; x) y^{M−2ℓ} + \frac{x^{3a}y^{3}}{1 − x^{2a}y^{2}} .

After some algebraic manipulations, we get

E\overline{C} ; A(a; x, y) = \frac{x^{2a}y^{2}}{1 − x^{2a}y^{2}} (E_{A}^{L}(x, y) − 1 − 2E_{A}^{L}(a; x, y)) + \frac{x^{3a}y^{3}}{1 − x^{2a}y^{2}} .

Using equation (46) from Lemma 13, we get

E\overline{C} ; A(a; x, y) = \frac{x^{2a}y^{2}}{(1 + x^{a}y)^{2}} E_{A}^{L}(x, y) − \frac{x^{2a}y^{2}}{1 + x^{a}y} .

Summing over a ∈ A and using equation (2), we get

E\overline{C} ; A(x, y) = \frac{∑a∈A \frac{x^{2a}y^{2}}{(1+x^{a}y)^{2}}}{1 − ∑_{a∈A} \frac{x^{a}y}{1+x^{a}y}} − ∑_{a∈A} \frac{x^{2a}y^{2}}{1 + x^{a}y} .

The bivariate generating function of the number of C-type cyclic Carlitz compositions of N with length K and parts in A satisfies

E_{A}^{C}(x, y) = E_{A}^{L}(x, y) − 1 − E\overline{C} ; A(x, y),

Therefore, after some algebra, we can easily prove equation (11).

Proof of Corollary 5. It follows from Theorem 4 by letting y = 1 in equation (11).

Proof of Theorem 6. The proof of this theorem is similar to the proofs of the main results in Hadjicostas [10], and hence we give only a sketch of the proof and emphasize the important steps.

Consider an arbitrary (modified) CR-type Carlitz composition [(λ_{1}, …, λ_{K})]_{CR} of N with length K and parts in A. We place the λ_{i}’s on a circle (i.e., λ_{1} follows λ_{N}), and we define the period h of this circular composition to be the length of the shortest subsequence of λ_{i}’s with consecutive indices that is able to reproduce [(λ_{1}, …, λ_{K})]_{CR} by repeating itself K/h times. It follows that K/h divides N.

Denote by Ẽ_{A}^{CR}(N; K; h) the number of all (modified) CR-type cyclic Carlitz compositions of N with length K, period h, and parts in A. For 1 ≤ K ≤ N,

Ẽ_{A}^{CR} (N; K; \frac{K}{d} ) = Ẽ_{A}^{CR} (\frac{N}{d}; \frac{K}{d}; \frac{K}{d} ) for all positive divisors d of gcd(N, K) (49)

and

Ẽ_{A}^{C}(N; K) = ∑_{h|K & \frac{K}{h} |N} h Ẽ_{A}^{CR}(N; K; h).  (50)

Letting s = \frac{K}{h} , it follows from equations (49) and (50) that

Ẽ_{A}^{C}(N; K) = ∑_{s| gcd(N,K)} \frac{K}{s} Ẽ_{A}^{CR} (N; K; \frac{K}{s} ) = ∑_{s| gcd(N,K)} \frac{K}{s} Ẽ_{A}^{CR} (\frac{N}{s}; \frac{K}{s}; \frac{K}{s} ) .  (51)

Similarly,

Ẽ_{A}^{CR}(N; K) = ∑_{h|K & \frac{K}{h} |N} Ẽ_{A}^{CR}(N; K; h)

= ∑_{s| gcd(N,K)} Ẽ_{A}^{CR} (N; K; \frac{K}{s} ) = ∑_{s| gcd(N,K)} Ẽ_{A}^{CR} (\frac{N}{s}; \frac{K}{s}; \frac{K}{s} ) . (52)

Using equations (51) and (52), the associativity of Dirichlet convolutions, and Möbius’s inversion principle, we can derive equation (14) using similar techniques as in the proof of Theorem 1 in Hadjicostas [10].

To prove equation (15), we sum both sides of (14) from K = 1 to K = N:

Ẽ_{A}^{CR}(N) = ∑_{K=1}^{N} Ẽ_{A}^{CR}(N; K) = ∑_{K=1}^{N} ∑_{d| gcd(N,K)} \frac{1}{K} ϕ(d) Ẽ_{A}^{C} (\frac{N}{d}; \frac{K}{d} ) .

Letting s = N/d and ℓ = K/d, and switching the order of summation in the last double sum above, we get

Ẽ_{A}^{CR}(N) = ∑_{s|N} ∑_{ℓ=1}^{s} \frac{ϕ(N/s)}{ℓN/s} Ẽ_{A}^{C}(s; ℓ) = \frac{1}{N} ∑_{s|N} ϕ (\frac{N}{s} ) s ∑_{ℓ=1}^{s} \frac{Ẽ_{A}^{C}(s; ℓ)}{ℓ}.  (53)

Using equations (16) and (53), we can easily prove equation (15).

To derive the generating function for Ẽ_{A}^{CR}(N; K), note that equation (11) implies

∑_{N,K≥1} Ẽ_{A}^{C}(N; K) x^{N}y^{K} = ∑_{N,K≥1} E_{A}^{C}(N; K) x^{N}y^{K} − ∑_{N≥1} I(N ∈ A) x^{N}y

= \frac{∑a∈A \frac{x^{a}y}{(1+x^{a}y)^{2}}}{1 − ∑_{a∈A} \frac{x^{a}y}{1+x^{a}y}} − ∑_{a∈A} \frac{x^{a}y}{1 + x^{a}y} .

It follows that

∑_{N,K≥1} \frac{Ẽ_{A}^{C}(N; K) x^{N}y^{K}}{K} = ∫_{0}^{y} ∑_{N,K≥1} Ẽ_{A}^{C}(N; K) x^{N}w^{K−1} dw

= ∫_{0}^{y} (\frac{∑a∈A \frac{x^{a}}{(1+x^{a}w)^{2}}}{1 − ∑_{a∈A} \frac{x^{a}w}{1+x^{a}w}} − ∑_{a∈A} \frac{x^{a}}{1 + x^{a}w}) dw.

Therefore,

∑_{N,K≥1} \frac{Ẽ_{A}^{C}(N; K) x^{N}y^{K}}{K} = G_{A}(x, y),  (54)

where G_{A}(x, y) is given by equation (17). Equation (14) then implies

G.F. = ∑_{N=1}^{∞} ∑_{K=1}^{∞} Ẽ_{A}^{CR}(N; K) x^{N}y^{K} = ∑_{N=1}^{∞} ∑_{K=1}^{∞} \frac{1}{K} ∑_{s| gcd(N,K)} ϕ(s) Ẽ_{A}^{C} (\frac{N}{s}; \frac{K}{s} ) x^{N}y^{K}.

Letting n = N/s and k = K/s and changing the order of the triple summation, we get

G.F. = ∑_{s=1}^{∞} ∑_{n=1}^{∞} ∑_{k=1}^{∞} \frac{ϕ(s)}{ks}Ẽ_{A}^{C}(n; k) x^{ns}y^{ks}

= ∑_{s=1}^{∞} \frac{ϕ(s)}{s} ∑_{n,k≥1} \frac{Ẽ_{A}^{C}(n; k)}{k}(x^{s})^{n}(y^{s})^{k} = ∑_{s=1}^{∞} \frac{ϕ(s)}{s}G_{A}(x^{s}, y^{s}).

This completes the proof of the theorem.

Proof of Theorem 7. If K = 1, we clearly have F_{A}^{CR}(N; K = 1) = I(N ∈ A). Assume 2 ≤ K ≤ N. Then every symmetrical CR-type cyclic Carlitz composition of N with length K and parts in A has at least two distinct parts and its equivalence class contains exactly two linear palindromic (Carlitz) compositions of either type. (The latter fact follows from Theorem 1.1 in Hadjicostas and Zhang [11].) But every type I linear palindromic composition (λ_{1}, …, λ_{K}) with K ≥ 2 satisfies λ_{1} = λ_{K}, so it cannot be Carlitz. This immediately implies that F_{A}^{CR}(N; K) = F_{A}^{L_{2}}(N; K)/2. Equation (18) follows immediately from Theorem 3.

Proof of Corollary 8. We have

F_{A}^{CR}(N) = F_{A}^{CR}(N; K = 1) + ∑_{K=2}^{∞} F_{A}^{CR}(N; K)

= I(N ∈ A) + \frac{1}{2} ∑_{K=2}^{∞} F_{A}^{L_{2}}(N; K)

= I(N ∈ A) + \frac{1}{2} (F_{A}^{L_{2}}(N) − F_{A}^{L_{2}}(N; K = 1)) = \frac{F_{A}^{L_{2}}(N) + I(N ∈ A)}{2}.

The G.F. for F_{A}^{CR}(N) follows by setting y = 1 in equation (18).

Proof of Theorem 9. Similar to an argument in Hadjicostas and Zhang [11] (see equation (7) in this paper), we have

E_{A}^{D}(N; K) = \frac{E_{A}^{CR}(N; K) − F_{A}^{CR}(N; K)}{2} + F_{A}^{CR}(N; K) = \frac{E_{A}^{CR}(N; K) + F_{A}^{CR}(N; K)}{2}.

The proof of the rest of theorem follows easily from Theorem 7.

Proof of Corollary 10. It follows from Corollary 8 and Theorem 9.

4 Future research

In a series of four papers, Bender and Canfield [2, 3, 4] and Bender, Canfield, and Gao [5] discuss “locally restricted compositions,” which generalize the idea of Carlitz composition. In these four papers, the authors discuss at least two different definitions of “locally restricted compositions.” They also prove asymptotic probabilistic results about random locally restricted compositions.

Cyclic and dihedral compositions do not form part of these “locally restrictive compositions,” and hence further research is needed to create a general theory of locally restricted cyclic and dihedral compositions. The techniques in this paper and in Taylor [23], along with the techniques in the four aforementioned papers, may serve as starting points for creating such a general theory.

5 Acknowledgments

The author wishes to thank statistician Lingyun Zhang for some help in writing this paper. In addition, the author wishes to thank the referee for useful comments that improved the presentation of the paper. In particular, the material in Section 4 is based on his or her suggestions.

References

[1] M. Beck and N. Robbins, Variations on a generating-function theme: enumerating compositions with parts avoiding an arithmetic sequence, Amer. Math. Monthly 122 (2015), 256–263.

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

[3] E. A. Bender and E. R. Canfield, Locally restricted compositions II. General restrictions and infinite matrices, Electron. J. Combin. 16 (2009), Article #R108.

[4] E. A. Bender and E. R. Canfield, Locally restricted compositions III. Adjacent-part periodic inequalities, Electron. J. Combin. 17 (2010), Article #R145.

[5] E. A. Bender, E. R. Canfield, and Z. Gao, Locally restricted compositions IV. Nearly free large parts and gap-freeness, Electron. J. Combin. 19 (4) (2012), Article #P14.

[6] L. Carlitz, Restricted compositions, Fibonacci Quart. 14 (1976), 254–264.

[7] S. Corteel and P. Hitczenko, Generalizations of Carlitz compositions, J. Integer Sequences 10 (2007), Article 07.8.8.

[8] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[9] P. Flajolet and M. Soria, The cycle construction, SIAM J. Discrete Math. 4 (1991), 58–60.

[10] P. Hadjicostas, Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence, J. Integer Sequences 19 (2016), Article 16.8.2.

[11] P. Hadjicostas and L. Zhang, Sommerville’s symmetrical cyclic compositions of a positive integer with parts avoiding multiples of an integer, Fibonacci Quart. 55 (2017), 54–73.

[12] S. Heubach and T. Mansour, Compositions of n with parts in a set, Congr. Numer. 168 (2004), 127–143.

[13] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

[14] V. E. Hoggatt, Jr., and D. A. Lind, Fibonacci and binomial properties of weighted compositions, J. Combin. Theory 4 (1968), 121–124.

[15] A. Knopfmacher and H. Prodinger, On Carlitz compositions, European J. Combin. 19 (1998), 579–589.

[16] A. Knopfmacher and N. Robbins, Some properties of cyclic compositions, Fibonacci Quart. 48 (2010), 249–255.

[17] A. Knopfmacher and N. Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207–220.

[18] P. A. MacMahon, Memoir on the theory of the compositions of numbers, Philos. Trans. Roy. Soc. London A 184 (1893), 835–901.

[19] P. A. MacMahon, Second memoir on the compositions of numbers, Philos. Trans. Roy. Soc. London A 207 (1908), 65–134.

[20] L. Moser and E. L. Whitney, Weighted compositions, Canad. Math. Bull. 4 (1961), 39–43.

[21] R. Razen, J. Seberry, and K. Wehrhahn, Ordered partitions and codes generated by circulant matrices, J. Combin. Theory Ser. A 27 (1979), 333–341.

[22] D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263–313.

[23] J. Taylor, Counting words with Laguerre series, Electron. J. Combin. 21 (2) (2014), #P2.1.

[24] N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl. 27 (1999), 37–40.

[25] L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern “11...1”, Math. Scientist 40 (2015), 89–96.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A10. Keywords: Carlitz composition, cyclic composition, dihedral composition, Euler’s totient function, palindromic composition, symmetrical cyclic composition.

(Concerned with sequences \underline{A000070}, \underline{A106369}, \underline{A212322}, and \underline{A239327}.)

Received February 1 2017; revised versions received February 12 2017; July 12 2017; August 24 2017. Published in Journal of Integer Sequences, September 2 2017.

Return to Journal of Integer Sequences home page.