Some New Restricted n-Color Composition Functions

Jarib R. Acosta, Yadira Caicedo, and Juan P. Poveda

Departamento de Matemáticas y Estadística

Universidad del Tolima Tolima Colombia

jracostac@ut.edu.co
nycaicedob@ut.edu.co
jppovedac@ut.edu.co

José L. Ramírez Departamento de Matemáticas

Universidad Nacional de Colombia Bogotá Colombia

jlramirezr@unal.edu.co

Mark Shattuck^{1}

Institute for Computational Science

and

Faculty of Mathematics and Statistics

Ton Duc Thang University

Ho Chi Minh City

Vietnam

mark.shattuck@tdtu.edu.vn

1Corresponding author.

Abstract

An n-color composition is one in which a part of size m can come in m colors (denoted by subscripts). Let C(ν) denote the set of n-color compositions of the positive integer ν. In this paper, we consider further modular restrictions on the subscripts of the parts within members of C(ν). We first count members of C(ν) in which all parts have subscripts of the form ℓa + b, where b and ℓ are fixed and a ≥ 0 is arbitrary. Generating function and explicit formulas are found for general b and ℓ which extend earlier results when ℓ = 2 and b ≤ 3. We study the case ℓ = b − 1 in further detail and find that the corresponding subset of C(ν) is in bijection with various classes of compositions. Finally, we consider two related problems: one where the subscript restriction applies only to parts within a given modular class and another where the subscript of a part belongs to the same modular class mod ℓ as the part where ℓ is fixed.

1 Introduction

A composition of a positive integer ν is a sequence of positive integers σ = {σ_{1}, σ_{2}, …, σ_{r}} such that σ_{1} + σ_{2} + ⋯ + σ_{r} = ν. The summands σ_{i} are called the parts of σ and ν is the weight of σ. For example, the compositions of 4 are

{4}, {3, 1}, {1, 3}, {2, 2}, {2, 1, 1}, {1, 2, 1}, {1, 1, 2}, {1, 1, 1, 1}.

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

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

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

It is well-known that the total number of n-color compositions of ν is given by the Fibonacci number F_{2ν}. Moreover, the number of n-color compositions of ν with exactly m parts is the binomial coefficient \binom{ν+m−1}{2m−1}. For further results about n-color compositions, see, e.g., [1, 2, 4, 6, 7, 9, 10, 11, 13, 14, 15]. In this paper, we study some new restrictions on n-color compositions that generalize previous results given by Sachdeva and Agarwal [13].

The organization of this paper is as follows. In the next section, we count the members of C(ν) in which the subscripts on all parts are of the form ℓa + b for some a ≥ 0, where b, ℓ ≥ 1 are fixed, providing generating function and explicit formulas. This extends recent work [13] in the case ℓ = 2. We consider further the case ℓ = b − 1, which yields several previously studied sequences from [16], and find bijections between various restricted classes of binary words and compositions and the corresponding subset of C(ν). In the third section, we count members of C(ν) in which only parts of the form ℓa + b for some a ≥ 0 satisfy a similar modular requirement with respect to their subscripts. An explicit formula for the generating function is found which extends prior results [13]. Finally, a comparable formula can be given which counts members of C(ν) in which parts of the form ℓa + b where a ≥ 0 and 1 ≤ b ≤ ℓ must have subscripts of the same form.

2 Generalized restricted n-color compositions

Given positive integers ℓ and b, let C_{ℓa+b}(ν) denote the number of n-color compositions of ν into parts with subscripts of the form ℓa + b for some integer a ≥ 0. We also denote by C_{ℓa+b}(m, ν) the number of n-color compositions of ν into m parts with subscripts of the form ℓa + b.

For example, C_{3a+1}(4) = 9, the compositions being

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

Theorem 1. Let GC_{ℓa+b}(m, x) and GC_{ℓa+b}(x) denote the generating functions for the sequences C_{ℓa+b}(m, ν) and C_{ℓa+b}(ν), respectively. Then we have

GC_{ℓa+b}(m, x) = (\frac{x^{b}}{(1 − x)(1 − x^{ℓ})})^{m} ,
GC_{ℓa+b}(x) = \frac{x^{b}}{1 − x − x^{ℓ} + x^{ℓ+1} − x^{b}} .

Proof. Let σ = σ_{1} ⋯ σ_{m} be a non-empty n-color composition having m parts where each subscript is of the form ℓa + b for some a ≥ 0. If σ_{j} = i with i ≥ b, then σ_{j} contributes to the generating function the term w_{i}x^{i}, where

w_{i} = ⌊\frac{i − b + ℓ}{ℓ}⌋ ,

while if i < b, then it fails to contribute.

Note that the generating function of the sequence

\{w_{i}\}_{i≥0} = \{\underbrace{0, …, 0}_{b}, \underbrace{1, …, 1}_{ℓ}, \underbrace{2, …, 2}_{ℓ}, … \}

is given by

\frac{x^{b}}{(1 − x)(1 − x^{ℓ})}.

Therefore,

GC_{ℓa+b}(m, x) = (∑_{i≥0} w_{i}x^{i})^{m} = (\frac{x^{b}}{(1 − x)(1 − x^{ℓ})})^{m} .

Finally, summing the last expression over m ≥ 1, we get

GC_{ℓa+b}(x) = \frac{\frac{x^{b}}{(1−x)(1−x^{ℓ})}}{1 − \frac{x^{b}}{(1−x)(1−x^{ℓ})}} = \frac{x^{b}}{1 − x − x^{ℓ} + x^{ℓ+1} − x^{b}} .

We have the following combinatorial formula for the sequence C_{ℓa+b}(m, ν).

Theorem 2. The sequence C_{ℓa+b}(m, ν) is given by the expression

C_{ℓa+b}(m, ν) = \begin{aligned}⌊ & \frac{ν−bm}{ℓ} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{m + i − 1}{m − 1}\binom{ν − ℓi + m(1 − b) − 1}{m − 1}.

Moreover, C_{ℓa+b}(ν) = C_{ℓa+b}(ν − 1) + C_{ℓa+b}(ν − ℓ) − C_{ℓa+b}(ν − ℓ − 1) + C_{ℓa+b}(ν − b) when ν > max{ℓ + 1, b}.

Proof. By Theorem 1, we have

GC_{ℓa+b}(m, x) = (\frac{x^{b}}{(1 − x)(1 − x^{ℓ})})^{m}

= ∑_{i=0}^{∞} ∑_{j=0}^{∞} \binom{m + i − 1}{i}\binom{m + j − 1}{j}x^{j+iℓ+bm}.

Taking t = j + ℓi + bm gives

GC_{ℓa+b}(m, x) = ∑_{i=0}^{∞} ∑_{t=iℓ+bm}^{∞} \binom{m + i − 1}{m − 1}\binom{t − ℓi + m(1 − b) − 1}{m − 1}x^{t}.

By comparing the ν-th coefficient of both sides of the last equation, we obtain the desired result. The recurrence relation follows from the generating function formula for GC_{ℓa+b}(x) given in Theorem 1.

Remark 3. Setting ℓ = b = 1 in Theorem 2, and using the binomial identity [5, Formula 5.26], recovers the fact that there are \binom{ν+m−1}{2m−1} n-color compositions of ν with exactly m parts and thus F_{2ν} altogether with no restriction as to the number of parts.

By setting ℓ = 2 and b = 1, we have the following corollary (see Theorem 2.1 of [13]).

Corollary 4. The generating functions for the number of n-color compositions of ν into m parts with odd subscripts and for the total number of n-color compositions of ν with odd subscripts are

GC_{2a+1}(m, x) = (\frac{x}{(1 − x)(1 − x^{2})})^{m} = (\frac{x}{(1 + x)(1 − x)^{2}} )^{m} ,
GC_{2a+1}(x) = \frac{x}{1 − 2x − x^{2} + x^{3}} .

Moreover,

C_{2a+1}(m, ν) = \begin{aligned}⌊ & \frac{ν−m}{2} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{m + i − 1}{m − 1}\binom{ν − 2i − 1}{m − 1}

and C_{2a+1}(ν) = 2C_{2a+1}(ν − 1) + C_{2a+1}(ν − 2) − C_{2a+1}(ν − 3) for ν > 3, with the initial values C_{2a+1}(1) = 1, C_{2a+1}(2) = 2, C_{2a+1}(3) = 5.

Letting ℓ = 2 and b = 2 yields the following corollary (see Theorem 2.3 of [13]).

Corollary 5. The generating functions for the number of n-color compositions of ν into m parts with even subscripts and for the total number of n-color compositions of ν with even subscripts are

GC_{2a+2}(m, x) = (\frac{x^{2}}{(1 − x)(1 − x^{2})})^{m} = (\frac{x^{2}}{(1 + x)(1 − x)^{2}} )^{m} ,
GC_{2a+2}(x) = \frac{x^{2}}{1 − x − 2x^{2} + x^{3}} .

Moreover,

C_{2a+2}(m, ν) = \begin{aligned}⌊ & \frac{ν−2m}{2} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{m + i − 1}{m − 1}\binom{ν − 2i − m − 1}{m − 1}

and C_{2a+2}(ν) = C_{2a+2}(ν − 1) + 2C_{2a+2}(ν − 2) − C_{2a+2}(ν − 3) for ν > 3, with the initial values C_{2a+2}(1) = 0, C_{2a+2}(2) = 1, C_{2a+2}(3) = 1.

Letting ℓ = 2 and b = 3 yields the further corollary (see Theorem 2.2 of [13]).

Corollary 6. The generating functions for the number of n-color compositions of ν into m parts with odd subscripts > 1 and for the total number of n-color compositions of ν with odd subscripts > 1 are

GC_{2a+3}(m, x) = (\frac{x^{3}}{(1 + x)(1 − x)^{2}} )^{m} ,
GC_{2a+3}(x) = \frac{x^{3}}{1 − x − x^{2}} .

Moreover,

C_{2a+3}(m, ν) = \begin{aligned}⌊ & \frac{ν−3m}{2} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{m + i − 1}{m − 1}\binom{ν − 2i − 2m − 1}{m − 1}

and C_{2a+3}(ν) = C_{2a+3}(ν − 1) + C_{2a+3}(ν − 2) for ν > 3, with the initial values C_{2a+3}(1) = 0, C_{2a+3}(2) = 0, C_{2a+3}(3) = 1.

ℓ b  Sequence C_{ℓa+b}(ν)  A-Sequence
3 1 1, 2, 4, 9, 19, 40, 85, 180, 381, 807, 1709, 3619, 7664, 16230, 34370 \underline{A052908}
3 2 1, 1, 2, 4, 6, 11, 19, 32, 56, 96, 165, 285, 490, 844, 1454, 2503, 4311 \underline{A116732}
3 3 1, 1, 1, 3, 4, 5, 10, 15, 21, 36, 56, 83, 134, 210, 320, 505, 791, 1221 \underline{A176848}

Table 1: Some particular cases for ℓ = 3.

When ℓ = 3, we obtain some known sequences from the OEIS [16]. In Table 1, we give the first several non-zero values.

Note that the sequence \underline{A052908} does not have a combinatorial interpretation listed. For the sequence \underline{A116732}, our combinatorial interpretation differs from the one given. Let A be the set of compositions with parts in {1, 2, 3} such that the order of adjacent 1’s and 3’s is unimportant. Let a(n) be the number of elements in A of weight n. For example, a(6) = 19, where the compositions are

{3, 3}, {3, 2, 1}, {3, 1, 2}, {2, 3, 1}, {1, 2, 3}, {3, 1, 1, 1}, {2, 2, 2}, {2, 2, 1, 1}, {2, 1, 2, 1}, {2, 1, 1, 2}, {1, 2, 2, 1}, {1, 2, 1, 2}, {1, 1, 2, 2}, {2, 1, 1, 1, 1}, {1, 2, 1, 1, 1}, {1, 1, 2, 1, 1}, {1, 1, 1, 2, 1}, {1, 1, 1, 1, 2}, {1, 1, 1, 1, 1, 1}.

Theorem 7. For n ≥ 0, a(n) = C_{3a+2}(n + 2).

Proof. Let w be a composition in A. Then w is either an integer partition (non-ordered composition) with parts in {1, 3} or can be factorized as p 2 w′, where p is a partition with parts in {1, 3} and w′ ∈ A. Thus, the generating function A(x) of the sequence a(n) satisfies the relation

A(x) = P_{1,3}(x) + P_{1,3}(x)x^{2}A(x),

where P_{1,3}(x) counts integer partitions with parts in {1, 3}. Since

P_{1,3}(x) = \frac{1}{(1 − x)(1 − x^{3})},

we have

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

Finally, by Theorem 1,

GC_{3a+2}(x) = x^{2}A(x),

which yields the desired result upon comparing n-th coefficients.

Let b(n) be the number of compositions of n where each part of size j for j ≥ 1 comes in ⌊j/3⌋ kinds (sequence \underline{A176848}). For example, b(7) = 4, the enumerated compositions being {7_{x}}, {7_{y}}, {3_{x}, 4_{x}}, {4_{x}, 3_{x}}. It is clear from the definitions that b(n) = C_{3a+3}(n) for n ≥ 1.

We now give a bijective proof of the prior theorem.

Combinatorial proof of Theorem 7.

Let A_{n} and C_{n} denote the set of compositions enumerated by a(n) and C_{3a+2}(n), respectively. We will define a bijection between A_{n} and C_{n+2} for n ≥ 0. Let us assume that 3 always precedes 1 whenever there is an adjacency of the two letters within a member of A_{n}. Let λ ∈ A_{n}. First assume λ contains no 2’s. Then we may write λ = 3^{i}1^{j}, where i, j ≥ 0 with 3i + j = n. In this case, we map λ to the colored composition λ′ = (3i + j + 2)_{3i+2} of n + 2 containing a single part. So assume λ contains at least one 2, in which case we may write

λ = 3^{i_{0}}1^{j_{0}}2^{a_{1}}3^{i_{1}}1^{j_{1}}2^{a_{2}}3^{i_{2}}1^{j_{2}} ⋯ 2^{a_{r}}3^{i_{r}}1^{j_{r}},

where all exponents are non-negative, r ≥ 1, a_{1}, …, a_{r} ≥ 1, and i_{k} +j_{k} ≥ 1 for 1 ≤ k ≤ r−1. In this case, we let

λ′ = (3i_{0} + j_{0} + 2)_{3i_{0}+2}, (2_{2})^{a_{1}−1}, (3i_{1} + j_{1} + 2)_{3i_{1}+2}, …, (2_{2})^{a_{r}−1}, (3i_{r} + j_{r} + 2)_{3i_{r}+2},

where (2_{2})^{t} denotes a run of the part 2_{2} of length t.

Note that λ′ contains r + 1 parts and indeed belongs to C_{n+2}. Also, while it is possible for the first or the last part of λ′ to be 2_{2}, all parts of the form (3i_{k} + j_{k} + 2)_{3i_{k}+2} where 1 ≤ k ≤ r − 1 are greater than 2. Furthermore, since j_{k} ≥ 0 for 0 ≤ k ≤ r, arbitrary differences can occur between the part sizes and subscripts. Thus, the mapping λ ↦ λ′ may be reversed and hence is a bijection between A_{n} and C_{n+2}, as desired, upon decomposing members of C_{n+2} in the same way λ′ was above.

2.1 The case ℓ = b − 1

In this subsection, we provide additional combinatorial interpretations for the sequence C_{ℓa+ℓ+1}(n), where ℓ ≥ 1. In Table 2, we give the first several non-zero values of these sequences for 2 ≤ ℓ ≤ 6.

ℓ b  Sequence C_{ℓa+b}(ν)  A-Sequence
2 3 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597  \underline{A000045}
3 4 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595 \underline{A000930}
4 5 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 19, 26, 36, 50, 69, 95, 131, 181, 250 \underline{A003269}
5 6 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 26, 34, 45, 60, 80, 106, 140 \underline{A003520}
6 7 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 12, 16, 21, 27, 34, 43, 55, 71, 92 \underline{A005708}

Table 2: Some particular cases of ℓ = b − 1.

Let F_{ℓ}(n) := C_{ℓa+ℓ+1}(n). By Theorem 1, we have

F_{ℓ}(x) := ∑_{n=0}^{∞} F_{ℓ}(n)x^{n} = \frac{x^{ℓ+1}}{1 − x − x^{ℓ}} .

Moreover, F_{ℓ}(n) = F_{ℓ}(n − 1) + F_{ℓ}(n − ℓ) for n > ℓ + 1, with the initial values F_{ℓ}(ℓ + 1) = 1 and F_{ℓ}(n) = 0 for n ∈ [ℓ] = {1, 2, …, ℓ}. For ℓ = 2, it is clear that the sequence F_{2}(n) coincides with the Fibonacci numbers, i.e., F_{2}(n) = F_{n−2} for n ≥ 2. Moreover, F_{3}(n) is seen to correspond to the Narayana sequence (cf. [12]).

Let E_{ℓ} be the set of compositions into parts 1 and ℓ, where ℓ ≥ 2. Let e_{ℓ}(n) denote the number of elements in E_{ℓ} of weight n. Chinn and Heubach [3] studied this family of compositions and, in particular, found

E_{ℓ}(x) := ∑_{n=0}^{∞} e_{ℓ}(n)x^{n} = \frac{1}{1 − x − x^{ℓ}} .

Then x^{ℓ+1}E_{ℓ}(x) = F_{ℓ}(x) and we have the following result.

Theorem 8. For n ≥ 0, F_{ℓ}(n + ℓ + 1) = e_{ℓ}(n).

Let H_{ℓ} be the set of compositions into parts greater than or equal to ℓ. Let h_{ℓ}(n) be the number of elements in H_{ℓ} of weight n. It is not difficult to show that (see, for example, [8, Theorem 3.13])

H_{ℓ}(x) := ∑_{n=0}^{∞} h_{ℓ}(n)x^{n} = \frac{1}{1 − (x^{ℓ} + x^{ℓ+1} + ⋯)} = \frac{1 − x}{1 − x − x^{ℓ}} .

Therefore, we have the following relation.

Theorem 9. For n ≥ 1, F_{ℓ}(n + 1) = h_{ℓ}(n).

Let G_{ℓ} be the set of binary words such that between any two successive ones there are at least ℓ−1 zeros. Let g_{ℓ}(n) be the number of words in G_{ℓ} of length n. Let w be a binary word in G_{ℓ} of length n > ℓ. Then w can be decomposed as w = 0w_{1} or w = 1 \underbrace{0 ⋯ 0}_{ℓ−1} w_{2}, where

w_{1}, w_{2} ∈ G_{ℓ}, which implies g_{ℓ}(n) = g_{ℓ}(n − 1) + g_{ℓ}(n − ℓ) for all n > ℓ. Thus, this sequence satisfies the same recurrence relation as F_{ℓ}(n). Note that g_{ℓ}(n) = n + 1 if n ∈ [ℓ], which follows from the definitions. Since F_{ℓ}(n + ℓ) = 1 if n ∈ [ℓ], applying the recurrence for F_{ℓ}(n) implies F_{ℓ}(n + 2ℓ) = n + 1 for n ∈ [ℓ]. Comparing the recurrences and initial values gives the following relation.

Theorem 10. For n ≥ 0, F_{ℓ}(n + 2ℓ) = g_{ℓ}(n).

We conclude this section by providing bijective proofs of the last three results.

Combinatorial proofs of Theorems 8 and 9.

Let E_{ℓ}(n) denote the set of compositions of n with parts 1 and ℓ and F_{ℓ}(n) the set of colored compositions enumerated by F_{ℓ}(n). We define a mapping f : E_{ℓ}(n) → F_{ℓ}(n + ℓ + 1) as follows. If λ = 1^{n−bℓ}ℓ^{b}, where 0 ≤ b ≤ ⌊n/ℓ⌋, then let f(λ) = ((b+1)ℓ+n−bℓ+1)_{(b+1)ℓ+1}. Otherwise, we have

λ = 1^{a_{0}}ℓ^{b_{1}}1^{a_{1}} ⋯ ℓ^{b_{r}}1^{a_{r}}ℓ^{b_{r+1}},

where r ≥ 1, a_{0} ≥ 0, a_{i}, b_{i} ≥ 1 if 1 ≤ i ≤ r and b_{r+1} ≥ 0. In this case, let

f(λ) = (b_{1}ℓ + a_{0} + 1)_{b_{1}ℓ+1}, (b_{2}ℓ + a_{1})_{b_{2}ℓ+1}, …, (b_{r}ℓ + a_{r−1})_{b_{r}ℓ+1}, ((b_{r+1} + 1)ℓ + a_{r})_{(b_{r+1}+1)ℓ+1}.

Note that f(λ) contains r + 1 parts and indeed belongs to F_{ℓ}(n + ℓ + 1) (a 1 not accounted for by λ occurs in the first part and there is an extra ℓ in the last part). Observe further that the last part of f(λ) has subscript greater than or equal to ℓ + 1 depending on whether the last part of λ is ℓ or 1. Upon considering the number of parts in a member of F_{ℓ}(n + ℓ + 1), the mapping f is seen to be reversible and hence yields the desired bijection.

To show Theorem 9, let H_{ℓ}(n) denote the set of compositions of n having parts of size ℓ or more. We define g : H_{ℓ}(n) → F_{ℓ}(n + 1) for n ≥ 1 as follows. If n ∈ [ℓ − 1], then both sets are empty, so assume n ≥ ℓ. Then we may express λ ∈ H_{ℓ}(n) as

λ = x_{1}ℓ^{a_{1}}x_{2}ℓ^{a_{2}} ⋯ x_{r}ℓ^{a_{r}},

where r ≥ 1, x_{1} ≥ ℓ, x_{i} ≥ ℓ + 1 if i > 1 and a_{i} ≥ 0 for all i. Let

g(λ) = (a_{1}ℓ + x_{1} + 1)_{(a_{1}+1)ℓ+1}, (a_{2}ℓ + x_{2})_{(a_{2}+1)ℓ+1}, …, (a_{r}ℓ + x_{r})_{(a_{r}+1)ℓ+1}.

One may verify that the mapping g is a bijection, which completes the proof.

Combinatorial proof of Theorem 10.

Let G_{ℓ}(n) denote the set of binary words enumerated by g_{ℓ}(n). We define a mapping f : G_{ℓ}(n) → F_{ℓ}(n + 2ℓ) in several steps as follows. Let λ = λ_{1}λ_{2} ⋯ λ_{n} ∈ G_{ℓ}(n) and first assume n ∈ [ℓ]. In this case, let

f(λ) = \begin{cases}(n + 2ℓ)_{ℓ+1}, & if λ = 0^{n}; \\ (n − s + ℓ)_{ℓ+1}, (s + ℓ)_{ℓ+1}, & if λ = 0^{s}10^{n−1−s}, where 1 ≤ s ≤ n − 1; \\ (n + 2ℓ)_{2ℓ+1}, & if λ = 10^{n−1}. \end{cases}

Henceforth, assume n > ℓ. We will also assume ℓ > 1, as the adjustments necessary in the ℓ = 1 case will be apparent. Note that λ ∈ G_{ℓ}(n) may start with an initial (possibly empty) run of 0’s with the remainder of λ being decomposed into sections of the form u = 10^{ℓ−1} (1 followed by ℓ − 1 0’s) and v = 10^{m−1} where m ≥ ℓ + 1 is arbitrary (to be specified). Furthermore, it is possible for λ to end in a section w of the form w = 10^{p}, where 0 ≤ p ≤ ℓ − 2.

First assume λ contains no section of the form v above. Then either

λ = 0^{n−iℓ}u^{i},  0 ≤ i ≤ ⌊n/ℓ⌋,  (1)

or

λ = 0^{n−p−1−iℓ}u^{i}w,  0 ≤ p ≤ ℓ − 2 and 0 ≤ i ≤ ⌊(n − p − 1)/ℓ⌋,  (2)

where w = 10^{p}. We define f in this case by considering whether or not n is divisible by ℓ. If ℓ divides n, then let f(λ) = (n + 2ℓ)_{(i+1)ℓ+1}, if λ is of the form (1), and let

f(λ) = (ℓ + p + 1)_{ℓ+1}, ((i + 1)ℓ + n − p − 1 − iℓ)_{(i+1)ℓ+1},

if of form (2). If ℓ does not divide n, then we define f(λ) the same way as before provided λ is not of the form (2) with n − p − 1 = iℓ. Note that n − p − 1 = iℓ corresponds to exactly one λ in (2) since 0 ≤ p ≤ ℓ − 2. We set f(λ) = (n + 2ℓ)_{qℓ+1} in this case where q = ⌊n/ℓ⌋ + 2 (note that qℓ + 1 ≤ n + 2ℓ if and only if ℓ does not divide n). Observe that in either case f maps the members of G_{ℓ}(n) not containing a v section in a one-to-one manner to the subset of F_{ℓ}(n + 2ℓ) whose members either have one part or have two parts where the first part is less than 2ℓ.

Assume henceforth that λ contains at least one section of the form v above. Then we may write

λ = 0^{j}u^{i_{1}}v_{1} ⋯ u^{i_{r}}v_{r}u^{i_{r+1}},  (3)

where r ≥ 1, j, i_{1}, …, i_{r+1} ≥ 0, and v_{i} = 10^{m_{i}−1} with m_{i} ≥ ℓ + 1 for 1 ≤ i ≤ r, or

λ = 0^{j}u^{i_{1}}v_{1} ⋯ u^{i_{r}}v_{r}u^{i_{r+1}}w,  (4)

with all the same restrictions as before and w = 10^{p} for some 0 ≤ p ≤ ℓ − 2. If λ is of the form (3), then let

f(λ) = ((i_{1} + 2)ℓ + j)_{(i_{1}+1)ℓ+1}, (i_{2}ℓ + m_{1})_{(i_{2}+1)ℓ+1}, …, (i_{r+1}ℓ + m_{r})_{(i_{r+1}+1)ℓ+1}.

Observe that r ≥ 1 implies f(λ) contains at least two parts in this case and m_{i} ≥ ℓ + 1 for all i implies the size of the part always exceeds the size of the subscript (with the first part of size at least 2ℓ).

Now suppose λ is of form (4). To define f, we consider cases on j. If j ≥ 1 in (4), then let

f(λ) = (ℓ + p + 1)_{ℓ+1}, ((i_{1} + 1)ℓ + j)_{(i_{1}+1)ℓ+1}, (i_{2}ℓ + m_{1})_{(i_{2}+1)ℓ+1}, …, (i_{r+1}ℓ + m_{r})_{(i_{r+1}+1)ℓ+1}.

Note f(λ) here must contain at least three parts and therefore this covers the remaining cases where the first part is less than 2ℓ. If j = 0 in (4), then let

f(λ) = ((i_{1} + 2)ℓ + p + 1)_{(i_{1}+2)ℓ+1}, (i_{2}ℓ + m_{1})_{(i_{2}+1)ℓ+1}, …, (i_{r+1}ℓ + m_{r})_{(i_{r+1}+1)ℓ+1}.

Notice that this covers the remaining ρ ∈ F_{ℓ}(n + 2ℓ) in which the first part of ρ is at least 2ℓ with ρ containing at least two parts. The inverse of f can then be constructed (we leave the details to the reader) in a composite manner in much the same way as f was above upon considering the number of parts and whether or not the first part is at least 2ℓ.

3 Subscript restrictions only on certain parts

Given integers ℓ, ℓ′, b, b′ ≥ 1, let D_{ℓa+b}^{ℓ′a′+b′}(ν) denote the number of n-color compositions of ν such that the parts of the form ℓa + b for some a ≥ 0 have only subscripts of the form ℓ′a′ +b′ for some a′ ≥ 0. Additionally, we denote by D_{ℓa+b}^{ℓ′a′+b′}(m, ν) the number of such n-color compositions of ν that have exactly m parts.

For example, D_{4a+3}^{3a′+1}(3) = 6, the compositions being

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

Theorem 11. Let GD_{ℓa+b}^{ℓ′a′+b′}(m, x) and GD_{ℓa+b}^{ℓ′a′+b′}(x) denote the generating functions for the sequences D_{ℓa+b}^{ℓ′a′+b′}(m, ν) and D_{ℓa+b}^{ℓ′a′+b′}(ν), respectively. Then we have

GD_{ℓa+b}^{ℓ′a′+b′}(m, x) = (x^{b}H(x^{ℓ}) + P (x) + ∑_{i=1, i≢b (mod ℓ)}^{ℓ} \frac{i + (ℓ − i)x^{ℓ}}{(1 − x^{ℓ})^{2}} x^{i})^{m} ,

GD_{ℓa+b}^{ℓ′a′+b′}(x) = \frac{x^{b}H(x^{ℓ}) + P (x) + ∑_{i=1, i≢b (mod ℓ)}^{ℓ} \frac{i+(ℓ−i)x^{ℓ}}{(1−x^{ℓ})^{2}} x^{i}}{1 − (x^{b}H(x^{ℓ}) + P (x) + ∑_{i=1, i≢b (mod ℓ)}^{ℓ} \frac{i+(ℓ−i)x^{ℓ}}{(1−x^{ℓ})^{2}} x^{i})},

where H(x) is the generating function of the sequence

h_{n} = \begin{cases}⌊\frac{ℓn+b−b′}{ℓ′} ⌋ + 1, & if ℓn + b ≥ b′ and n ≥ 0; \\ 0, & otherwise, \end{cases}

and P (x) is the polynomial given by

P (x) = ∑_{\begin{matrix}i≡b (mod ℓ) \\ 0≤i<b \end{matrix}} ix^{i}.

Proof. Summing the first expression over m ≥ 1 gives the second, so we need only prove the first. Let σ = σ_{1}σ_{2} ⋯ σ_{m} be a non-empty n-color composition having m parts such that parts of the form ℓa + b where a ≥ 0 have only subscripts of the form ℓ′a′ + b′ where a′ ≥ 0. First assume σ_{j} ≡ b (mod ℓ) and suppose σ_{j} = r = ℓa + b. If a ≥ 0 and r ≥ b′, then σ_{j} contributes to the generating function a w_{a}x^{r} term, where

w_{a} = ⌊\frac{ℓa + b − b′}{ℓ′} ⌋ + 1.

If a ≥ 0 and r < b′, then there are no possible such parts for otherwise the index would exceed the part (note that this case can occur only if b < b′).

If a < 0, then σ_{j} = r < b and there is a contribution to the generating function of rx^{r} per the definitions, and combining all such r yields the polynomial P (x) defined above. If σ_{j} ≢ b (mod ℓ), then there is again a contribution of rx^{r}. Thus, for each i ∈ [ℓ] such that i ≢ b (mod ℓ), we have a total contribution of

ix^{i} + (ℓ + i)x^{ℓ+i} + (2ℓ + i)x^{2ℓ+i} + ⋯

= ix^{i}(1 + x^{ℓ} + x^{2ℓ} + ⋯) + ℓx^{i}(x^{ℓ} + 2x^{2ℓ} + 3x^{3ℓ} + ⋯)

= \frac{ix^{i}}{1 − x^{ℓ}} + ℓx^{i} [\frac{y}{(1 − y)^{2}} ]_{y=x^{ℓ}} = \frac{ix^{i}}{1 − x^{ℓ}} + \frac{ℓx^{i+ℓ}}{(1 − x^{ℓ})^{2}} ,

which gives the final part of the formula for GD_{ℓa+b}^{ℓ′a′+b′}(m, x) above.

For example, the generating function for the sequence D_{3a+7}^{4a′+3}(m, ν) is given by

GD_{3a+7}^{4a′+3}(m, x) = (x^{7}H(x^{3}) + x + 4x^{4} + \frac{(2 + x^{3})}{(1 − x^{3})^{2}} x^{2} + \frac{3}{(1 − x^{3})^{2}} x^{3})^{m} ,

where H(x) = \frac{2+x^{2}+x^{3}−x^{4}}{(1−x)^{2}(1+x+x^{2}+x^{3})}. Note that H(x) is the generating function for the sequence

{2, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 10, 11, 11, 12, 13, 14, 14, 15, 16, 17, 17, 18, 19, 20, 20, 21, 22, … }.

Moreover,

GD_{3a+7}^{4a′+3}(x)

= \frac{−3x^{19} + 2x^{16} − x^{14} − 3x^{12} − 3x^{11} − 3x^{9} − 3x^{8} + 2x^{7} − 3x^{6} − 3x^{5} − 3x^{4} − 3x^{3} − 2x^{2} − x}{3x^{19} − 2x^{16} − x^{15} + x^{14} + 4x^{12} + 3x^{11} + 3x^{9} + 3x^{8} − 2x^{7} + 3x^{6} + 3x^{5} + 3x^{4} + 4x^{3} + 2x^{2} + x − 1}

= x + 3x^{2} + 8x^{3} + 21x^{4} + 55x^{5} + 144x^{6} + 372x^{7} + 977x^{8} + 2549x^{9} + 6647x^{10} + · · · .

For example, D_{3a+7}^{4a′+3}(7) = 372, as all n-color compositions of n = 7 are counted except

{7_{1}}, {7_{2}}, {7_{4}}, {7_{5}}, {7_{6}}.

Remark 12. Taking all of the relevant parameters to be one in Theorem 11 gives

GD_{a+1}^{a′+1}(m, x) = \frac{x^{m}}{(1 − x)^{2m}} , m ≥ 1,

and

GD_{a+1}^{a′+1}(x) = \frac{x}{1 − 3x + x^{2}} ,

which are the generating functions for the number with m parts and the total number of n-color compositions of ν for ν ≥ 1, respectively.

By setting ℓ = 2 = ℓ′ in Theorem 11, we have the following corollaries.

Corollary 13 (Theorem 2.4 of [13]). The generating functions for the number of n-color compositions of ν into m parts such that the odd parts have only even subscripts and for the total number of n-color compositions of ν such that the odd parts have only even subscripts are

GD_{2a+1}^{2a′+2}(m, x) = (\frac{2x^{2} + x^{3}}{(1 − x^{2})^{2}} )^{m} ,
GD_{2a+1}^{2a′+2}(x) = \frac{2x^{2} + x^{3}}{1 − 4x^{2} − x^{3} + x^{4}} .

Corollary 14 (Theorem 2.5 of [13]). The generating functions for the number of n-color compositions of ν into m parts such that the odd parts have only odd subscripts and for the total number of n-color compositions of ν such that the odd parts have only odd subscripts are

GD_{2a+1}^{2a′+1}(m, x) = (\frac{x + 2x^{2}}{(1 − x^{2})^{2}} )^{m} ,
GD_{2a+1}^{2a′+1}(x) = \frac{x + 2x^{2}}{1 − x − 4x^{2} + x^{4}} .

Corollary 15 (Theorem 2.6 of [13]). The generating functions for the number of n-color compositions of ν into m parts such that the even parts have only even (odd) subscripts and for the total number of n-color compositions of ν such that the even parts have only even (odd) subscripts are

GD_{2a+2}^{2a′+2}(m, x) = GD_{2a+2}^{2a′+1}(m, x) = (\frac{x + x^{2} + x^{3}}{(1 − x^{2})^{2}} )^{m} ,
GD_{2a+2}^{2a′+2}(x) = GD_{2a+2}^{2a′+1}(x) = \frac{x + x^{2} + x^{3}}{1 − x − 3x^{2} − x^{3} + x^{4}} .

4 A further related restriction

Given ℓ ≥ 1, let T_{ℓ}(ν) denote the number of n-color compositions of ν such that any part of the form ℓa + b for some a ≥ 0 and 1 ≤ b ≤ ℓ has a subscript of the same form. Additionally, we denote by T_{ℓ}(m, ν) the number of such n-color compositions of ν that have m parts.

For example, T_{4}(5) = 17, the compositions being

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

Similar to the proof of Theorems 1 and 2 above, we have the following result.

Theorem 16. Let GT_{ℓ}(m, x) and GT_{ℓ}(x) denote the generating functions for the sequences T_{ℓ}(m, ν) and T_{ℓ}(ν), respectively. Then we have

GT_{ℓ}(m, x) = (\frac{x}{(1 − x)(1 − x^{ℓ})})^{m} ,
GT_{ℓ}(x) = \frac{x}{1 − 2x − x^{ℓ} + x^{ℓ+1}} .

Moreover, the sequence T_{ℓ}(m, ν) for 1 ≤ m ≤ ν is given explicitly by

T_{ℓ}(m, ν) = \begin{aligned}⌊ & \frac{ν−m}{ℓ} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{m + i − 1}{m − 1}\binom{ν − ℓi − 1}{m − 1},

with T_{ℓ}(ν) = 2T_{ℓ}(ν − 1) + T_{ℓ}(ν − ℓ) − T_{ℓ}(ν − ℓ − 1) for ν > ℓ + 1.

Note that the sequences T_{ℓ}(ν) and C_{ℓa+1}(ν) are the same which can be shown using the definitions.

We now describe a statistic on n-color compositions which accounts for the expression given for T_{ℓ}(m, ν) above. More precisely, let S_{ℓ}(m, ν) denote the set of n-color compositions enumerated by T_{ℓ}(m, ν) and we determine a statistic σ on S_{ℓ}(m, ν) such that

|\{π ∈ S_{ℓ}(m, ν) : σ(π) = i\}| = \binom{m + i − 1}{m − 1}\binom{ν − ℓi − 1}{m − 1}.

Given a part α_{β} of π ∈ S_{ℓ}(m, ν), let σ(α_{β}) = ⌊(β − 1)/ℓ⌋. Define σ(π) to be the sum of the σ-values of its individual parts. For example, if ℓ = 3 and π = 5_{2}, 7_{7}, 8_{5}, 12_{9}, 3_{3} ∈ S_{3}(5, 35), then σ(π) = 0 + 2 + 1 + 2 + 0 = 5. Note that if β corresponds to the i-th smallest possible subscript on a part of π of size α, then α_{β} contributes i − 1 towards the σ(π) statistic value. If ℓ = 1, then it is seen that σ(π) is simply the sum of the subscripts of all the parts minus the number of parts of π. Define

t_{ν,m}^{(ℓ)}(q) = ∑_{π∈S_{ℓ}(m,ν)} q^{σ(π)}, ν ≥ m ≥ 1,

where q is an indeterminate. We have the following explicit formula for t_{ν,m}^{(ℓ)}(q).

Theorem 17. If ν ≥ m ≥ 1 and ℓ ≥ 1, then

t_{ν,m}^{(ℓ)}(q) = \begin{aligned}⌊ & \frac{ν−m}{ℓ} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{m + i − 1}{m − 1}\binom{ν − ℓi − 1}{m − 1}q^{i}.  (5)

Proof. Let σ′ be the statistic defined on π ∈ S_{ℓ}(m, ν) as follows. Given a part α_{β} of π, let σ′(α_{β}) = \frac{α−β}{ℓ} and define σ′(π) to be the sum of the σ′ values of its parts. For example, if π ∈ S_{3}(5, 35) is as before, then σ′(π) = 3. We first show that σ and σ′ are identically distributed on S_{ℓ}(m, ν). To do so, we change the subscripts on each part of π ∈ S_{ℓ}(m, ν) as follows. Let r_{s} be a part of π. First assume r is not divisible by ℓ. Then r = ℓa + b where a ≥ 0 and 1 ≤ b ≤ ℓ − 1 and s = ℓa′ + b for some 0 ≤ a′ ≤ a. In this case, we replace r_{s} with r_{t}, where t = ℓ(a − a′) + b. If r is divisible be ℓ, then r = ℓa and s = ℓa′ for some 1 ≤ a′ ≤ a, in which case we replace the part r_{s} with r_{t}, where t = ℓ(a − a′ + 1). Let π′ denote the resulting member of S_{ℓ}(m, ν). One may verify that the mapping π ↦ π′ is a bijection with σ(π) = σ′(π′) for all π.

We now count members π ∈ S_{ℓ}(m, ν) such that σ′(π) = i where 0 ≤ i ≤ ⌊(ν − m)/ℓ⌋. We denote these π by

π = (a_{1} + ℓb_{1})_{a_{1}}, …, (a_{m} + ℓb_{m})_{a_{m}},

where a_{j} ≥ 1 and b_{j} ≥ 0 for all j. Then b_{1}+⋯+b_{m} = i implies there are \binom{m+i−1}{m−1} possibilities for the b_{j}. Thus, a_{1} + ⋯ + a_{m} = ν − ℓi so that there are \binom{ν−ℓi−1}{m−1} possibilities for the a_{j}. Since the a_{j} and b_{j} may be chosen independently of one another, it follows that there are \binom{m+i−1}{m−1}\binom{ν−ℓi−1}{m−1} such π, which completes the proof of (5).

Let t_{ν}^{(ℓ)}(q, u) = ∑_{m=1}^{ν} t_{ν,m}^{(ℓ)}(q)u^{m} for ν ≥ 1 and define the generating function

T^{(ℓ)}(x; q, u) = ∑_{ν≥1} t_{ν}^{(ℓ)}(q, u)x^{ν}.

Using (5) and interchanging summation yields the following result.

Corollary 18. We have

T^{(ℓ)}(x; q, u) = \frac{xu}{1 − x(1 + u) − x^{ℓ}q + x^{ℓ+1}q}  (6)

and thus

t_{ν}^{(ℓ)}(q, u) = (1 + u)t_{ν−1}^{(ℓ)}(q, u) + qt_{ν−ℓ}^{(ℓ)}(q, u) − qt_{ν−ℓ−1}^{(ℓ)}(q, u),  ν > ℓ + 1.  (7)

Formulas (6) and (7) reduce, respectively, to the generating function and recurrence formulas for T_{ℓ}(ν) in Theorem 16 when q = u = 1. Note that the ℓ = u = 1 case of recurrence (7) was previously considered in [9]. A combinatorial proof may be given for (7) by considering whether or not the last part is 1_{1}, and if not, whether or not the last part is equal to its subscript. Finally, taking ℓ = 2 in the preceding yields a polynomial generalization of the problem of counting n-color compositions of a given size in which each part and its respective subscript always have the same parity.

5 Acknowledgments

The fourth author thanks an invitation from the Department of Mathematics and Statistics of Universidad del Tolima, Tolima, Colombia, where the presented work was initiated. Additionally, the research of the fourth author was partially supported by Universidad Nacional de Colombia, Project No. 46240.

References

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

[2] A. K. Agarwal, Combinatorial properties of n-color compositions, in Ramanujan Math. Soc. Lect. Notes Ser., Vol. 20, Ramanujan Math. Soc., 2013, pp. 13–28.

[3] P. Chinn and S. Heubach, (1, k)-compositions, Congr. Numer. 164 (2003), 183–194.

[4] A. Collins, C. Dedrickson, and H. Wang, Binary words, n-color compositions and bisection of the Fibonacci numbers, Fibonacci Quart. 51 (2013), 130–136.

[5] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd edition, Addison-Wesley, 1994.

[6] Y.-H. Guo, Some n-color compositions, J. Integer Sequences 15 (2012), Article 12.1.2.

[7] Y.-H. Guo, n-Color even compositions, Ars Combin. 109 (2013), 425–432.

[8] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, CRC Press, 2009.

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

[10] G. Narang and A. K. Agarwal, n-Color self-inverse compositions, Proc. Indian Acad. Sci. Math. Sci. 116 (2006), 257–266.

[11] G. Narang and A. K. Agarwal, Lattice paths and n-color compositions, Discrete Math. 308 (2008), 1732–1740.

[12] J. L. Ramírez and V. Sirvent, A note on the k-Narayana sequence, Ann. Math. Inform. 45 (2015), 91–105.

[13] R. Sachdeva and A. K. Agarwal, Combinatorics of certain restricted n-color composition functions, Discrete Math. 340 (2017), 361–372.

[14] C. Shapcott, C-color compositions and palindromes, Fibonacci Quart. 50 (2012), 297– 303.

[15] C. Shapcott, New bijections from n-color compositions, J. Comb. 4 (2013), 373–385.

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

    at https://oeis.org.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: n-color composition, generating function, combinatorial identity.

(Concerned with sequences \underline{A000045}, \underline{A000930}, \underline{A003269}, \underline{A003520}, \underline{A005708}, \underline{A052908}, \underline{A116732}, \underline{A176848}.)

Received January 26 2019; revised version received August 15 2019. Published in Journal of Integer Sequences, August 24 2019.

Return to Journal of Integer Sequences home page.