Allowing or Prohibiting Two Consecutive Colors in n-Color Compositions

Brian Hopkins Department of Mathematics and Statistics Saint Peter’s University Jersey City, NJ 07306 USA

               bhopkins@saintpeters.edu

Hua Wang Department of Mathematical Sciences Georgia Southern University Statesboro, GA 30460 USA

               hwang@georgiasouthern.edu

Abstract

Agarwal introduced n-color compositions in 2000 and subsequent research has considered both restricting which parts are allowed and, more recently, which colors are allowed. Here we consider allowing or prohibiting two consecutive colors, focusing on several cases that connect with other types of compositions. We also prove several identities for certain tribonacci numbers. Most proofs are combinatorial, several using the notion of spotted tilings introduced by the first named author in 2012.

1 Introduction and Background

A composition of a given positive integer n is an ordered sequence of positive integers with sum n. The summands are called parts of the composition. Write C(n) for the set of compositions of n with c(n) = |C(n)|. For example,

C(3) = {(3), (2, 1), (1, 2), (1, 1, 1)}.

We can represent a composition of n as a tiling of a 1 × n board where, in order from left to right, each part k corresponds to a 1 × k block. MacMahon [12] established that c(n) = 2^{n−1} by a combinatorial argument equivalent to the cut-join sequence: Working from left to right, each of the n − 1 junctures between the n cells is assigned C for cut if a new part starts with the next cell or J for join if the current part continues. Each possibility of n − 1 binary choices corresponds to a composition of n. See Figure 1 for an example of both the visual representation of a composition and its cut-join sequence.

                              J    J    C    J

Figure 1: The composition (3, 2) is shown as a 1 × 3 block followed by a 1 × 2 block. The cut-join sequence for (3, 2) is JJCJ.

Agarwal [1] introduced the concept of n-color compositions, where a part k has one of k possible colors, denoted by a subscript 1, …, k. Write CC(n) for the set of n-color compositions of n (this is the standard terminology even though n is being used in two different ways). For example,

CC(3) = {(3_{1}), (3_{2}), (3_{3}), (2_{1}, 1_{1}), (2_{2}, 1_{1}), (1_{1}, 2_{1}), (1_{1}, 2_{2}), (1_{1}, 1_{1}, 1_{1})}.

The first named author developed the following representation of n-color compositions [9]: In the tiling of a 1 × n board described above, the part k_{i} corresponds to a 1 × k block with a spot in position i. Here we modify the cut-join sequence to record the color by writing J_{i} for each join inside the block corresponding to k_{i}. (Compare this to a different modification used by Hopkins and Ouvry [10] where the cuts have subscripts.) See Figure 2 for an example of both notions.

                              [figure: J_{3}; J_{3}; C; J_{1}]

Figure 2: The n-color composition (3_{3}, 2_{1}) is shown as a 1 × 3 block with a spot in its third cell followed by a 1 × 2 block with a spot in its first cell. The modified cut-join sequence for (3_{3}, 2_{1}) is J_{3}J_{3}CJ_{1}.

There is additional terminology that will be helpful in the combinatorial arguments [11, Definition 3.1]: Given the 1 × k block corresponding to a part k_{c} of an n-color composition, the c-block consists of the first c cells (which includes the spotted cell) and the tail consists of any remaining cells. For instance, 3_{3} consists of a 3-block and an empty tail while 2_{1} consists of a 1-block and a length 1 tail.

The current authors recently made a thorough study of n-color compositions under various restrictions on colors [11]. In this work, we provide additional examples of results concerning consecutive colors b and b + 1.

In the next section, we cite general results for allowing two consecutive colors along with a new combinatorial interpretation in addition to several new particular results for small colors. In Section 3, we cite a general result for prohibiting two consecutive colors along with three new results for compositions prohibiting colors 1 and 2. (Below, propositions have been established before and are cited here for background or given new combinatorial proofs. Theorems are, we believe, results new with this work.)

2 Allowing two consecutive colors

In this section, we consider n-color compositions where, for some positive integer b ≥ 1, only colors b and b + 1 are allowed. Note that this precludes parts less than b from these compositions. We write CC_{b,b+1}(n) for the set of these compositions and cc_{b,b+1}(n) for their count.

Proposition 1. Given positive integers b and n, the number cc_{b,b+1}(n) of n-color compositions of n with only colors b and b + 1 allowed satisfies the recurrence

cc_{b,b+1}(n) = cc_{b,b+1}(n − 1) + cc_{b,b+1}(n − b) + cc_{b,b+1}(n − b − 1).  (1)

A direct formula for the number of n-color compositions of n with only colors b and b + 1 allowed is

cc_{b,b+1}(n) = ∑_{m=1}^{n} ∑_{i=0}^{n−bm} \binom{i + m − 1}{m − 1}\binom{m}{n − bm − i}.  (2)

These are special cases of [11, Theorem 2.1] and [11, Proposition 3.4], respectively.

Next, we establish a new combinatorial result connecting certain ternary stings and ncolor compositions of n with only colors b and b + 1 allowed.

Theorem 2. Given positive integers b and n, there is a bijection between CC_{b,b+1}(n), the n-color compositions of n with only colors b and b + 1 allowed, and length n − 1 ternary strings satisfying the following conditions.

• There are no 12 or 21 subwords,

• runs of 1’s have length at least b − 1, • runs of 2’s have length at least b, and

• successive 0’s are separated by at least b − 1 digits.

The constraints of such ternary strings can be viewed as walks on a state diagram of the kind used in symbolic dynamics; see Figure 3.

\begin{matrix}1 \\ 0 \\ 2 \\ (b − 1)+ \\ b+ \end{matrix}

Figure 3: A representation of the ternary words of Theorem 2. The b+ label on a loop, for instance, indicates that if a walk uses that edge, it must use it at least b times in a row.

Proof. Given a composition in CC_{b,b+1}(n), its modified cut-join sequence consists of n − 1 total symbols among C, J_{b}, and J_{b+1}. Create a length n − 1 ternary word via C ↦ 0, J_{b} ↦ 1, and J_{b+1} ↦ 2.

The resulting ternary word avoids 12 and 21 since adjacent parts (corresponding to runs of 1’s or 2’s) are separated by a cut corresponding to 0. A run of 1’s corresponds to a part with color b which has length at least b and thus at least b − 1 consecutive joins J_{b}, so the run of 1’s has length at least b − 1. Similarly, a run of 2’s corresponds to a part with color b + 1 so the run of 2’s has length at least b. Since the minimum part size is b, successive 0’s are separated by a run of 1’s (or 2’s) of length at least b − 1 (or b).

Given a ternary string satisfying the constraints, applying 0 ↦ C, 1 ↦ J_{b}, and 2 ↦ J_{b+1} gives the modified cut-join sequence of an n-color composition in CC_{b,b+1}(n) by the previous reasoning.

See Figure 4 for an example of the bijection.

[figure: 2; 2; 2; 2; 0; 1; 1; 0; 2; 2; 2; 0; 1; 1; 1]

Figure 4: The correspondence between (5_{4}, 3_{3}, 4_{4}, 4_{3}) ∈ CC_{3,4}(16) and the length 15 ternary string 222201102220111.

In the remainder of this section, we give further particular results for n-color compositions with only colors 1 and 2 allowed, with only colors 2 and 3 allowed, and with only colors 3 and 4 allowed.

2.1 Allowing colors 1 and 2

The recurrence for the number of n-color compositions of n with only colors 1 and 2 allowed is, by (1),

cc_{1,2}(n) = 2 cc_{1,2}(n − 1) + cc_{1,2}(n − 2),

\underline{A001333}. In the OEIS [13] entry for this sequence, Paul Barry stated a direct formula simpler than applying our general formula (2). Next, we provide a combinatorial argument using n-color compositions for his formula.

Theorem 3. Given a positive integer n,

cc_{1,2}(n) = ∑_{m=0}^{⌊ \frac{n}{2} ⌋} 2^{m}\binom{n}{2m}.

Proof. We show that the summation counts the number of ways to build a composition in CC_{1,2}(n). Let m satisfying 0 ≤ m ≤ ⌊\frac{n}{2}⌋ be the number of parts of size at least 2. There are \binom{n}{2m} ways to choose a sequence of cells a_{1}, a_{2}, …, a_{2m} from a 1 × n board. Let a_{2i+1} and a_{2i+2} mark the starting and ending cells of a part of size at least 2 for 0 ≤ i ≤ m − 1. The remaining cells between these parts (i.e., not between a_{2i+1} and a_{2i+2} for any i) are parts of size 1 which must have color 1. Each of the m larger parts has two choices of color, giving the factor 2^{m}.

Figure 5 shows an example of the procedure.

a_{1} a_{2} a_{3}  a_{4}  a_{5} a_{6}

Figure 5: The selection of 2, 3, 4, 8, 11, 13 for the a_{i} when m = 3 gives the composition (1, 2, 5, 1, 1, 3) ∈ C(13) which has 2^{3} = 8 possible ways to color the parts at least 2 to determine an element of CC_{1,2}(13).

2.2 Allowing colors 2 and 3

Our greatest number of new results concerns the number of n-color compositions of n with only colors 2 and 3 allowed. By (1) the recurrence is

cc_{2,3}(n) = cc_{2,3}(n − 1) + cc_{2,3}(n − 2) + cc_{2,3}(n − 3)

and this is (one version of) tribonacci numbers, \underline{A001590}. This sequence is known to count regular compositions restricted to parts congruent to 1 or 2 modulo 3 [3, 8]. Next we establish a bijection between CC_{2,3}(n + 1) and these restricted compositions which we denote by C_{1,2m3}(n).

Theorem 4. For each positive integer n, there is a bijection between n-color compositions of n + 1 with only colors 2 and 3 allowed and compositions of n with all parts congruent to 1 and 2 modulo 3. I.e.,

CC_{2,3}(n + 1) ≅ C_{1,2m3}(n).

Proof. Given the spotted tiling of a composition in CC_{2,3}(n+1), we construct a composition in C_{1,2m3}(n) as follows.

• For each part of the n-color composition of n + 1, convert the c-block into a part c and each cell of the tail into a part 1.

• Decrease the first part (which is 2 or 3) by 1.

• We now have a composition of n restricted to parts 1, 2, or 3 with first part 1 or 2. Combine runs of parts 3 with the part preceding the run.

Since all parts 3 have been combined into greater parts merged with a part 1 or 2, this gives a composition in C_{1,2m3}(n).

The reverse map is clear: Given a composition in C_{1,2m3}(n), we construct an element of CC_{2,3}(n + 1) as follows.

• Replace each part k > 3 with the part k mod 3 followed by ⌊k/3⌋ parts 3.

• Increase the first part by 1 (so that it is now 2 or 3).

• Convert each part 2 or 3 followed by a length j ≥ 0 run of parts 1 into a part of an n-color composition consisting of a 2- or 3-block, respectively, and length j tail, i.e., the part (j + 2)_{2} or (j + 3)_{3}.

This gives an n-color composition of n + 1 with each part colored 2 or 3 as desired.

See Figure 6 for an example of the bijection.

[figure]

Figure 6: The correspondence between (5_{3}, 3_{2}, 4_{3}) ∈ C_{2,3}(12) and (2, 1, 1, 2, 4, 1) ∈ C_{1,2m3}(11).

The n-color compositions with only colors 2 and 3 allowed match a particular type of “restricted tiling” studied by Barry Balof [2, Example 4], namely, tilings of a board using two types of 1 × 1 blocks and a single type of 1 × 2 blocks, such that no adjacent 1 × 1 blocks have the same type. Equivalently, let C_{1,2}^{∗}(n) be the compositions of n restricted to parts 1_{1}, 1_{2}, 2 with no adjacent parts 1 having the same color.

Theorem 5. There is a bijection between n-color compositions of n + 2 with only colors 2 and 3 allowed and compositions of n with parts 2, two types of parts 1, with no adjacent parts 1 of the same type. I.e.,

CC_{2,3}(n + 2) ≅ C_{1,2}^{∗}(n).

(1_{1}, 2, 2, 1_{2}, 1_{1}, 1_{2}, 2)
a c c c c b a b c c
c a c | c c | c b a b c | c c
(3_{2}, 2_{2}, 5_{3}, 2_{2})

Figure 7: The correspondence between (1_{1}, 2, 2, 1_{2}, 1_{1}, 1_{2}, 2) ∈ C_{1,2}^{∗}(10) and (3_{2}, 2_{2}, 5_{3}, 2_{2}) ∈ CC_{2,3}(12).

Proof. Given a composition in C_{1,2}^{∗}(n), we construct a composition in CC_{2,3}(n+2). Following Balof, we write a and b for the two types of parts 1.

First, replace each part 2 with two symbols c and add an additional symbol c at the beginning and end. This gives a length n + 2 string of symbols a, b, c with an even number of symbols c, beginning and ending with c, and with no aa or bb subsequences.

Similar to the proof of Theorem 3, supposing there are 2m symbols c, we consider the (2i + 1)st and (2i + 2)nd successive symbols c for each 0 ≤ i ≤ m − 1.

• If the two symbols c are adjacent, then map them to a part 2_{2}.

• If the two symbols c are separated by a string aba … of length k, then map the string caba … c to a part (k + 2)_{2}.

• If the two symbols c are separated by a string bab … of length k, then map the string cbab … c to a part (k + 2)_{3}.

Since the string had n + 2 symbols, this produces an n-color composition in CC_{2,3}(n + 2).

The reverse map is clear: Given an element of CC_{2,3}(n + 2), make the substitutions 2_{2} ↦ cc and, for k > 2, k_{2} ↦ caba … c and k_{3} ↦ cbab … c each consisting of k symbols. Removing the first and last symbol c leaves a string of symbols a, b, c where all symbols c occur in pairs. The substitution cc ↦ 2 gives a tiling equivalent to a composition in C_{1,2}^{∗}(n).

See Figure 7 for an example of the bijection.

The remaining results of this subsection are combinatorial proofs of identities involving certain tribonacci numbers, some known and some new. Since this sequence is of broader interest, we state the identities in terms of the sequence t(n) defined by

t(n) = t(n − 1) + t(n − 2) + t(n − 3)

with t(0) = 1, t(1) = 0, and t(2) = 1 (\underline{A001590}). The proofs make use of the fact cc_{2,3}(n) = t(n).

The first identity (in an equivalent form and starting from our t(2)) was used by Erdős, Székely, etc., in their study of “tribonacci graphs” [7]. It is also a special case of Identity 77 in the book of Benjamin and Quinn [4].

Proposition 6. For each integer n ≥ 3,

t(n) = t(n − 2) + 2 ∑_{i=3}^{n} t(n − i).

Proof. We establish a bijection

CC_{2,3}(n) ≅ CC_{2,3}(n − 2) ∪ ⋃_{i=3}^{n} 2 CC_{2,3}(n − i)

where 2 CC_{2,3}(k) denotes two copies of CC_{2,3}(k).

Given a composition in CC_{2,3}(n), consider its last part.

• If the last part is 2_{2}, then removing that part leaves a composition in CC_{2,3}(n − 2).

• If the last part is k_{2} for some k ≥ 3, then removing that part leaves a composition in one copy of CC_{2,3}(n − k).

• If the last part is k_{3} for some k ≥ 3, then removing that part leaves a composition in the other copy of CC_{2,3}(n − k).

The reverse map is clear: Given a composition in CC_{2,3}(n − 2), add a part 2_{2} at the end. Given a composition in one set of ⋃ CC_{2,3}(n − k) for k ≥ 3, add a part k_{2} at the end. Given a composition from the other ⋃ CC_{2,3}(n − k) for k ≥ 3, add a part k_{3} at the end. By construction, the images are distinct.

Proposition 6 involves the sum of consecutive t(i) terms. The identity in the following result, which combines cases of Identities 104 and 105 in Benjamin and Quinn [4], involves the sum of every other t(i) term.

Proposition 7. For each integer n ≥ 3,

t(n) = t(n − 1) + 1 + 2 ∑_{i=1}^{⌊n/2⌋−1} t(n − 2i − 1).

Proof. We establish a bijection

CC_{2,3}(n) ≅ CC_{2,3}(n − 1) ∪ {h} ∪ ⋃_{i=1}^{⌊n/2⌋−1} 2 CC_{2,3}(n − 2i − 1)

where h = h_{e} := ((2_{2})^{n/2}) if n is even (where the exponent designates repetition), h = h_{o} := (3_{3}, (2_{2})^{(n−3)/2}) if n is odd, and 2 CC_{2,3}(k) denotes two copies of CC_{2,3}(k).

Write a composition in CC_{2,3}(n) as the concatenation of b ∈ CC_{2,3}(n − 2k) and k parts 2_{2} where the final part b_{c} of b is not 2_{2}, i.e., the maximal terminal run of parts 2_{2} has length k.

If b is empty, then n is even and we have the composition h_{e} = ((2_{2})^{n/2}). If b = 3_{3}, then n is odd and we have the composition h_{o} = (3_{3}, (2_{2})^{(n−3)/2}). Otherwise, consider b_{c}, the last part of b.

• If b_{c} ≠ 3_{3}, then applying b_{c} ↦ (b − 1)_{c} and removing the k terminal parts 2_{2} leaves a composition in CC_{2,3}(n − 2k − 1).

• If b_{c} = 3_{3}, then removing that 3_{3} and the k terminal parts 2_{2} leaves a composition in CC_{2,3}(n − 2k − 3).

As k ranges from 0 to ⌊n/2⌋ − 1 (since h_{e} and h_{o} are excluded), together we have

(CC_{2,3}(n − 1) ∪ CC_{2,3}(n − 3)) ∪ (CC_{2,3}(n − 3) ∪ CC_{2,3}(n − 5)) ∪ ⋯

ending with (CC_{2,3}(5) ∪ CC_{2,3}(3)) ∪ CC_{2,3}(3) if n is even (recall that CC_{2,3}(1) = 0) and (CC_{2,3}(6) ∪ CC_{2,3}(4)) ∪ CC_{2,3}(4) if n is odd.

The reverse map is clear: For a composition in CC_{2,3}(n − 1) or one ⋃ CC_{2,3}(n − 2i − 1), apply k_{c} ↦ (k + 1)_{c} to the last part of the composition and append the appropriate number of parts 2_{2} to make a composition in CC_{2,3}(n). For a composition in the other set ⋃ CC_{2,3}(n − 2i − 1), add a part 3_{3} and then the appropriate number of parts 2_{2} to make a composition in CC_{2,3}(n). Carry over the composition h_{e} or h_{o} depending on whether n is even or odd, respectively. By construction, the images are distinct.

In addition to the above identities on t(n) that can be found in the existing literature, with n-color compositions and spotted tilings we can also prove some new identities.

First, we establish a combinatorial proof of a general recursion on t(n). We use the convention that t(n) = 0 for n < 0.

Theorem 8. For each integer n ≥ 0,

t(n) = \begin{cases}1 + ∑_{i=0}^{k}(t(n − 3i − 1) + t(n − 3i − 2)), & if n = 3k; \\ −1 + ∑_{i=0}^{k}(t(n − 3i − 1) + t(n − 3i − 2)), & if n = 3k + 1; \\ ∑_{i=0}^{k}(t(n − 3i − 1) + t(n − 3i − 2)), & if n = 3k + 2. \end{cases}

Proof. We consider the case n = 3k + 2 in detail and then explain the modifications for the other cases. We establish a bijection

CC_{2,3}(n) ≅ ⋃_{i=0}^{k}(CC_{2,3}(n − 3i − 1) ∪ CC_{2,3}(n − 3i − 2)).

Write a composition c ∈ CC_{2,3}(n) as the concatenation of b ∈ CC_{2,3}(n − 3k) and k parts 3_{3} where the final part b_{c} of b is not 3_{3}, i.e., the maximal terminal run of parts 3_{3} has length k. We know b is nonempty since n = 3k + 2. Consider b_{c}, the last part of b.

• If b_{c} ≠ 2_{2}, then applying b_{c} ↦ (b − 1)_{c} and removing the k terminal parts 3_{3} leaves a composition in CC_{2,3}(n − 3k − 1).

• If b_{c} = 2_{2}, then removing that 2_{2} and the k terminal parts 3_{3} leaves a composition in CC_{2,3}(n − 3k − 2).

The reverse map is clear: For a composition in ⋃ CC_{2,3}(n − 3i − 1), apply k_{c} ↦ (k + 1)_{c} to the last part of the composition and append the appropriate number of parts 3_{3} to make a composition in CC_{2,3}(n). For a composition in ⋃ CC_{2,3}(n − 3i − 2), add a part 2_{2} and then the appropriate number of parts 3_{3} to make a composition in CC_{2,3}(n).

In the case n = 3k, there is also the composition ((3_{3})^{k}) (for which b used above is empty) that contributes one to the sum. In the case n = 3k + 1, the first part of the reverse map references the last part of the empty composition of zero, so the count is decreased by one.

Now we prove an analogue of Proposition 6 involving consecutive t(i) terms and Proposition 7 involving every other t(i) term. Our last result for this subsection uses Theorem 8 to establish an identity involving every third t(i) term. The proof is algebraic but relies on the combinatorial proof of the previous theorem.

Theorem 9. For n ≥ 3,

t(n) + t(n − 2) = \begin{cases}2 ∑_{i=0}^{k−1} t(n − 3i − 1), & if n = 3k or n = 3k + 1; \\ 2 + 2 ∑_{i=0}^{k−1} t(n − 3i − 1), & if n = 3k + 2. \end{cases}

Proof. We consider the case n = 3k + 1. Applying Theorem 8 to t(n) = t(3k + 1) and t(n − 2) = t(3(k − 1) + 2) gives

t(n) + t(n − 2)

= −1 + ∑_{i=0}^{k}(t(3k − 3i) + t(3k − 3i − 1)) + ∑_{i=0}^{k−1}(t(3k − 3i − 2) + t(3k − 3i − 3))

= −1 + ∑_{i=0}^{k} t(3k − 3i) + (∑_{i=0}^{k}(t(3k − 3i − 1) + t(3k − 3i − 2))) + ∑_{i=1}^{k} t(3k − 3i)

= −1 + ∑_{i=0}^{k} t(3k − 3i) + [t(3k) − 1] + ∑_{i=1}^{k} t(3k − 3i)

= −2 + 2 ∑_{i=0}^{k} t(3k − 3i)

= −2 + 2t(0) + 2 ∑_{i=1}^{k} t(3k − 3i)

where the second equality uses t(−2) = 0 and the third equality invokes Theorem 8 again, here the n = 3k case. From the final line, the result follows since t(0) = 1.

The other two cases are similar (and slightly easier).

2.3 Allowing colors 3 and 4

The recurrence for the number of n-color compositions of n with only colors 3 and 4 allowed is, by (1),

cc_{3,4}(n) = cc_{3,4}(n − 1) + cc_{3,4}(n − 3) + cc_{3,4}(n − 4),

\underline{A070550}. Our last result for this section establishes a result mentioned in the OEIS connecting this sequence with the Fibonacci numbers (\underline{A000045}) defined by f(0) = 0, f(1) = 1, and f(n) = f(n − 1) + f(n − 2) for n ≥ 2.

For the following combinatorial proof, we use compositions of n with no parts 1, denoted Cˆ1(n). Cayley found that cˆ1(n) = f(n − 1) [5].

Proposition 10. For n ≥ 3,

cc_{3,4}(n) + cc_{3,4}(n − 2) = f(n − 1).

Proof. We establish a bijection

CC_{3,4}(n) ∪ CC_{3,4}(n − 2) ≅ Cˆ1(n).

For a composition in CC_{3,4}(n), working from left to right, apply the substitutions k_{3} ↦ k and k_{4} ↦ (2, k − 2). For a composition in CC_{3,4}(n − 2), use the same substitutions and add a part 2 at the end. This produces distinct compositions in Cˆ1(n).

For the inverse map, for a composition in Cˆ1(n), let j ≥ 0 be the length of the terminal run of parts 2. If j is odd, remove a part 2 from the end, giving a composition of n − 2 with an even length terminal run of parts 2. Working from left to right, map each part k ≥ 3 to k_{3} and, for each part 2, combine it with the following part k and map the pair (2, k) to (k + 2)_{4}. This produces distinct compositions in CC_{3,4}(n) ∪ CC_{3,4}(n − 2).

See Figure 8 for an example of the bijection.

3 Prohibiting two consecutive colors

In this section, we consider n-color compositions where, for some integer b ≥ 1, the colors b and b+1 are prohibited. We write CC{ \atop b,b+1}(n) for the set of these compositions and cc{ \atop b,b+1}(n) for their count.

(7_{3}) ⟷ (7)
(7_{4}) ⟷ (2, 5)
(4_{3}, 3_{3}) ⟷ (4, 3)
(4_{4}, 3_{3}) ⟷ (2, 2, 3)
(3_{3}, 4_{3}) ⟷ (3, 4)
(3_{3}, 4_{4}) ⟷ (3, 2, 2)
(5_{3}) ⟷ (5, 2)
(5_{4}) ⟷ (2, 3, 2)

Figure 8: The correspondence between CC_{3,4}(7) ∪ CC_{3,4}(5) and Cˆ1(7), each with f(6) = 8 elements.

Proposition 11. Given an integer b ≥ 1, the number of n-color compositions of n with colors b and b + 1 prohibited satisfies the recurrence

cc{ \atop b,b+1}(n) = 3 cc{ \atop b,b+1}(n − 1) − cc{ \atop b,b+1}(n − 2) − cc{ \atop b,b+1}(n − b) + cc{ \atop b,b+1}(n − b − 2).

This is a special case of [11, Theorem 2.2].

3.1 Prohibiting colors 1 and 2

We give three results for n-color compositions where the colors 1 and 2 are prohibited. Note that this means there cannot be parts of size 1 or 2. By Proposition 11 we have the recurrence

cc ˆ1,2(n) = 2 cc ˆ1,2(n − 1) − cc ˆ1,2(n − 2) + cc ˆ1,2(n − 3),  (3)

\underline{A005314}, which also has a direct formula,

cc ˆ1,2(n) = ∑_{m=1}^{⌊n/3⌋} \binom{n − m − 1}{2m − 1},

a special case of [11, Proposition 3.8].

Our first result of this section connects n-color compositions with colors 1 and 2 prohibited and regular compositions restricted to parts congruent to 1 or 2 modulo 4. Write C_{1,2m4}(n) for these compositions of n. Recall the notion of c-block and tail given in the introduction and used in Theorem 4.

Theorem 12. There is a bijection between n-color compositions of n + 2 with colors 1 and 2 prohibited and compositions of n restricted to parts congruent to 1 or 2 modulo 4. I.e.,

CC ˆ1,2(n + 2) ≅ C_{1,2m4}(n).

Proof. Given the spotted tiling of a composition in CC ˆ1,2(n+2), we construct a composition in C_{1,2m4}(n) as follows.

• Remove the first two cells (which cannot contain a spot).

• For each part of the n-color composition of n, convert the c-block into a part c and each cell of the tail into a part 1.

• In the composition of n, replace each part k with k ≡ 3, 4 mod 4 with the pair (k−2, 2).

Since all parts congruent to 3 or 4 modulo 4 have been replaced by parts congruent to 1 or 2 modulo 4, this gives a composition in C_{1,2m4}(n).

For the reverse map, given a composition in C_{1,2m4}(n), we construct an element of CC ˆ1,2(n + 2) as follows.

• Increase the first part by 2 making it at least 3.

• Working from right to left, replace each pair (k, 2) by k + 2. This gives a composition with no parts 2.

• Working left to right, convert each part c ≥ 3 followed by a length j ≥ 0 run of parts 1 into a part of an n-color composition consisting of a c-block and length j tail, i.e., the part (c + j)_{c}.

This gives an n-color composition of n + 2 with no part colored 1 or 2 as desired.

See Figure 9 for an example of the bijection.

[figure]

Figure 9: The correspondence between (5_{4}, 3_{3}, 4_{4}) ∈ CC ˆ1,2(12) and (2, 1, 1, 2, 2, 2) ∈ C_{1,2m4}(10).

Our next result involves palindromic compositions, those that read the same from left to right as from right to left. These have been studied since at least 1975 [8]. Among these, we consider palindromic compositions PCo ; ˆ2(n) that have no parts 2 and an odd number of parts which were studied by Chinn and Heubach [6].

Theorem 13. There is a bijection between n-color compositions of n with colors 1 and 2 prohibited and palindromic compositions of 2n − 5 with no parts 2 and an odd number of parts. I.e.,

CC ˆ1,2(n) ≅ PCo ; ˆ2(2n − 5).

Proof. Given a composition in CC ˆ1,2(n), first build a regular composition of n by converting each c-block into a part c and each cell of the tail into a part 1. Let ℓ be the length of this composition d and note that its first part d_{1} is at least 3 and that it has no part 2. Now prepend the reverse of d in front of d making a palindromic composition of 2n with 2ℓ parts including two parts d_{1} in the middle. Replace that pair (d_{1}, d_{1}) with a single part 2d_{1} − 5. This gives a palindromic composition of 2n − 5 with 2ℓ − 1 parts having no parts 2, i.e., an element of PCo ; ˆ2(2n − 5).

For the reverse map, given a composition in PCo ; ˆ2(2n−5), it has a well-defined middle part m since its length is odd. Because every other part of the palindromic composition is doubled and the sum is odd, we know m is odd. Replace m with the pair ((m + 5)/2, (m + 5)/2) giving a palindromic composition of 2n with an even number of parts. Now consider just the second half, a composition of n with first part (m + 5)/2 which is at least 3. To make an n-color composition, convert each part c with c ≥ 3 followed by a length j ≥ 0 run of parts 1 into a part of an n-color composition consisting of a c-block and length j tail. This produces an element of CC ˆ1,2(n).

See Figure 10 for an example of the bijection.

[figure: …; …; …; …; …]

Figure 10: The connection between an n-color composition (5_{4}, 6_{3}, …) and a palindromic composition of the form (…, 1, 1, 1, 3, 1, 3, 1, 3, 1, 1, 1, …).

Our last result connects two types of n-color compositions, those prohibiting colors 1 and 2 and those prohibiting the color 2 (counted by \underline{A034943}; see [11, §3.2.2]).

Theorem 14. For k a positive integer, the number of n-color compositions of 3k with colors 1 and 2 prohibited equals the number of n-color compositions of 2k − 1 prohibiting the color 2. I.e.,

cc ˆ1,2(3k) = ccˆ2(2k − 1).

In other words, there is a trisection of \underline{A005314} that matches a bisection of \underline{A034943}.

Proof. Let a(k) = cc ˆ1,2(3k). Repeated algebraic manipulation of

cc ˆ1,2(3k) = 2 cc ˆ1,2(3k − 1) − cc ˆ1,2(3k − 2) + cc ˆ1,2(3k − 3)

from (3) into an expression in terms of cc ˆ1,2(3k − 3), cc ˆ1,2(3k − 6), and cc ˆ1,2(3k − 9) gives

a(k) = 5a(k − 1) + 2a(k − 2) + a(k − 3)

with initial values a(1) = 1, a(2) = 5, a(3) = 28. The recurrence for a(k) can also be determined by using the generating function for cc ˆ1,2(k), namely

F (x) = \frac{x^{3}}{1 − 2x + x^{2} − x^{3}} ,

and determining the trisection of the series by

\frac{F (\sqrt[3]{x}) + F (ω\sqrt[3]{x}) + F (ω^{2}\sqrt[3]{x})}{3}

where ω is a primitive third root of unity.

Let b(k) = ccˆ2(2k − 1). By [11, Theorem 2.2] we have

ccˆ2(2k − 1) = 3 ccˆ2(2k − 2) − 2 ccˆ2(2k − 3) + ccˆ2(2k − 4).

Either approach mentioned above leads to

b(k) = 5b(k − 1) + 2b(k − 2) + b(k − 3)

with initial values b(1) = 1, b(2) = 5, b(3) = 28. Thus the sequences are equal.

Of course, in the spirit of this paper, we would prefer a combinatorial proof using a bijection CC ˆ1,2(3k) ≅ CCˆ2(2k − 1); we invite the reader to find one.

4 Acknowledgments

We appreciate the anonymous referee for careful reading and helpful suggestions.

References

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

[2] B. Balof, Restricted tilings and bijections, J. Integer Sequences 15 (2012), Article 12.2.3.

[3] 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.

[4] A. T. Benjamin and J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof. Mathematical Association of America, 2003.

[5] A. Cayley, Theorem on partitions, Messenger Math. 5 (1876) 188.

[6] P. Chinn and S. Heubach, Integer sequences related to compositions without 2’s, J. Integer Sequences 6 (2003), Article 03.2.3.

[7] L. Clark, R. Entringer, P. Erdős, H. Sun, and L. Székely, Extremal problems for the Bondy-Chvátal closure of a graph, in Graphs, Matrices, and Designs, ed. R. S. Rees, Marcel Dekker, 1993, pp. 73–83.

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

[9] B. Hopkins, Spotted tilings and n-color compositions, Integers 12B (2012), Article A6.

[10] B. Hopkins and S. Ouvry, Combinatorics of multicompositions, in Combinatorial and Additive Number Theory IV, ed. M. Nathanson, Springer, 2021, pp. 307–321.

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

[12] P. MacMahon, Combinatory Analysis, Vol. 1, Cambridge University Press, 1915.

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

2020 Mathematics Subject Classification: Primary 05A17; Secondary 05A15, 05A19, 11P81. Keywords: integer composition, n-color composition, recurrence relation, exact enumeration, bijective combinatorics.

(Concerned with sequences \underline{A000045}, \underline{A001333}, \underline{A001590}, \underline{A005314}, \underline{A034943}, and \underline{A070550}.)

Received June 26 2024; revised version received October 9 2024. Published in Journal of Integer Sequences, October 16 2024.

Return to Journal of Integer Sequences home page.