Some Identities For Palindromic Compositions

Yu-hong Guo^{1} School of Mathematics and Statistics Hexi University Zhangye, Gansu, 734000 P. R. China

                        gyh7001@163.com

Abstract This paper considers self-inverse or palindromic compositions of positive integers into parts ≤ 3. First we obtain two classes of such compositions that are enumerated by the Fibonacci numbers. Then we provide combinatorial identities between palindromic compositions and compositions into 1’s and 2’s, compositions into odd parts, and compositions into parts greater than 1.

1 Introduction

A composition of a positive integer n is a representation of n as a sequence of positive integers called parts which sum to n. 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).

A palindromic or self-inverse composition of n is one that remains unchanged when the order of its parts is reversed. For example, there are four palindromic compositions of 4, namely, (4), (1, 2, 1), (2, 2), (1, 1, 1, 1).

It is well known that there are 2^{n−1} unrestricted compositions of n [2, 1, 5, 8]. A composition may be represented graphically by means of the MacMahon zig-zag graph [5]. It is similar to the partition Ferrers graph except that the first dot of each part is aligned with the last part of its predecessor. For instance the zig-zag graph of the composition (6, 3, 1, 2, 2) is shown in Figure 1.

1This work was supported by the National Natural Science Foundation of China (Grant No. 11461020).

• • • • • •
• • •
•
• •
• •

Figure 1. zig-zag graph

The conjugate of a composition is obtained by reading its graph by columns from left to right. We see that the figure demonstrates that the conjugate of the composition (6, 3, 1, 2, 2) is (1, 1, 1, 1, 1, 2, 1, 3, 2, 1).

Munagi [6] presented five methods to obtain the conjugate of a composition, including the zig-zag graph. He also carried out a classification of the set of all compositions into certain classes based on some primary criteria.

We recall essential terms and definitions for a composition of n into k parts, say c = (c_{1}, c_{2}, …, c_{k}). The conjugate of c is usually denoted by c′, while the inverse of c, denoted by \overline{c}, is defined by \overline{c} = (c_{k}, c_{k−1}, …, c_{1}). Thus c is self-inverse or palindromic if c = \overline{c}.

In 1975, Hoggatt and Bicknell studied standard compositions having parts of size ≤ 3, and found the following relation.

Theorem 1. [4] Let C_{3}(n) be the number of compositions of a positive integer n using only the parts 1, 2 and 3. Then

C_{3}(n) = T_{n+1},

where T_{n} is the nth Tribonacci number, where T_{1} = 1, T_{2} = 1, T_{3} = 2, and T_{n} = T_{n−1} + T_{n−2} + T_{n−3}, n > 3.

Hoggatt and Bicknell also determined that the generating function for the number of palindromic compositions of n with 1, 2 and 3 is

\frac{1 + x + x^{2} + x^{3}}{1 − x^{2} − x^{4} − x^{6}} ;

the sequence of coefficients consists of two copies of the modified Tribonacci sequence interleaved: 1, 1, 2, 2, 3, 3, 6, 6, 11, 11, 20, 20, ….

In this paper, we consider palindromic compositions of positive integers when only parts of size ≤ 3 are allowed in both a composition and its conjugate. For example, c = (1, 3, 1) is a relevant composition, since c′ = (2, 1, 2) and the parts of both compositions do not exceed 3; but (1, 1, 1, 1, 1) is forbidden because the conjugate (5) contains a part greater than 3. In Section 2 we establish some properties of palindromic compositions. We also obtain two combinatorial relations between the number of palindromic compositions and the Fibonacci numbers. Consequently, we give several identities between these palindromic compositions of n and compositions of n into 1’s and 2’s, compositions of n into odd parts, and compositions of n into parts greater than 1.

2 Main results

We first obtain two fundamental recurrence relations for compositions of odd and even weights separately.

Let P_{3}(N) be the number of palindromic compositions c of N into parts ≤ 3 such that the parts c′ also consists of parts ≤ 3.

Theorem 2. Let n be an integer. Then

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

with P_{3}(1) = 1, P_{3}(3) = 2, P_{3}(5) = 2.

Proof. We give a combinatorial proof. If c is any palindromic composition, then it is clear that c′ is also palindromic. Because c has a first part 1 if and only c′ has a first part greater than 1, it will suffice to prove the recurrence for only compositions with first part 1. We split the relevant palindromic compositions c of 2n + 1 into two classes as follows:

(A): the first or last part of c is 1;

(B): the first two parts, or the last two parts, of c, are “1, 1”.

In class (A) we delete the first and last 1’s from c to get a composition β. Then we derive the conjugate β′ which is a relevant palindromic composition of 2n − 1 with first part 1. In class (B), we delete the first and last two copies of 1 from c to obtain a composition γ. The conjugate γ′ then gives a relevant palindromic composition of 2n − 3 with first part 1. Both transformations are clearly reversible.

For example, the only relevant composition of 1 is (1), for 2n + 1 = 3 the relevant compositions are (1, 1, 1) and (3), and for 2n + 1 = 5 they are (1, 3, 1) and (2, 1, 2).

Similarly, we also obtain the following recurrence relation for the number of palindromic compositions of even integers.

Theorem 3.

P_{3}(2n) = P_{3}(2n − 2) + P_{3}(2n − 4), n > 2,

with P_{3}(2) = 2, P_{3}(4) = 2.

The proof of Theorem 3 is similar to the proof of Theorem 2, so we omit the details. The following table gives some values of P_{3}(N):

\begin{matrix}N & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ P_{3}(N) & 1 & 2 & 2 & 2 & 2 & 4 & 4 & 6 & 6 & 10 & 10 & 16 & 16 & 26 & 26 & 42 & 42 \end{matrix}

Table 1: The number of palindromic compositions of N with parts ≤ 3

We find that P_{3}(N) forms a sequence of twice the Fibonacci numbers repeated, for all N > 1. The sequence P_{3}(2n + 1) appears as A055389, except for n = 0, in Sloane’s On-Line Encyclopedia of Integer Sequences [7]. Note that if the Fibonacci sequence is shifted so that F_{0} = 1, then A055389 becomes the sequence of twice the Fibonacci numbers. On the other hand P_{3}(2n) agrees at once with the sequence of twice the Fibonacci numbers.

Consequently we obtain the following corollaries.

Corollary 4.

P_{3}(2n + 1) = 2F_{n}, n > 0,

where F_{n} is the n^{th} Fibonacci number with F_{1} = F_{2} = 1, and F_{n} = F_{n−1} + F_{n−2}.

Corollary 5.

P_{3}(2n) = 2F_{n}, n > 0.

Corollary 6.

P_{3}(2n) = P_{3}(2n + 1), n > 0.

We also give the following generating functions:

Corollary 7.

∑_{n=0} P_{3}(2n + 1)x^{n} = \frac{1 + x + x^{2}}{1 − x − x^{2}} .
∑_{n=1} P_{3}(2n)x^{n} = \frac{2x}{1 − x − x^{2}} .

∑_{n=2} P_{3}(n)x^{n} = \frac{2x^{2}(x + 1)}{1 − x^{2} − x^{4}} .

It is well-known that the number of compositions of a positive integer n into odd parts is F_{n}, the number of compositions of n into parts of size 1 and 2 is equal to F_{n+1} and the number of compositions of n into parts greater than 1 is F_{n−1}. Consequently, we present the following identities for compositions of odd integers in line with Corollary 4.

Theorem 8. The number of compositions α of N with first part 1 such that the parts of α and α′ are ≤ 3 is equal to the number of compositions of N into odd parts.

Proof. We give a bijective proof. Denote the enumerated sets of compositions by CC(N)_{1} and {C_{odd}(N)} respectively. Let c ∈ CC(N)_{1} have the first part equal to 1. Then c may contain at most two initial 1’s. We define a bijection Υ : CC(N)_{1} → {C_{odd}(N)} below.

Thus if c starts with one 1, then c ↦ Υ(c) ∈ {C_{odd}(N)}; otherwise the first part of the conjugate c′ is 3 and we have c ↦ Υ(c′) ∈ {C_{odd}(N)}. Correspondingly if λ ∈ {C_{odd}(N)}, then λ ↦ Υ^{−1}(λ) ∈ CC(N)_{1} or λ ↦ Υ^{−1}(λ) with Υ^{−1}(λ)′ ∈ CC(N)_{1}. We now describe the function Υ : CC(N)_{1} → C_{odd}(N). Let c ∈ CC(N)_{1}.

Then if 2 ∉ c, we set Υ(c) = c ∈ {C_{odd}(N)}. Otherwise let γ be the composition obtained from c by replacing every instance of the string “1,2” by “1,1,1”. Then replace each maximal string of the form 1, 2, 2, … or 3, 2, 2, … in γ by the sum of its parts. Set the resulting composition equal to Υ(c). Clearly Υ(c) belongs to {C_{odd}(N)} and has first part 1.

Conversely we obtain Υ^{−1} using the following algorithm. Consider any λ ∈ {C_{odd}(N)}.

(i) Replace every string of r ≥ 3 ones by 1, 2, 1, 2, … from left to right, to produce a composition δ which has at most two 1’s immediately before an odd part.

(ii) Let h > 1 be an odd part of δ. If the string “1, 1, h” occurs, then replace h with its composition of the form “1, 2, …, 2”, otherwise replace h with its composition of the form 3, 2, …, 2, to obtain a composition β.

(iii) Lastly, replace every occurrence of the string “1, 1, 1” by “1, 2” to obtain Υ^{−1}(λ) ∈ CC(N)_{1}. (Note that this step ensures that the conjugate of Υ^{−1}(λ) has parts ≤ 3). Equivalently, apply steps (i) and (ii) to β until we obtain a relevant palindromic composition of N.

This shows that Υ is a bijection.

We give the following example to illustrate the bijection Υ in the proof of Theorem 8.

Example 9. If N = 10, then Υ maps (1, 2, 2, 3, 2), (1, 3, 2, 1, 2, 1), (1, 1, 3, 2, 1, 2) ∈ CC(10)_{1} to (1, 1, 3, 5), (1, 5, 1, 1, 1, 1), (3, 1, 1, 1, 3, 1) ∈ {C_{odd}(10)} respectively, as follows:

(1, 2, 2, 3, 2) ⟶ (1, 1, 1, 2, 3, 2) ⟶ (1, 1, 3, 5),
(1, 3, 2, 1, 2, 1) ⟶ (1, 3, 2, 1, 1, 1, 1) ⟶ (1, 5, 1, 1, 1, 1),
(1, 1, 3, 2, 1, 2) ⟶ (3, 1, 2, 3, 1) ⟶ (3, 1, 1, 1, 3, 1).

Similarly Υ maps (1, 1, 3, 3, 2, 1) ∈ CC(11)_{1} to (3, 1, 1, 1, 1, 1, 3) ∈ {C_{odd}(11)} as follows:

(1, 1, 3, 3, 2, 1) ⟶ (3, 1, 2, 1, 2, 2) ⟶ (3, 1, 1, 1, 1, 1, 1, 2) ⟶ (3, 1, 1, 1, 1, 1, 3);

and conversely,

(3, 1, 1, 1, 1, 1, 3) ⟶ (3, 1, 2, 1, 1, 3) ⟶ (3, 1, 2, 1, 1, 1, 2) ⟶ (3, 1, 2, 1, 2, 2)
⟶ (1, 1, 3, 3, 2, 1).

We are now ready to prove the following important combinatorial identity.

Theorem 10. Let C_{odd}(N) be the number of compositions of n into odd parts. Then

P_{3}(2n + 1) = 2C_{odd}(n), n > 0.  (1)

Proof. First we show that there is a bijection between compositions enumerated by P_{3}(2n+1) and compositions α of n such that the parts of α and α′ are ≤ 3. Denote the the enumerated sets by {P_{3}(2n+1)} and CC(n) respectively. Let c = (c_{1}, …, c_{i−1}, c_{i}, c_{i−1}, …, c_{1}) ∈ {P_{3}(2n+ 1)}. Then c_{i} = 1 or c_{i} = 3. Define a function Φ : {P_{3}(2n + 1)} → CC(n) as follows.

If c_{i} = 1, then Φ(c) = (c_{1}, …, c_{i−1}) ∈ CC(n), and if c_{i} = 3, then Φ(c) = (c_{1}, …, c_{i−1}, 1) ∈ CC(n). Due to the inherited parts, we see that Φ(c) as well as Φ(c)′ are compositions of n with parts ≤ 3. Conversely, let α = (α_{1}, …, α_{k}) ∈ CC(n). Then we obtain that Φ^{−1}(α) is given by c = (α_{1}, …, α_{k}, 1, α_{k}, …, α_{1}) if α_{k} > 1 or by c = (α_{1}, …, α_{k−1}, 3, α_{k−1}, …, α_{1}) if α_{k} = 1. Hence Φ is a bijection.

Note that Φ maps a composition with first part 1 to a composition with first part 1 and vice-versa. So by Theorem 8 there is a bijection between the set of compositions in {P_{3}(2n + 1)} with first part 1 and {C_{odd}(n)}. Since the conjugate of a composition with first part > 1 has first part 1, it also follows that the set of compositions in {P_{3}(2n + 1)} with first part > 1 is in bijection with {C_{odd}(n)}. In other words, we have proved that |{P_{3}(2n + 1)}| = 2|{C_{odd}(n)}| which is (1).

This completes the proof.

We cite an example to illustrate Theorem 10.

Example 11. Let n = 6, the corresponding relations between the relevant palindromic compositions of 13 and compositions of 6 into odd parts are as follows.

(1, 2, 3, 1, 3, 2, 1) ⟷ (1, 1, 1, 3) ⟷ (2, 2, 1, 3, 1, 2, 2),
(1, 3, 2, 1, 2, 3, 1) ⟷ (1, 5) ⟷ (2, 1, 2, 3, 2, 1, 2),
(1, 3, 1, 3, 1, 3, 1) ⟷ (1, 3, 1, 1) ⟷ (2, 1, 3, 1, 3, 1, 2),
(1, 2, 2, 3, 2, 2, 1) ⟷ (1, 1, 3, 1) ⟷ (2, 2, 2, 1, 2, 2, 2),
(1, 2, 1, 2, 1, 2, 1, 2, 1) ⟷ (1, 1, 1, 1, 1, 1) ⟷ (2, 3, 3, 3, 2),
(1, 1, 3, 3, 3, 1, 1) ⟷ (3, 1, 1, 1) ⟷ (3, 1, 2, 1, 2, 1, 3),
(1, 1, 2, 1, 3, 1, 2, 1, 1) ⟷ (3, 3) ⟷ (3, 3, 1, 3, 3),
(1, 1, 2, 2, 1, 2, 2, 1, 1) ⟷ (5, 1) ⟷ (3, 2, 3, 2, 3).

Theorem 12. Let C_{2}(N) be the number of compositions of N into parts of size 1, 2. Then

P_{3}(2n + 1) = 2C_{2}(n − 1), n > 1.  (2)

Proof. Given a composition α enumerated by P_{3}(2n + 1) with first and last parts equal to 1, we first use Theorem 10 to obtain a composition β of n into odd parts. Next, we replace each odd part h > 1 by 1, 2, …, 2 to obtain a composition γ of n into 1’s and 2’s with first part 1. Finally, a composition enumerated by C_{2}(n − 1) is obtained by deleting the first part 1.

Obviously, this correspondence is one-to-one. This completes the proof.

Theorem 13. Let C_{>1}(N) be the number of compositions of N into parts greater than 1. Then

P3^{′}(2n + 1) = 2C_{>1}(n + 1), n ≥ 1.  (3)

Proof. Given a composition α enumerated by P_{3}(2n + 1) with first and last parts equal to 1, we use Theorem 10 to obtain a composition β of n into odd parts. Then we replace each odd part h > 1 by 1, 2, …, 2 to obtain a composition γ of n into 1’s and 2’s with first part 1. Next we append 1 to the right end of γ to obtain a composition λ of n + 1 into 1’s and 2’s having first and last parts equal to 1. Finally we take the conjugate λ′ which is a composition of n + 1 into parts greater than 1.

This correspondence is clearly one-to-one. The proof is complete.

We cite an example to illustrate Theorem 13.

Example 14. Let n = 6, the corresponding relations between the relevant palindromic compositions of 13 and compositions of 7 into parts greater than 1 are as follows.

(1, 2, 3, 1, 3, 2, 1) ⟷ (5, 2) ⟷ (2, 2, 1, 3, 1, 2, 2),
(1, 3, 2, 1, 2, 3, 1) ⟷ (3, 2, 2) ⟷ (2, 1, 2, 3, 2, 1, 2),
(1, 3, 1, 3, 1, 3, 1) ⟷ (3, 4) ⟷ (2, 1, 3, 1, 3, 1, 2),
(1, 2, 2, 3, 2, 2, 1) ⟷ (4, 3) ⟷ (2, 2, 2, 1, 2, 2, 2),
(1, 2, 1, 2, 1, 2, 1, 2, 1) ⟷ (7) ⟷ (2, 3, 3, 3, 2),
(1, 1, 3, 3, 3, 1, 1) ⟷ (2, 5) ⟷ (3, 1, 2, 1, 2, 1, 3),
(1, 1, 2, 1, 3, 1, 2, 1, 1) ⟷ (2, 3, 2) ⟷ (3, 3, 1, 3, 3),
(1, 1, 2, 2, 1, 2, 2, 1, 1) ⟷ (2, 2, 3) ⟷ (3, 2, 3, 2, 3).

We state analogous identities for the number P_{3}(2n) of palindromic compositions of even integers 2n when only parts of size ≤ 3 are allowed in both a composition and its conjugate.

Theorem 15.

P_{3}(2n) = 2C_{odd}(n), n > 0.  (4)

Theorem 16.

P_{3}(2n) = 2C_{2}(n − 1), n > 1.  (5)

Theorem 17.

P_{3}(2n) = 2C_{>1}(n + 1), n ≥ 1.  (6)

The proofs of Theorems 15 to 17 are similar to the proofs of the foregoing identities for P_{3}(2n + 1). So we omit the details. We only cite an example below to illustrate Theorem 17.

Example 18. Let n = 6, the corresponding relations between the relevant palindromic compositions of 12 and compositions of 7 into parts greater than 1 are as follows.

(1, 2, 3, 3, 2, 1) ⟷ (5, 2) ⟷ (2, 2, 1, 2, 1, 2, 2),

(1, 3, 2, 2, 3, 1) ⟷ (3, 2, 2) ⟷ (2, 1, 2, 2, 2, 1, 2),
(1, 3, 1, 2, 1, 3, 1) ⟷ (3, 4) ⟷ (2, 1, 3, 3, 1, 2),
(1, 2, 2, 2, 2, 2, 1) ⟷ (4, 3) ⟷ (2, 2, 2, 2, 2, 2),
(1, 2, 1, 2, 2, 1, 2, 1) ⟷ (7) ⟷ (2, 3, 2, 3, 2),
(1, 1, 3, 2, 3, 1, 1) ⟷ (2, 5) ⟷ (3, 1, 2, 2, 1, 3),
(1, 1, 2, 1, 2, 1, 2, 1, 1) ⟷ (2, 3, 2) ⟷ (3, 3, 3, 3),
(1, 1, 2, 2, 2, 2, 1, 1) ⟷ (2, 2, 3) ⟷ (3, 2, 2, 2, 3).

3 Acknowledgments

The author would like to thank the referees for their valuable comments and corrections which have improved the quality of this paper. Special thanks also to Professor Augustine Munagi for his revision of this paper.

References

[1] G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1984.

[2] G. E. Andrews and K. Eriksson, Integer Partitions, Cambridge University Press, 2004.

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

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

[5] P. A. MacMahon, Combinatory Analysis, Vol. I, Cambridge University Press, 1995.

[6] A. O. Munagi, Primary classes of compositions of numbers, Ann. Math. Inform., 41 (2013), 193–204.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org.

[8] R. P. Stanley, Enumerative Combinatorics, Vol. I, Cambridge University Press, 1997.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A17, 05A19.

Keywords: palindromic composition, Fibonacci number, identity, combinatorial proof.

(Concerned with sequence \underline{A055389}.)

Received October 11 2017; revised versions received October 14 2017; October 24 2017; May 12 2018; June 9 2018; June 11 2018. Published in Journal of Integer Sequences, August 22 2018.

Return to Journal of Integer Sequences home page.