Some identities for compositions into parts of size at most 3

Abstract

In this paper, we consider compositions of integers when only parts of size at most 3 are allowed in both composition and its conjugate composition. First we obtain a relation between the number of such compositions and the Fibonacci numbers. Then we provide combinatorial identities between these compositions and compositions into 1’s and 2’s, compositions into odd parts, and compositions into parts greater than 1. Further, several generalized results for these compositions are obtained.

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).$

It is well-known that there are $2^{n-1}$ unrestricted compositions of n [1,2,3,4]. A composition may be represented graphically by means of the MacMahon zig-zag graph [3]. 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 (5, 3, 1, 3, 2) is shown in Figure 1.

The conjugate of a composition is obtained by reading its graph by columns from left to right. Thus the figure gives the conjugate of the composition (5, 3, 1, 3, 2) as (1, 1, 1, 1, 2, 1, 3, 1, 2, 1).

Munagi [5] 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. Now we recall essential terminology and definitions for a composition of n into k parts, say $c=(c_{1},c_{2},\ldots ,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},\ldots ,c_{1})$.

Fig. 1

Zig-zag graph

In 1974, Hoggate-Bicknell studied standard compositions having parts of size $\le 3$, and found the following relation.

Theorem 1.1

[6] Let $C_{3}(n)$ be the number of compositions of a positive integer n with 1, 2 and 3. Then

$$\begin{aligned} C_{3}(n)=T_{n+1}, \end{aligned}$$

where $T_{n}$ is the Tribonacci number with $T_{1}=T_{2}=1, T_{3}=2$, and $T_{n+3}=T_{n+2}+T_{n+1}+T_{n}$.

Hoggatt-Bicknell also obtained the generating function for the number of compositions of n with 1, 2 and 3 as $\frac{1}{1+x+x^2+x^3}$, which generates the Tribonacci sequence.

In this paper, we consider compositions of integers when only parts of size $\le 3$ are allowed in both a composition and its conjugate. For example, $c=(1,1,2,3,2,2)$ is a relevant composition since $c^{'}=(3,2,1,2,2,1)$ and the parts of both compositions do not exceed 3; but (1, 1, 1, 2, 3, 2, 1) is forbidden because the conjugate (4, 2, 1, 2, 2) contains a part greater than 3. In Section 2, we obtain some properties of these compositions. We show that the number of these compositions is equal to $2F_{n}$, where $F_n$ is the $n^{th}$ Fibonacci number. Consequently, we present several identities related to the number of these compositions, the number of compositions into 1’s and 2’s, the number of compositions into odd parts and the number of compositions into parts greater than 1. Further, we obtain several generalized results for these compositions.

2 Main results

We first obtain the following recurrence relation for the number of these composition of n.

Theorem 2.1

Let $CC_{3}(n)$ be the number of compositions c of n into parts $\le 3$ such that the parts of $c'$ also consists of parts $\le 3$. Then

$$\begin{aligned}&CC_{3}(1)=1, ~~CC_{3}(2)=2,~~CC_{3}(3)=4,~~and\\&CC_{3}(n)=CC_{3}(n-1)+CC_{3}(n-2), n>3. \end{aligned}$$

Proof

Because a composition is always paired with its conjugate, we give combinatorial proofs for only compositions of n with first part 1. The proofs for compositions with the first part $> 1$ are similar. We split the relevant compositions of n into two classes.

• (A)   the first part of c is 1, and the second part is greater than 1;

• (B)   the first two parts of c are $``1,1''$.

In Class (A), we delete the first 1 of c to obtain a composition $\beta$. Then we derive the conjugate $\beta ^{'}$ which is a relevant composition of $n-1$ with the first part is 1. And vice versa.

In Class (B), we delete the first two copies of 1 from c to obtain a composition $\gamma$. The conjugate $\gamma ^{'}$ then gives a relevant composition of $n-2$ with the first part is 1. And vice versa.

Here, the relevant composition of 1 is: (1); the relevant compositions of 2 are: (1, 1), (2); the relevant compositions of 3 are: (3), (1, 2), (2, 1), (1, 1, 1).

Thus we complete the proof. $\square$

The following table gives some values of $CC_{3}(n)$.

Table 1 The number of relevant compositions of n with parts $\le 3$

The sequence $CC_{3}(n)$ appears as A128588 in Sloane’s On-Line Encyclopedia of Integer Sequences [7]. Apart from the initial term, the sequence A128588 is double the Fibonacci numbers.

Consequently we obtain the following corollary.

Corollary 2.1

Let $CC_{3}(n)$ be the number of compositions of n in both a composition and its conjugate composition with parts $\le 3$. Then

$$\begin{aligned} CC_{3}(n)=2F_{n},~~~n>1, \end{aligned}$$

where $F_n$ is the $n^{th}$ Fibonacci number.

We also give the following generating function.

Corollary 2.2

$$\begin{aligned} \sum _{n\ge 1}CC_{3}(n)x^n=\frac{x(1+x+x^2)}{1-x-x^2}. \end{aligned}$$

It is well-known that the number of compositions of 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 in line with Corollary 2.1.

Because a composition is always paired with its conjugate, we give combinatorial proofs for only compositions $\alpha$ of n with first part 1. The proofs for compositions with the first part $> 1$ are similar.

Theorem 2.2

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

$$\begin{aligned} CC_{3}(n)=2C_{odd}(n), ~~~n>1. \end{aligned}$$

Proof

We split the relevant compositions $\alpha$ of n into two classes.

• (A)   the first part of $\alpha$ is 1, and the second part is greater than 1;

• (B)   the first two parts of $\alpha$ are “1, 1".

Given any composition $\alpha$ in Class (A), we replace every instance of the string “1,2" by “1,1,1", from left to right to get a composition $\beta$. Then replace each maximal string of the form $1,2,2,\dots$ or $3,2,2,\dots$ in $\beta$ by the sum of its parts. Hence we obtain a composition into odd parts of n with the first part 1.

For example, the composition (1, 2, 2, 3, 2) of 10 produces the composition (1, 1, 3, 5) of 10, and (1, 2, 3, 1, 2, 2, 2, 3, 2) of 18 produces the composition (1, 1, 1, 3, 1, 1, 5, 5) are as follows:

$$\begin{aligned}&(1,2,2,3,2)\longrightarrow (1,1,1,2,3,2)\longrightarrow (1,1,3,5).\\&(1,2,3,1,2,2,2,3,2)\longrightarrow (1,1,1,3,1,1,1,2,2,3,2)\longrightarrow (1,1,1,3,1,1,5,5). \end{aligned}$$

Conversely, for each composition $\gamma$ of n into odd parts with the first part 1. First, replace parts $``\underbrace{1,1,\ldots ,1}_{k\ge 3}"$ by $``{1,2,1,2,\ldots \ldots }"$, from left to right to produce a composition $\delta$, which has at most two consecutive 1’s on the left side of an odd part $>1$. Next, let $h>1$ be an odd part of $\delta$. If the string “1, 1, h" occurs, then replace h with the form $``1,2,\ldots ,2"$, otherwise replace h with the form $3,2,\ldots ,2$. Thus we obtain a composition c. Finally, replace parts “1, 1, 1" by “1, 2" from left to right in c to obtain composition $\delta _1$, which is a relevant composition of n with the first part is 1.

For example, the composition (1, 1, 3, 5) of 10 produces the composition (1, 2, 2, 3, 2) of 10, and (1, 1, 1, 3, 1, 1, 5, 5) of 18 produces the composition (1, 2, 3, 1, 2, 2, 2, 3, 2) of 18 are as follows.

$$\begin{aligned}&(1,1,3,5)\longrightarrow (1,1,1,2,3,2)\longrightarrow (1,2,2,3,2).\\&(1,1,1,3,1,1,5,5)\longrightarrow (1,2,3,1,1,1,2,2,3,2)\longrightarrow (1,2,3,1,2,2,2,3,2). \end{aligned}$$

If $\alpha$ belongs to Class (B), then the first part of the conjugate $\alpha ^{'}$ is 3. For $\alpha ^{'}$, we replace every occurrence of the string “1,2" by “1,1,1", from left to right to get composition $\beta$. Then replace each maximal string of the form $1,2,2,\dots$ or $3,2,2,\dots$ in $\beta$ by the sum of its parts. Hence we obtain a composition into odd parts of n with the first part $>1$.

For example, the composition (1, 1, 2, 3, 2, 2) of 11 produces the composition

(5, 1, 1, 3, 1) of 11 are as follows.

$$\begin{aligned} (1,1,2,3,2,2)\longrightarrow (3,2,1,2,2,1)\longrightarrow (3,2,1,1,1,2,1)\longrightarrow (5,1,1,3,1). \end{aligned}$$

Conversely, for each composition $\gamma$ of n into odd parts with the first part $>1$. First, using the same manner of the inverse mapping in class (A), we obtain a composition $\delta _1$ with the first part is 3. Next, derive the conjugate composition $\delta _1^{'}$. So we obtain a relevant composition.

For example, the composition (3, 1, 1, 1, 1, 1, 3) of 11 produces the composition (1, 1, 3, 3, 2, 1) of 11 are as follows.

$$\begin{aligned}&(3,1,1,1,1,1,3)\longrightarrow (3,1,2,1,1,3)\longrightarrow (3,1,2,1,1,1,2)\longrightarrow (3,1,2,1,2,2)\\&\longrightarrow (1,1,3,3,2,1). \end{aligned}$$

Thus the proof is completed. $\square$

We cite an example to illustrate Theorem 2.2.

Example 2.1

Let $n=6$. The corresponding relations between the relevant compositions of 6 are as follows.

$$\begin{aligned}&(1,2,3)\longleftrightarrow (1,1,1,3)\longleftrightarrow (2,2,1,1), ~~~(1,3,2)\longleftrightarrow (1,5)\longleftrightarrow (2,1,2,1),\\&(1,3,1,1)\longleftrightarrow (1,3,1,1)\longleftrightarrow (2,1,3), ~~~(1,2,2,1)\longleftrightarrow (1,1,3,1)\longleftrightarrow (2,2,2),\\&(1,2,1,2)\longleftrightarrow (1,1,1,1,1,1)\longleftrightarrow (2,3,1), ~(1,1,3,1)\longleftrightarrow (3,1,1,1)\longleftrightarrow (3,1,2),\\&(1,1,2,1,1)\longleftrightarrow (3,3)\longleftrightarrow (3,3),~~~(1,1,2,2)\longleftrightarrow (5,1)\longleftrightarrow (3,2,1). \end{aligned}$$

Theorem 2.3

Let $C_{2}(n)$ be the number of compositions of n into parts of size 1, 2. Then

$$\begin{aligned} CC_{3}(n)=2C_{2}(n-1), ~~~n>1. \end{aligned}$$

Proof

Given any composition $\alpha$ of n when only parts of size $\le 3$ are allowed in both a composition and its conjugate, and the first part is 1, based on the proof of Theorem 2.2 we obtain a composition $\beta$ of n into odd parts. Then replace an odd part $h>1$ by 1, 2, ..., 2 to obtain a composition $\gamma$ of n with parts of size 1, 2 in which the first part is 1. Finally, a composition of $n-1$ is got by deleting the first part 1 of $\gamma$. So we obtain a composition of $n-1$ having 1’s and 2’s.

For example, the composition (1, 2, 2, 3, 2) of 10 produces the composition (1, 1, 2, 1, 2, 2) of 9 are as follows.

$$\begin{aligned} (1,2,2,3,2)\longrightarrow (1,1,1,2,3,2)\longrightarrow (1,1,3,5)\longrightarrow (1,1,1,2,1,2,2) \longrightarrow (1,1,2,1,2,2). \end{aligned}$$

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

Theorem 2.4

Let $C_{>1}(n)$ be the number of compositions of n into parts greater than 1. Then

$$\begin{aligned} CC_{3}(n)=2C_{>1}(n+1), ~~~n>1. \end{aligned}$$

Proof

Given any composition $\alpha$ of n when only parts of size $\le 3$ are allowed in both a composition and its conjugate, and the first part is 1, based on the proof of Theorem 2.2 we get a composition $\beta$ of n into odd parts. Then replace the odd parts of $\beta$ by $1, 2,\cdot \cdot \cdot , 2$ to obtain a composition $\gamma$ of n with parts of size 1, 2. Next, append 1 to the right end of $\gamma$ to obtain a composition $\delta$, which is a composition of $n+1$ into 1’s and 2’s having the first part and last part equal to 1. Finally, we take the conjugate $\beta ^{'}$ which is a composition of $n+1$ into parts greater than 1.

For example, the composition (1, 2, 2, 3, 2) of 10 produces the composition (4, 3, 2, 2) of 11 are as follows.

$$\begin{aligned}&(1,2,2,3,2)\longrightarrow (1,1,1,2,3,2)\longrightarrow (1,1,3,5)\longrightarrow (1,1,1,2,1,2,2)\\&\longrightarrow (1,1,1,2,1,2,2,1)\longrightarrow (4,3,2,2). \end{aligned}$$

This correspondence is clearly one-to-one. The proof is completed. $\square$

We cite an example to illustrate Theorem 2.4.

Example 2.2

Let $n=6$. Then the corresponding relations between the relevant compositions of 6 and 7 are as follows.

$$\begin{aligned}&(1,2,3)\longleftrightarrow (5,2)\longleftrightarrow (2,2,1,1), ~~~(1,3,2)\longleftrightarrow (3,2,2)\longleftrightarrow (2,1,2,1),\\&(1,3,1,1)\longleftrightarrow (3,4)\longleftrightarrow (2,1,3), ~~~(1,2,2,1)\longleftrightarrow (4,3)\longleftrightarrow (2,2,2),\\&(1,2,1,2)\longleftrightarrow (7)\longleftrightarrow (2,3,1), ~(1,1,3,1)\longleftrightarrow (2,5)\longleftrightarrow (3,1,2),\\&(1,1,2,1,1)\longleftrightarrow (2,3,2)\longleftrightarrow (3,3),~~~(1,1,2,2)\longleftrightarrow (2,2,3)\longleftrightarrow (3,2,1). \end{aligned}$$

Further, we obtain the following generalized theorem of Theorem 2.3.

Theorem 2.5

For $k>2$. Let $C_{k}(n)$ be the number of compositions of n using only the parts $\le k$, $CC_{k}(n)$ be the number of compositions of n when only parts of size $\le k$ are allowed in both a composition and its conjugate, respectively. Then

$$\begin{aligned} CC_{k}(n)=2C_{k-1}(n-1), ~~~n>1. \end{aligned}$$

Proof

We present a combinatorial bijective proof for compositions with the first part 1. Let $\alpha$ be a composition of n when only parts of size $\le k$ are allowed in both a composition and its conjugate, and the first part is 1. Then there are at most $k-1$ consecutive 1’s on the left of $\alpha$, and there are at most $k-2$ consecutive 1’s between two parts $>1$. First, we delete the first 1 of $\alpha$ to obtain a composition $\beta$, which is a composition of $n-1$ when parts $\le k$ are allowed in both a composition and its conjugate. Then, we do the following transformation from left to right in $\beta$: if there is one 1 on the left of k, we transform k to “$\underbrace{1,1,\ldots ,1}_{k-2},2$"; if there are two consecutive 1’s on the left of k, we transform k to “$\underbrace{1,1,\ldots ,1}_{k-3},3$", ..., if there are $k-2$ consecutive 1’s on the left of part k, we transform k to “$1,k-1$". Otherwise, we transform k to “$\underbrace{1,1,\ldots ,1}_{k}$". But the rest parts remain the same. In this way, we obtain a composition of $n-1$ using only parts of size $\le k-1$.

Conversely, given a compositions $\gamma$ of $n-1$ using only the parts $\le k-1$, firstly, we replace “$\underbrace{1,1,\ldots ,1}_{r\ge k}$" with “$k,k,\ldots \ldots$", or replace “$\underbrace{1,1,\ldots ,1}_{r= k-1}, h$" with “$\underbrace{1,1,\ldots ,1}_{r= h-1}, k$" (where $1<h<k$), from left to right. But the rest parts remain the same. Thus we obtain a composition $\nu$ of $n-1$, and there are at most $k-2$ 1’s between two parts $>1$. Next append 1 to the left end of $\nu$ to take a composition $\delta$ of n, which is a composition when only parts of size $\le k$ are allowed in both a composition and its conjugate, and the first part is 1.

Thus the proof is completed. $\square$

We cite an example to illustrate Theorem 2.5.

Example 2.3

Let $n=6$ and $k=4$. Then the corresponding relations between the relevant compositions of 6 and 5 are as follows.

$$\begin{aligned}&(1,1,4)\longleftrightarrow (1,1,1,2)\longleftrightarrow (3,1,1,1), ~~~(1,4,1)\longleftrightarrow (1,1,1,1,1)\longleftrightarrow (2,1,1,2),\\&(1,3,1,1)\longleftrightarrow (3,1,1)\longleftrightarrow (2,1,3), ~~~(1,2,2,1)\longleftrightarrow (2,2,1)\longleftrightarrow (2,2,2),\\&(1,2,1,2)\longleftrightarrow (2,1,2)\longleftrightarrow (2,3,1), ~(1,1,3,1)\longleftrightarrow (1,3,1)\longleftrightarrow (3,1,2),\\&(1,1,2,1,1)\longleftrightarrow (1,2,1,1)\longleftrightarrow (3,3),~~~(1,1,2,2)\longleftrightarrow (1,2,2)\longleftrightarrow (3,2,1),\\&(1,1,1,3)\longleftrightarrow (1,1,3)\longleftrightarrow (4,1,1), ~(1,1,1,2,1)\longleftrightarrow (1,1,2,1)\longleftrightarrow (4,2),\\&(1,2,1,1,1)\longleftrightarrow (2,1,1,1)\longleftrightarrow (2,4),~~~(1,2,3)\longleftrightarrow (2,3)\longleftrightarrow (2,2,1,1),\\&(1,3,2)\longleftrightarrow (3,2)\longleftrightarrow (2,1,2,1). \end{aligned}$$

In particular the following corollary holds.

Corollary 2.3

Let $CC_{4}(n)$ be the number of compositions of n in both a composition and its conjugate with parts $\le 4$. Then

$$\begin{aligned} CC_{4}(n)=2C_{3}(n-1),~~~n>1. \end{aligned}$$

From Theorem 1.1, we also obtain the following relation.

Corollary 2.4

Let $CC_{4}(n)$ be the number of compositions of a positive integer n in both a composition and its conjugate with parts $\le 4$. Then

$$\begin{aligned} CC_{4}(n)=2T_{n}, \end{aligned}$$

where $T_{n}$ is the Tribonacci number with $T_{1}=T_{2}=1, T_{3}=2$, and $T_{n+3}=T_{n+2}+T_{n+1}+T_{n}$.

The next result asserts a recurrence relation for $CC_{k}(n)$.

Theorem 2.6

For $k>2$, let $CC_{k}(n)$ be the number of compositions of n when only parts of size $\le k$ are allowed in both a composition and its conjugate. Then

$$\begin{aligned}&CC_{k}(1)=1, ~~CC_{k}(2)=2,~~CC_{k}(3)=4,\ldots , CC_{k}(k)=2^{k-1}~~~~and\\&CC_{k}(n)=CC_{k}(n-1)+CC_{k}(n-2)+\cdots +CC_{k}(n-k+1), ~~~n>k. \end{aligned}$$

Proof

Similar to the proof of Theorem 2.1, we only consider compositions with the first part 1. There are at most k consecutive 1’s on the left end of a relevant composition, so we split the relevant compositions c of n into $k-1$ classes.

$(A_{1})$:

the first part of c is 1, and the second part is greater than 1;

$(A_{2})$:

the first two parts of c are “1, 1", and the third part is greater than 1;                $\cdots \cdots \cdots \cdots$

$(A_{i})$:

the first i parts of c are $``\underbrace{1,1,\ldots ,1}_{i}"$, and the $(i+1)^{th}$ part is greater than 1;                $\cdots \cdots \cdots \cdots$

$(A_{k-1})$:

the first $k-1$ parts of c are $``\underbrace{1,1,\ldots ,1}_{k-1}"$.

In Class $(A_{1})$, we delete the first 1 of c to obtain a composition $\beta$. Then we derive the conjugate $\beta ^{'}$ which is a relevant composition of $n-1$ with the first part 1. And vice versa.

In Class $(A_{2})$, we delete the first two 1’s of c to obtain a composition $\gamma$. Then we derive the conjugate $\gamma ^{'}$ which is a relevant composition of $n-2$ with the first part 1. And vice versa.

Repeating the above transformation in Class $(A_{i})$, where $3\le i\le k-1$, we know that a relevant composition in Class $(A_{i})$ corresponds to a relevant composition of $n-i$ with the first part 1.

These correspondences are obviously reversible. Thus the proof is completed. $\square$

The following generating function may be deduced from Theorem 2.6

Corollary 2.5

$$\begin{aligned} \sum _{n=1}CC_{k}(n)x^n=\frac{x(1+x+x^2+\cdots +x^{k-1})}{1-x-x^2-\cdots -x^{k-1}}. \end{aligned}$$