n-Color Odd Self-Inverse Compositions

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

                        gyh7001@163.com

Abstract An n-color odd self-inverse composition is an n-color self-inverse composition with odd parts. In this paper, we obtain generating functions, explicit formulas, and recurrence formulas for n-color odd self-inverse compositions.

1 Introduction

In the classical theory of partitions, compositions were first defined by MacMahon [9] as ordered partitions. For example, there are 5 partitions and 8 compositions of 4. The partitions are 4, 31, 22, 211, 1111 and the compositions are 4, 31, 13, 22, 211, 121, 112, 1111.

Agarwal and Andrews [1] defined an n-color partition as a partition in which a part of size n can come in n different colors. They denoted different colors by subscripts: n_{1}, n_{2}, …, n_{n}. In analogy with MacMahon’s ordinary compositions, Agarwal [2] defined an n-color composition as an n-color ordered partition. Thus, for example, there are 8 n-color compositions of 3, viz.,

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}.

More properties of n-color compositions were given in [3, 5].

Definition 1. ([9]) A composition is said to be self-inverse when the parts of the composition read from left to right are identical with the parts when read from right to left.

1This work is supported by the National Natural Science Foundation of China (Grant No. 11461020) and the Fund of the Education Department of Gansu Province (No. 2010-04.)

In analogy with the definition above for classical self-inverse compositions, Narang and Agarwal [10] defined an n-color self-inverse composition and gave some properties of them. Definition 2. ([10]) An n-color odd composition is an n-color composition with odd parts.

For example there are 8 n-color self-inverse compositions of 4, viz.,

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

In 2010, the author [6] also defined an n-color even self-inverse composition and gave some properties. Definition 3. ([6]) An n-color even composition is an n-color composition whose parts are even. Definition 4. ([6]) An n-color even composition whose parts read from left to right are identical with when read from right to left is called an n-color even self-inverse composition.

Thus, for example, there are 8 n-color even self-inverse compositions of 4, viz.,

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

And there are 6 n-color even self-inverse compositions of 4, viz.,

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

Recently, the author [7] studied n-color odd compositions. Definition 5. ([7]) An n-color odd composition is an n-color composition whose parts are odd.

Thus, for example, there are 7 n-color odd compositions of 4, viz.,

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

In this paper, we shall study n-color odd self-inverse compositions. Definition 6. An n-color odd composition whose parts read from left to right are identical with when read from right to left is called an n-color odd self-inverse composition.

Thus, for example, there are 4 n-color odd self-inverse compositions of 6, viz.,

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

In section 2 we shall give explicit formulas, recurrence formulas, generating functions for n-color odd self-inverse compositions.

The author [7] proved the following theorems.

Theorem 7. ([7]) Let C_{o}(m, q) and C_{o}(q) denote the enumerative generating functions for C_{o}(m, ν) and C_{o}(ν), respectively, where C_{o}(m, ν) is the number of n-color odd compositions of ν into m parts and C_{o}(ν) is the number of n-color odd compositions of ν. Then

C_{o}(m, q) = \frac{q^{m}(1 + q^{2})^{m}}{(1 − q^{2})^{2m}} ,  (1)
C_{o}(q) = \frac{q + q^{3}}{1 − q − 2q^{2} − q^{3} + q^{4}} ,  (2)
C_{o}(m, ν) = ∑_{i+j= \frac{ν−m}{2}} \binom{2m + i − 1}{2m − 1}\binom{m}{j},  (3)

C_{o}(ν) = ∑_{m≤ν} ∑_{i+j= \frac{ν−m}{2}} \binom{2m + i − 1}{2m − 1}\binom{m}{j}.  (4)

where (ν − m) is even, and (ν − m) ≥ 0; 0 ≤ i, j are integers.

Theorem 8. ([7]) Let C_{o}(ν) denote the number of n-color odd compositions of ν. Then

C_{o}(1) = 1, C_{o}(2) = 1, C_{o}(3) = 4, C_{o}(4) = 7 and
C_{o}(ν) = C_{o}(ν − 1) + 2C_{o}(ν − 2) + C_{o}(ν − 3) − C_{o}(ν − 4) for ν > 4.

2 Main results

In this section, we first prove the following explicit formulas for the number of n-color odd self-inverse compositions.

Theorem 9. Let S(O, ν) denote the number of n-color odd self-inverse compositions of ν. Then

(1) S(O, 2ν + 1) = (2ν + 1) + ∑_{t=1}^{2ν−1} ∑_{m≤ \frac{2ν+1−t}{2}} ∑_{i+j= \frac{2ν+1−t−2m}{4}} t\binom{2m + i − 1}{2m − 1}\binom{m}{j},

where ν = 0, 1, 2, …; t = 2k + 1, k = 0, 1, 2, …, (ν − 1); 0 ≤ \frac{2ν+1−t−2m}{2} is even; 0 ≤ i, j are integers.

(2) S(O, 2ν) = ∑_{m≤ν} ∑_{i+j= \frac{ν−m}{2}} \binom{2m + i − 1}{2m − 1}\binom{m}{j},

where 0 ≤ ν − m is even, and 0 ≤ i, j are integers.

Proof. (1) Obviously, an odd number which is 2ν + 1 (ν = 0, 1, 2, …) can have odd selfinverse n-color compositions only when the number of parts is odd. There are 2ν + 1 n-color odd self-inverse compositions when the number of parts is only one. An odd self-inverse compositions of 2ν + 1 into 2m + 1 (m ≥ 1) parts can be read as a central part, say, t (where t is odd) and two identical odd n-color compositions of \frac{2ν+1−t}{2} into m parts on each side of the central part. The number of odd n-color compositions of \frac{2ν+1−t}{2} into m parts is C_{o}(m, \frac{2ν+1−t}{2}) by equation (3). Now the central part can appear in t ways. Therefore, the number of n-color odd self-inverse compositions of 2ν + 1 is

S(O, 2ν + 1) = (2ν + 1) + ∑_{t=1}^{2ν−1} ∑_{m≤ \frac{2ν+1−t}{2}} tC_{o} (m, \frac{2ν + 1 − t}{2})

= (2ν + 1) + ∑_{t=1}^{2ν−1} ∑_{m≤ \frac{2ν+1−t}{2}} ∑_{i+j= \frac{2ν+1−t−2m}{4}} t\binom{2m + i − 1}{2m − 1}\binom{m}{j}.

(2) For even numbers 2ν (ν = 1, 2, …), we can have odd self-inverse n-color compositions only when the number of parts is even, and the two identical odd n-color compositions are exactly odd n-color compositions of ν, from equation (4) we see that the number of these is

∑_{m≤ν} ∑_{i+j= \frac{ν−m}{2}} \binom{2m + i − 1}{2m − 1}\binom{m}{j}.

Hence, the number of n-color odd self-inverse compositions of 2ν is

S(O, 2ν) = ∑_{m≤ν} ∑_{i+j= \frac{ν−m}{2}} \binom{2m + i − 1}{2m − 1}\binom{m}{j}.

We complete the proof of this theorem.

From the proof of this theorem we can see that odd n have n-color odd self-inverse compositions where the number of parts is odd. And even n have n-color odd self-inverse compositions where the number of parts is even. Let S_{o}(ν, m) denote the number of n-color odd self-inverse compositions of ν into m parts. Then we can get the following formula easily.

S_{o}(2k + 1, 2l + 1) = ∑_{t=1}^{2k−1} ∑_{i+j= \frac{2k+1−t−2l}{4}} \binom{2l + i − 1}{2l − 1}\binom{l}{j}.

where t is odd, k, l are integers and k, l ≥ 0.

S_{o}(2k, 2l) = ∑_{i+j= \frac{k−l}{2}} \binom{2l + i − 1}{2l − 1}\binom{l}{j}.

Table 1: S_{o}(ν, m) when both ν and m are odd

\begin{matrix}[figure: ν; m] & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & s_{ν} \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 3 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 \\ 5 & 5 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 9 \\ 7 & 7 & 8 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 19 \\ 9 & 9 & 16 & 11 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 40 \\ 11 & 11 & 29 & 25 & 16 & 3 & 1 & 0 & 0 & 0 & 0 & 83 \\ 13 & 13 & 49 & 56 & 34 & 17 & 3 & 1 & 0 & 0 & 0 & 173 \\ 15 & 15 & 72 & 110 & 96 & 43 & 20 & 3 & 1 & 0 & 0 & 360 \\ 17 & 17 & 104 & 206 & 200 & 143 & 52 & 23 & 3 & 1 & 0 & 749 \\ 19 & 19 & 145 & 346 & 442 & 317 & 199 & 61 & 26 & 3 & 1 & 1559 \end{matrix}

where k, l are integers and k, l ≥ 0.

Now S_{o}(ν, m) with ν, m = 1, 2, …, 20 is given in Tables 1 and 2.

From Tables 1 and 2 we can see the recurrence formulas for the number of the n-color odd self-inverse compositions of ν. So we prove the following recurrence relations.

Table 2: S_{o}(ν, m) when both ν and m are even

\begin{matrix}[figure: ν; m] & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & t_{ν} \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 4 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 6 & 3 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 \\ 8 & 0 & 6 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 7 \\ 10 & 5 & 0 & 9 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 15 \\ 12 & 0 & 19 & 0 & 12 & 0 & 1 & 0 & 0 & 0 & 0 & 32 \\ 14 & 7 & 0 & 42 & 0 & 15 & 0 & 1 & 0 & 0 & 0 & 65 \\ 16 & 0 & 44 & 0 & 74 & 0 & 18 & 0 & 1 & 0 & 0 & 137 \\ 18 & 9 & 0 & 138 & 0 & 115 & 0 & 21 & 0 & 1 & 0 & 284 \\ 20 & 0 & 85 & 0 & 316 & 0 & 165 & 0 & 24 & 0 & 1 & 591 \end{matrix}

Theorem 10. Let s_{ν} and t_{ν} denote the number of n-color odd self-inverse compositions for 2ν + 1 and 2ν, respectively. Then

(1) s_{0} = 1, s_{1} = 4, s_{2} = 9, s_{3} = 19 and
s_{ν} = s_{ν−1} + 2s_{ν−2} + s_{ν−3} − s_{ν−4} for ν > 3
(2) t_{1} = 1, t_{2} = 1, t_{3} = 4, t_{4} = 7 and
t_{ν} = t_{ν−1} + 2t_{ν−2} + t_{ν−3} − t_{ν−4} for ν > 4.

Proof. (Combinatorial) (1) To prove that s_{ν} = s_{ν−1} + 2s_{ν−2} + s_{ν−3} − s_{ν−4}, we split the n-color odd self-inverse compositions enumerated by s_{ν} + s_{ν−4} into four classes:

(A) s_{ν} with 1_{1} on both ends. (B) s_{ν} with 3_{3} on both ends. (C) s_{ν} with h_{t} on both ends, h > 1, 1 ≤ t ≤ h − 2 and n-color odd self-inverse compositions of 2ν + 1 of form (2ν + 1)_{u}, 1 ≤ u ≤ 2ν − 3. (D) s_{ν} with h_{t} on both ends except 3_{3}, h > 1, h − 1 ≤ t ≤ h, (2ν + 1)_{u}, 2ν − 2 ≤ u ≤ 2ν + 1 and those enumerated by s_{ν−4}.

We transform the n-color odd self-inverse compositions in class (A) by deleting 1_{1} on both ends. This produces n-color odd self-inverse compositions enumerated by s_{ν−1}. Conversely, for any n-color odd composition enumerated by s_{ν−1} we add 1_{1} on both ends to produce the elements of the class (A). In this way we establish that there are exactly s_{ν−1} elements in the class (A).

Similarly, we can produce s_{ν−3} n-color odd self-inverse compositions in class (B) by deleting 3_{3} on both ends.

Next, we transform the n-color odd self-inverse compositions in class (C) by subtracting 2 from h, that is, replacing h_{t} by (h − 2)_{t} and subtracting 4 from 2ν + 1 of (2ν + 1)_{u}, 1 ≤ u ≤ 2ν − 3. This transformation also establishes the fact that there are exactly s_{ν−2} elements in class (C).

Finally, we transform the elements in class (D) as follows: Subtract 2_{2} from h_{t} on both ends, that is, replace h_{t} by (h − 2)_{(t−2)}, h > 3, h − 1 ≤ t ≤ h, while replace h_{t} by (h − 2)_{(t−1)} when h = 3, t = 2. We will get those n-color odd self-inverse compositions of 2ν − 3 with h_{t} on both ends, h−1 ≤ t ≤ h except self-inverse odd compositions in one part. We also replace (2ν +1)_{u} by (2ν −3)_{u−4}, 2ν −2 ≤ u ≤ 2ν +1. To get the remaining n-color odd compositions from s_{ν−4} we add 2 to both ends, that is, replace h_{t} by (h + 2)_{t}. For n-color odd self-inverse compositions into one part we add 4 ,that is, replace (2ν − 7)_{t} by (2ν − 3)_{t}, 1 ≤ t ≤ 2ν − 7. We see that the number of n-color odd self-inverse compositions in class (D) is also equal to s_{ν−2}. Hence, we have s_{ν} + s_{ν−4} = s_{ν−1} + 2s_{ν−2} + s_{ν−3}. viz., s_{ν} = s_{ν−1} + 2s_{ν−2} + s_{ν−3} − s_{ν−4}.

(2) From Theorem 8 and Theorem 9, we obtain the recurrence formula of t_{ν} easily. Thus, we complete the proof.

We easily get the following generating functions by the recurrence relations.

Corollary 11.

(1)  ∑_{ν=0}^{∞} s_{ν}q^{ν} = \frac{(1 + q)^{3}}{1 − q − 2q^{2} − q^{3} + q^{4}} .

(2)  ∑_{ν=1}^{∞} t_{ν}q^{ν} = \frac{q + q^{3}}{1 − q − 2q^{2} − q^{3} + q^{4}} .

3 Acknowledgments

The author would like to thank the referee for his/her suggestions and comments which have improved the quality of this paper.

References

[1] A. K. Agarwal and G. E. Andrews, Rogers-Ramanujan identities for partition with ‘n copies of n’, J. Combin. Theory Ser. A 45 (1987), 40–49.

[2] A. K. Agarwal, N-colour compositions, Indian J. Pure Appl. Math. 31 (2000), 1421– 1427.

[3] A. K. Agarwal, An analogue of Euler’s identity and new combinatorial properties of n-colour compositions, J. Comput. Appl. Math. 160 (2003), 9–15.

[4] G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, 1998.

[5] Yu-Hong Guo, Some identities between partitions and compositions, Acta Math. Sinica (Chin. Ser.) 50 (2007), 707–710.

[6] Yu-Hong Guo, N-colour even self-inverse compositions, Proc. Indian Acad. Sci. Math. Sci. 120 (2010), 27–33.

[7] Yu-Hong Guo, Some n-color compositions, J. Integer Sequences 15 (2012), Article 12.1.2.

[8] B. Hopkins, Spotted tilling and n-color compositions, Integers 12B (2012/13), Article A6.

[9] P. A. MacMahon, Combinatory Analysis, AMS Chelsea Publishing, 2001.

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

2010 Mathematics Subject Classification: 05A17. Keywords: n-color odd self-inverse composition, generating function, explicit formula, recurrence formula.

Received November 18 2013; revised versions received May 5 2014; September 16 2014. Published in Journal of Integer Sequences, November 4 2014.

Return to Journal of Integer Sequences home page.