The Number of Designated Parts in Compositions with Restricted Parts

Mengmeng Liu and Andrew Yezhou Wang School of Mathematical Sciences University of Electronic Science and Technology of China Chengdu 611731 P. R. China

                    dreamofliu@outlook.com
                      yzwang@uestc.edu.cn

Abstract In this paper, we study the number of designated parts in three types of compositions with restricted parts. We find new combinatorial interpretations of some known sequences, and establish two identities concerning these known sequences.

1 Introduction

A composition of an integer n is a way of expressing n as an ordered sum of integers. More precisely, a composition of n is a sequence α = (α_{1}, α_{2}, …, α_{k}) of positive integers satisfying α_{1} + α_{2} + ⋯ + α_{k} = n. The summands α_{i} are called the parts of α, and the number of parts is called the length of α. For example, there are eight compositions of 4; namely,

4, 3 + 1, 1 + 3, 2 + 2, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 1 + 1 + 1 + 1.

If α = (α_{1}, α_{2}, …, α_{k}) is a composition of n with k parts, then we define a (k − 1)-subset S_{α} of [n − 1] := {1, 2, …, n − 1} by

S_{α} = {α_{1}, α_{1} + α_{2}, …, α_{1} + α_{2} + ⋯ + α_{k−1}}.

The correspondence α → S_{α} gives a bijection from all compositions of n with k parts to all (k − 1)-subsets of [n − 1]. Thus, there are \binom{n−1}{k−1} compositions of n with k parts and 2^{n−1} compositions of n. Furthermore, a subset S ⊆ [n − 1] can be encoded by a binary sequence of length n − 1 whose ith component is 1 if i ∈ S and 0 otherwise. Therefore, we have a bijection between compositions of n and binary sequences of length n − 1.

In this paper, we consider the following three types of compositions with restricted parts. Let A(n), B(n), and C(n) denote, respectively, the set of compositions of n in which only the last part may be equal to 1, compositions of n into parts greater than 1, and compositions of n with only odd parts. There is a trivial bijection from the set A(n) to B(n + 1). More precisely, given a composition α ∈ A(n), increasing the last part of α by one, then we obtain a composition β in B(n + 1). We can uniquely recover α from β by decreasing the last part of β by one.

There is a known identity concerning the cardinality of B(n) and C(n). Theorem 1. For n ≥ 1, we have |B(n + 1)| = |C(n)|.

Both numbers in Theorem 1 are equal to the nth Fibonacci number F_{n}, defined by F_{0} = 0, F_{1} = 1, and for n ≥ 2,

F_{n} = F_{n−1} + F_{n−2}.

See Cayley [1] and Stanley [7, Exercise 1.35] for more details. Sills [5] provided a bijective proof of Theorem 1 relying on the binary sequence encoding of compositions. Recently, Li and Wang [4] found a simple bijection defined directly on the parts to prove Theorem 1.

In this paper, we study the number of designated parts among all compositions in A(n), B(n + 1), and C(n) respectively. In Section 2, we find a simple combinatorial interpretation of the sequence \underline{A102702} in the On-Line Encyclopedia of Integer Sequences (OEIS) [6]. The sequence \underline{A102702} was proposed in 2005 by Creighton Dement, stated as a floretion-generated sequence. But there are no further clues about the floretion definition. In Section 3, we give a new combinatorial object counted by the sequence \underline{A006367} and establish an identity relating the sequences \underline{A006367} and \underline{A010049}. In Section 4, we present a relationship concerning the number of three types of designated parts in compositions.

2 Compositions in which only the last part may be one

In this section, we mainly focus on the number of parts not greater than 2 among all compositions in A(n), denoted by \overline{A}_{n}.

It is easy to see that \overline{A}_{0} = 0, \overline{A}_{1} = 1, \overline{A}_{2} = 1, and \overline{A}_{3} = 2. We now present a recurrence relation for \overline{A}_{n}. Theorem 2. For n ≥ 4, we have

\overline{A}_{n} = \overline{A}_{n−1} + \overline{A}_{n−2} + F_{n−4}.  (1)

Proof. Given a composition α, let ℓ_{≤2}(α) count the number of parts less than or equal to 2 of α. Then,

\overline{A}_{n} = ∑_{α∈A(n)} ℓ_{≤2}(α).

Define A_{1}(n) and A_{2}(n) to be the subset of A(n) consisting of the compositions with the first part equal to 2 and greater than 2 respectively. It is clear that

A(n) = A_{1}(n) ∪ A_{2}(n)

is a disjoint set theoretic partitioning of A(n).

For any composition α ∈ A_{1}(n), deleting the first part of α produces a composition in A(n − 2), which gives a bijection ρ between A_{1}(n) and A(n − 2) such that

ℓ_{≤2}(α) = ℓ_{≤2}(ρ(α)) + 1.

Given a composition β ∈ A_{2}(n), we decrease the first part of β by 1 to obtain a composition in A(n − 1), and vice versa. Hence, there is a bijection τ between A_{2}(n) and A(n − 1). Moreover, ℓ_{≤2}(β) = ℓ_{≤2}(τ(β)) if and only if the first part of β is greater than 3. If β has its first part equal to 3, then ℓ_{≤2}(β) = ℓ_{≤2}(τ(β)) − 1. Similarly to the above bijection ρ, we know that such compositions correspond to those in A(n − 3).

Recall that |A(n)| = F_{n} for n ≥ 0. Therefore, we have

∑_{α∈A(n)} ℓ_{≤2}(α) = ∑_{α∈A_{1}(n)} ℓ_{≤2}(α) + ∑_{α∈A_{2}(n)} ℓ_{≤2}(α)

= ∑_{α∈A(n−2)}(ℓ_{≤2}(α) + 1) + ( ∑_{α∈A(n−1)} ℓ_{≤2}(α) − ∑_{α∈A(n−3)} 1)

= ∑_{α∈A(n−2)} ℓ_{≤2}(α) + F_{n−2} + ∑_{α∈A(n−1)} ℓ_{≤2}(α) − F_{n−3}

= ∑_{α∈A(n−2)} ℓ_{≤2}(α) + ∑_{α∈A(n−1)} ℓ_{≤2}(α) + F_{n−4},

which yields the desired result.

We now establish the generating function of \overline{A}_{n}.

Theorem 3. The generating function of \overline{A}_{n} is given by

\overline{A}(x) := ∑_{n≥0} \overline{A}_{n}x^{n} = \frac{x − x^{2} − x^{3} + x^{5}}{(1 − x − x^{2})^{2}} .  (2)

Proof. To find \overline{A}(x), multiply both sides of the recurrence relation (1) by x^{n} and sum over n ≥ 4. Then try to relate these sums to the unknown generating function \overline{A}(x). If we do this first to the left side of (1), we have

∑_{n≥4} \overline{A}_{n}x^{n} = \overline{A}(x) − x − x^{2} − 2x^{3}.

We next deal with the right side of (1). The result is

∑_{n≥4} (\overline{A}_{n−1} + \overline{A}_{n−2} + F_{n−4}) x^{n} = ∑_{n≥4} \overline{A}_{n−1}x^{n} + ∑_{n≥4} \overline{A}_{n−2}x^{n} + ∑_{n≥4} F_{n−4}x^{n}

= x (\overline{A}(x) − x − x^{2}) + x^{2} (\overline{A}(x) − x) + \frac{x^{5}}{1 − x − x^{2}} ,

wherein we have used the familiar generating function for the Fibonacci numbers

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

If we equate the results of operating on the two sides of (1), we find that

\overline{A}(x) − x − x^{2} − 2x^{3} = x (\overline{A}(x) − x − x^{2}) + x^{2} (\overline{A}(x) − x) + \frac{x^{5}}{1 − x − x^{2}} ,

which is trivial to solve for the unknown generating function \overline{A}(x), in the form

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

The proof is complete.

We now seek the relationship between the sequence (\overline{A}_{n})_{n≥0} and the sequence (a_{n})_{n≥0} in OEIS [6, \underline{A102702}]. It is routine to check that

\overline{A}(x) − x − x^{2} = \frac{x − x^{2} − x^{3} + x^{5}}{(1 − x − x^{2})^{2}} − x − x^{2}

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

where the second factor of the last identity above is the generating function of a_{n}. Therefore, a_{n} is the total number of parts not greater than 2 among all compositions of n + 3 in which only the last part may be equal to 1. This is a new and simple combinatorial interpretation of the sequence \underline{A102702}.

We next derive an explicit formula for \overline{A}_{n} in terms of the Fibonacci numbers by expanding \overline{A}(x) in a series.

Theorem 4. For n ≥ 2, we have

\overline{A}_{n} = \frac{(3n − 3)F_{n} − (4n − 10)F_{n−1}}{5} .  (4)

Proof. It follows from (3) that

∑_{n≥0} F_{n+1}x^{n} = \frac{1}{1 − x − x^{2}} .

Therefore, the coefficient P_{n} of x^{n} in 1/(1 − x − x^{2})^{2} is

F_{1}F_{n+1} + F_{2}F_{n} + ⋯ + F_{n+1}F_{1}.

By induction on n and using the fact F_{n} = F_{n−1} + F_{n−2}, it is easy to see that

P_{n} = F_{1}F_{n+1} + F_{2}F_{n} + ⋯ + F_{n+1}F_{1} = \frac{(n + 1)F_{n+2} + (2n + 4)F_{n+1}}{5} ,  (5)

which can be found in [3, Eq. (32.13), p. 375] or [8, Nr. (98), p. 183]. Combining (2) and (5), we conclude that for n ≥ 5,

\overline{A}_{n} = P_{n−1} − P_{n−2} − P_{n−3} + P_{n−5}

= \frac{nF_{n+1} + (2n + 2)F_{n}}{5} − \frac{(n − 1)F_{n} + 2nF_{n−1}}{5}

− \frac{(n − 2)F_{n−1} + (2n − 2)F_{n−2}}{5} + \frac{(n − 4)F_{n−3} + (2n − 6)F_{n−4}}{5}

= \frac{(2n + 3)F_{n} − (2n − 2)F_{n−1} − (2n − 2)F_{n−2} + (n − 4)F_{n−3} + (2n − 6)F_{n−4}}{5}

= \frac{(2n + 3)F_{n} − (2n − 2)F_{n−1} − 4F_{n−2} − (n − 2)F_{n−3}}{5}

= \frac{(2n + 3)F_{n} − (3n − 4)F_{n−1} + (n − 6)F_{n−2}}{5}

= \frac{(3n − 3)F_{n} − (4n − 10)F_{n−1}}{5} .

One can readily check that \overline{A}_{n} for each n = 2, 3, 4 also satisfies the formula (4).

As a consequence, we can express a_{n} in OEIS [6, \underline{A102702}] as

a_{n} = \frac{(3n + 6)F_{n+3} − (4n + 2)F_{n+2}}{5} = \frac{(2n + 10)F_{n+1} − (n − 4)F_{n}}{5}

for n ≥ 0.

To end this section, we consider the number of parts among all compositions in A(n), denoted by A_{n}. Obviously, A_{0} = 0 and A_{1} = 1. Applying arguments similar to those when dealing with \overline{A}_{n}, we can show that for n ≥ 2,

A_{n} = A_{n−1} + A_{n−2} + F_{n−2},

which implies the generating function

A(x) := ∑_{n≥0} A_{n}x^{n} = \frac{x − x^{2}}{(1 − x − x^{2})^{2}} .

Based on A(x), we derive the following simple formula

A_{n} = \frac{(2n + 3)F_{n} − nF_{n−1}}{5} , n ≥ 1.

The number A_{n} appears in OEIS [6, \underline{A010049}], which counts the total number of parts in all compositions of n + 1 with no 1’s.

3 Compositions with no ones

Let B_{n} be the number of parts among all compositions in B(n+1). Since the trivial bijection between A(n) and B(n + 1) preserves the length of compositions, we have B_{n} = A_{n}.

Define \overline{B}_{n} to be the number of parts equal to 2 among all compositions in B(n + 1). It is clear that \overline{B}_{0} = 0, \overline{B}_{1} = 1, \overline{B}_{2} = 0, and \overline{B}_{3} = 2. Using the arguments similar to those in the proof of Theorem 2, we obtain that for n ≥ 4,

\overline{B}_{n} = \overline{B}_{n−1} + \overline{B}_{n−2} + F_{n−4}.

The sequence (\overline{B}_{n})_{n≥0} satisfies the same recurrence relation as (\overline{A}_{n})_{n≥0} but with different initial conditions.

Similarly, we can find that

∑_{n≥0} \overline{B}_{n}x^{n} = \frac{x(1 − x)^{2}}{(1 − x − x^{2})^{2}} ,

and for n ≥ 1,

\overline{B}_{n} = \frac{(3n + 2)F_{n} − 4nF_{n−1}}{5} .

The number \overline{B}_{n} relates to the sequence \underline{A006367} in OEIS [6], which is interpreted as the number of compositions of n containing exactly one 1. We now give a combinatorial proof of this equality.

Theorem 5. The number \overline{B}_{n} equals the number of compositions of n with exactly one 1.

Proof. Assume that α = (α_{1}, α_{2}, …, α_{l}) ∈ B(n + 1) have j parts equal to 2, say

α_{i_{1}} = α_{i_{2}} = ⋯ = α_{i_{j}} = 2,

where 1 ≤ i_{1} < i_{2} < ⋯ < i_{j} ≤ l. For each 1 ≤ r ≤ j, define

α^{r} = (α_{1}, α_{2}, …, α_{i_{r}} − 1, …, α_{l}).

It is easy to see that α^{1}, α^{2}, …, α^{j} are j different compositions of n with exactly one 1.

Conversely, given a composition of n containing only one 1, we increase the unique part equal to 1 by one to obtain a composition counted by \overline{B}_{n}.

We have a new combinatorial interpretation of the sequence (\overline{B}_{n})_{n≥0}.

Theorem 6. The number \overline{B}_{n} counts the number of parts in all compositions of n + 1 with no 1’s and the last part being 2.

Proof. Let α ∈ B(n + 1) in which i (for i ≥ 2) occurs c_{i} times as a part. Then we define the type of α to be the nonnegative sequence (c_{2}, c_{3}, …, c_{n+1}). By the standard combinatorial analysis used to enumerate the permutations of a multiset, we know that there are

\frac{l!}{c_{2}!c_{3}! ⋯ c_{n+1}!}

compositions in B(n + 1) with length l and type (c_{2}, c_{3}, …, c_{n+1}). The part 2 appears

\frac{l!}{c_{2}!c_{3}! ⋯ c_{n+1}!} · c_{2} = \frac{l!}{(c_{2} − 1)!c_{3}! ⋯ c_{n+1}!}

times totally in these compositions.

On the other hand, there are

\frac{(l − 1)!}{(c_{2} − 1)!c_{3}! ⋯ c_{n+1}!}

compositions in B(n + 1) with length l, the last part being 2, and type (c_{2}, c_{3}, …, c_{n+1}). The total number of parts in these compositions is

\frac{(l − 1)!}{(c_{2} − 1)!c_{3}! ⋯ c_{n+1}!} · l = \frac{l!}{(c_{2} − 1)!c_{3}! ⋯ c_{n+1}!}.

The above combinatorial analysis shows the desired equality.

Remark 7. In fact, we can prove the following more general result. For fixed k ≥ 2, the number of appearances of k in all compositions of n with no 1’s is equal to the number of parts in all compositions of n in which each part is at least 2 and the last part is k.

We now give a relationship between B_{n} and \overline{B}_{n}.

Theorem 8. For n ≥ 1, we have

\overline{B}_{n} = B_{n} − B_{n−1}.

Proof. Let α ∈ B(n + 1) with the last part greater than 2. Then we decrease the last part of α by one to produce a composition α′ in B(n). The map α → α′ defines a bijection from the subset of B(n + 1) consisting of compositions with the last part greater than 2 to B(n), which preserves the length.

Hence, the remaining compositions in B(n + 1) have their last part equal to 2. It follows from Theorem 6 that the total number of parts in such compositions is equal to \overline{B}(n).

4 Compositions into odd parts

Let C_{n} be the number of parts among all compositions in C(n). By OEIS [6, \underline{A029907}], we know that

• C_{0} = 0, C_{1} = 1, and C_{n} = C_{n−1} + C_{n−2} + F_{n−1} for n ≥ 2.

• for n ≥ 1,

C_{n} = \frac{(n + 4)F_{n} + 2nF_{n−1}}{5} .

• the number C_{n} equals the number of compositions of n + 1 with exactly one even part.

Recently, Huang [2] found an identity concerning C_{n} and B_{n}.

Theorem 9. For n ≥ 1, we have

C_{n} = B_{n} + B_{n−1}.

Proof. See [2, Proposition 6.3] for a proof.

Let \overline{C}_{n} denote the number of 1’s among all compositions in C(n). The numbers \overline{C}(n) form the sequence \underline{A239342} in OEIS [6]. Applying similar arguments used in Section 2, we can obtain the recurrence relation and an explicit formula satisfied by \overline{C}(n). More precisely, we have

• \overline{C}_{0} = 0, \overline{C}_{1} = 1, \overline{C}_{2} = 2, \overline{C}_{3} = 3, and \overline{C}_{n} = \overline{C}_{n−1} + \overline{C}_{n−2} + F_{n−2} for n ≥ 4.

• for n ≥ 2,

\overline{C}_{n} = \frac{(2n − 2)F_{n} − (n − 10)F_{n−1}}{5} .

Finally, we present an identity involving the number of designated parts in the compositions under study in this paper.

Theorem 10. The number of parts not greater than 2 among all compositions in A(n) equals the difference between the number of parts of compositions in B(n + 1) and the number of parts greater than 1 among the compositions in C(n).

Proof. We first recall the bijection φ introduced by Li and Wang [4] between B(n + 1) and C(n). Given a composition α = (α_{1}, α_{2}, …, α_{l}), define

α̂ = (α_{1}, α_{2}, …, α_{l−1}, α_{l} − 1).

It is clear that α̂ ∈ A(n).

For each even part 2k of α̂, we split it into the pair of parts 1, 2k − 1. Let φ(α) be the yielded composition. Clearly, φ(α) ∈ C(n). Moreover, every odd part of φ(α) which is at least 3 either appears as a part of α̂ or is produced by splitting an even part of α̂. Therefore, every odd part of φ(α) which is at least 3 corresponds to a part of α̂ which is at least 3.

Now we can conclude that the difference between the number of parts of compositions in B(n + 1) and the number of parts greater than 1 among the compositions in C(n) is equal to the number of parts not greater than 2 among all compositions in A(n).

Remark 11. The statement is equivalent to

\overline{A}_{n} = B_{n} − (C_{n} − \overline{C}_{n}),

which can be easily proved by employing the formula of \overline{A}_{n}, B_{n}, C_{n}, and \overline{C}_{n}.

References

[1] A. Cayley, Theorems in trigonometry and on partitions, Messenger Math. 5 (1876), 164– 188.

[2] J. Huang, Compositions with restricted parts, preprint, 2018. Available at https://

   arxiv.org/abs/1812.11010.

[3] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley, 2001.

[4] R. Q. Li and A. Y. Z. Wang, Composition analogues of Beck’s conjectures on partitions, European J. Combin. 81 (2019), 210–220.

[5] A. V. Sills, Compositions, partitions, and Fibonacci numbers, Fibonacci Quart. 49 (2011), 348–354.

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

[7] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 2012.

[8] S. Vajda, Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, Ellis Horwood Limited, 1989.

2010 Mathematics Subject Classification: Primary 05A17; Secondary 05A19. Keywords: composition, designated part, Fibonacci number.

(Concerned with sequence \underline{A006367}, \underline{A010049}, \underline{A029907}, \underline{A102702}, and \underline{A239342}.)

Received July 7 2019; revised version received December 30 2019. Published in Journal of Integer Sequences, December 31 2019.

Return to Journal of Integer Sequences home page.