Even and Odd Compositions with Restricted Parts

Jia Huang Department of Mathematics and Statistics University of Nebraska at Kearney Kearney, NE 68849 USA

                        huangj2@unk.edu

Abstract

A result of Legendre asserts that the difference between the numbers of (length) even and odd partitions of n into distinct parts is 0, 1, or −1; this also follows from Euler’s pentagonal number theorem. We establish an analogous result for compositions and obtain some generalizations that are related to various entries in the On-Line Encyclopedia of Integer Sequences.

1 Introduction

A composition of n is a sequence α = (α_{1}, …, α_{ℓ}) of positive integers with size |α| := α_{1}+⋯+α_{ℓ} = n; the parts of α are α_{1}, …, α_{ℓ}, and the length of α is ℓ(α) := ℓ. We often drop parentheses and commas when writing a composition whose parts are single digit numbers. A partition of n is a composition of n whose parts are decreasing. A composition/partition is even (resp., odd) if its length is even (resp., odd). There are 2^{n−1} compositions of n since they correspond to binary sequences of length n − 1. On the other hand, although there are recursive and asymptotic formulae, no closed formula is known for the number of partitions of n.

Compositions and partitions have been extensively studied due to their significance in discrete mathematics, number theory, representation theory, and many other areas. This paper is motivated by the following result of Legendre [8].

Theorem 1 (Legendre). The number of even partitions of n into distinct parts minus the number of odd partitions of n into distinct parts equals (−1)^{j} if n = j(3j ± 1)/2 for some integer j ≥ 0 or 0 otherwise.

For example, there is only one even partition (31) and only one odd partition (4) among all partitions of n = 4 (4, 31, 22, 211, 1111), giving a difference of 0, and there are exactly two even partitions (41, 32) and one odd partition (5) among all partitions of n = 5 = 2(3j − 1) (5, 41, 32, 311, 221, 2111, 11111), giving a difference of 1 = (−1)^{j}, where j = 2.

Although Theorem 1 is often attributed to Legendre, it can be derived from the following result of Euler, which is known as Euler’s pentagonal number theorem since the pentagonal numbers are given by j(3j − 1)/2 for j = 1, 2, . . ..

Theorem 2 (Euler). One has (1 − x)(1 − x^{2})(1 − x^{3}) ⋯ = 1 − x − x^{2} + x^{5} + x^{7} − ⋯, i.e.,

∏_{n=1}^{∞}(1 − x^{n}) = 1 + ∑_{j=1}^{∞}(−1)^{j} (x^{j(3j+1)/2} + x^{j(3j−1)/2}) .

Given the subtle differences between partitions and compositions in not only their definitions and enumerative results as mentioned before but also many other aspects (an algebraic manifestation is given by the representation theory of the 0-Hecke algebra [6] compared with the well-known representation theory of the symmetric group), it is natural to ask for an analogous result of Legendre’s theorem for compositions. However, the number of even compositions of n with distinct parts minus the number of odd compositions of n with distinct parts is given by the sequence 1, −1, −1, 1, 1, 3, −3, −1, −7, −11, 7, 3, 15, 35, 71, −35, 25, −57, …, which does not resemble Legendre’s theorem; see \underline{A339435} in the On-Line Encyclopedia of Integer Sequences (OEIS) [13]. To remedy this, we recall another famous result of Euler.

Theorem 3 (Euler). The number of partitions of n into distinct parts equals the number of partitions of n into odd parts.

The number of even partitions of n into odd parts minus the number of odd partitions of n into odd parts is given by another known sequence \underline{A081360} (1, −1, 1, −2, 2, −3, 4, −5, 6, −8, 10, −12, 15, −18, 22, −27, 32, −38, …). In fact, this is simply a signed version of \underline{A000009}, the number of partitions of n into odd parts, since the length of a partition of n into odd parts has the same parity as n. Nevertheless, Euler’s theorem on partitions of n into distinct/odd parts opens a door for us to think about other related restrictions on the parts of a composition. In particular, the following composition analogue of Euler’s partition theorem comes to our mind.

Theorem 4 (Cayley–Stanley). The number of compositions of n with odd parts equals the number of compositions of n + 1 with parts greater than one.

Cayley [2] showed that the first number in Theorem 4 equals the Fibonacci number F_{n} defined by the recursive relation F_{n} := F_{n−1} + F_{n−2} for n ≥ 2 with initial conditions F_{0} := 1 and F_{1} := 1, and the second number in Theorem 4 also equals F_{n} by Stanley [14]. Recently, Sills [12] provided a bijective proof for Theorem 4. Motivated by Theorem 4, we provide the following extension of Legendre’s theorem to compositions, which involves a periodic sequence 1, 1, 0, −1, −1, 0, … of 0, 1, and −1 with period 6, that is, the sequence \underline{A010892} in the OEIS [13].

Theorem 5. Define b_{n} := c_{n,o}−c_{n,e}, where c_{n,o} (resp., c_{n,e}) is the number of odd (resp., even) compositions of n + 1 with parts greater than one. Then b_{n} = (−1)^{j} if n ∈ {3j + 1, 3j + 2} or b_{n} = 0 otherwise.

We also obtain some generalizations of Theorem 5, which are outlined below; note that we have “odd minus even” instead of “even minus odd” to make the difference as simple as possible in our results.

In Section 2, we establish a result which includes Theorem 5 as a special case. This gives a signed version of an earlier result by Munagi [9, Theorem 1.2] (see also Theorem 7), which generalized Theorem 4 in a similar way as the well-known generalization (Theorem 6) of Euler’s partition theorem due to Glaisher [5].

In Section 3, we provide a composition analogue of an extension (Theorem 9) of Legendre’s theorem obtained recently by Nyirenda [10] using extra congruence restrictions on the parts of a partition. A special case (Corollary 13) of our result resembles Legendre’s Theorem as it involves a periodic sequence whose jth term is (−1)^{j} if n ∈ {3rj + s + 1, 3rj + r + s + 1} for some integer j ≥ 0 or 0 otherwise, where r > s ≥ 0, and this also implies Theorem 5 when (r, s) = (1, 0).

By relaxing the restriction on the parts of a partition, Franklin [4] obtained a further generalization (Theorem 14) of Glaisher’s theorem. In our recent work [7], we obtained an analogous result for compositions, which includes Munagi’s result as a special case. In Section 4, we obtain a signed version of this result together with another variation, giving new interpretations for two entries in the OEIS [13].

Lastly, we ask some questions for future research in Section 5 based on various Legendretype results of Andrews [1] and Nyirenda–Mugwangwavari [11] on partitions with initial repetitions.

2 A signed version of Munagi’s Theorem

First, we recall a well-known result of Glaisher [5], which specializes to Euler’s partition theorem when k = 2.

Theorem 6 (Glaisher). Given an integer k ≥ 1, the number of partitions of n with no part occurring k or more times equals the number of partitions of n with no parts divisible by k.

Similarly, Munagi [9, Theorem 1.2] generalized Theorem 4, the composition analogue of Euler’s theorem, to the following result using the zigzag graphs of compositions.

Theorem 7 (Munagi). The number of compositions of n with parts congruent to 1 modulo k equals the number of compositions of n + k − 1 with parts no less than k.

Now we provide a signed version of Theorem 7 and prove it in two ways, one using a generating function and the other using a bijection.

Theorem 8. For k, n ≥ 1, let b_{k,n} := c_{k,n,o} − c_{k,n,e}, where c_{k,n,o} (resp., c_{k,n,e}) is the number of odd (resp., even) compositions of n + k − 1 with parts no less than k. Then

b_{k,n} = ∑_{0≤j≤(n−1)/k}(−1)^{j}\binom{n − 1 − j(k − 1)}{j}.

Analytic Proof. We have

1 − ∑_{n≥1} b_{k,n}x^{n+k−1} = ∑_{ℓ≥0} (−x^{k} − x^{k+1} − ⋯)^{ℓ} = ∑_{ℓ≥0} \frac{(−x^{k})^{ℓ}}{(1 − x)^{ℓ}}

= (1 − \frac{−x^{k}}{1 − x})^{−1} = \frac{1 − x}{1 − x + x^{k}}

= 1 − x^{k} ∑_{i≥0} (x − x^{k})^{i}

= 1 − ∑_{i≥0} x^{k+i} ∑_{j=0}^{i} \binom{i}{j}(−x^{k−1})^{j}.

For n ≥ 1, extracting the coefficient of x^{n+k−1} gives the desired formula for b_{k,n}.

Combinatorial Proof. There is a bijection from compositions of n + k − 1 with length j + 1 and parts no less than k to compositions of n − j(k − 1) with length j + 1 by subtracting k − 1 from each part of a composition. There are exactly \binom{n−1−j(k−1)}{j} many compositions of n−j(k −1) with length j +1 since each of these compositions can be obtained by inserting j bars between n − j(k − 1) dots with no two bars adjacent to each other. The desired formula for b_{k,n} follows immediately.

Taking k = 2 in Theorem 8 gives Theorem 5, which is a composition analogue of Legendre’s theorem. The sequence b_{k,n} can also be determined by b_{k,n} = 1 for n = 1, …, k and d_{k,n} = b_{k,n−1} − b_{k,n−k} for n > k; this gives \underline{A010892}, \underline{A050935}, and \underline{A099530} when k = 2, k = 3, and k = 4, respectively. Theorem 8 can be viewed as a signed version of Theorem 7 since by either of the above proofs, we can remove (−1)^{j} in the formula of b_{k,n} given by Theorem 8 and recover a closed formula by Munagi [9] for the number a_{k,n} of compositions of n + k − 1 with parts no less than k (the formula of a_{k,n} can also be found in our earlier work [7, Eq. (1)] and for k = 4, in \underline{A003269}).

3 A further restriction by congruence on parts

In this section, we generalize Theorem 8 by further imposing a congruence condition on the already restricted parts of the compositions. This is in the spirit of the following extension (slightly rephrased) of Legendre’s theorem by Nyirenda [10].

Theorem 9 (Nyirenda). Let d_{e}(n, r) (resp., d_{o}(n, r)) denote the number of partitions of n into an even (resp., odd) number of distinct parts, all of which are congruent to 0 or 2r ± 1 modulo 4r. Then

d_{e}(n, r) − d_{o}(n, r) = \begin{cases}(−1)^{j}, & if n = j(2rj ± 1) for some integer j ≥ 0; \\ 0, & otherwise. \end{cases}

Let c_{e}(n, r) (resp., c_{o}(n, r)) denote the number of partitions of n into an even (resp., odd) number of distinct parts, all of which are congruent to 0 or ±r modulo 2r + 1. Then

c_{e}(n, r) − c_{o}(n, r) = \begin{cases}(−1)^{j}, & if n = j((2r + 1)j ± 1))/2 for some integer j ≥ 0; \\ 0, & otherwise. \end{cases}

We provide an analogue of Theorem 9 for compositions with two proofs.

Theorem 10. Given integers k, n ≥ 1 and r > s ≥ 0, let b_{k,n}^{r,s} := c_{k,n,o}^{r,s} − c_{k,n,e}^{r,s}, where c_{k,n,o}^{r,s} (resp., c_{k,n,e}^{r,s}) is the number of odd (resp., even) compositions of n + k − 1 with parts no less than k and congruent to k + s modulo r. Then

b_{k,n}^{r,s} = ∑_{ri+j(k+s)=n−1−s}(−1)^{j}\binom{i + j}{i}.

Analytic Proof. We have

1 − ∑_{n≥1} b_{k,n}^{r,s}x^{n+k−1} = ∑_{ℓ≥0} (−x^{k+s} − x^{k+r+s} − x^{k+2r+s} + ⋯)^{ℓ}

= ∑_{ℓ≥0} \frac{(−x^{k+s})^{ℓ}}{(1 − x^{r})^{ℓ}} = (1 − \frac{−x^{k+s}}{1 − x^{r}} )^{−1}

= \frac{1 − x^{r}}{1 − x^{r} + x^{k+s}} = 1 − x^{k+s} ∑_{i≥0} (x^{r} − x^{k+s})^{i}

= 1 − ∑_{i≥0} x^{k+ri+s} ∑_{j=0}^{i}(−1)^{j}\binom{i}{j}x^{j(k+s−r)}.

Extracting the coefficient of x^{n+k−1} and replacing i with i + j gives the desired formula for b_{k,n}^{r,s}.

Remark 11. The above proof is valid even though the exponent of x^{j(k+s−r)} could be zero (when k = r − s) or negative (when k < r − s). Alternatively, one can deal with the cases k = r − s and k > r − s separately using similar techniques and obtain the same formula for b_{k,n}^{r,s}.

Combinatorial Proof. The allowed parts (no less than k and congruent to k + s modulo r) are k+s, k+r+s, k+2r+s, . . .. Dividing each part minus k+s−r by r gives a bijection from compositions of n + k − 1 with exactly j + 1 parts, each less than k and congruent to k + s, to compositions of i + j + 1 of length j + 1, where r(i + j + 1) + (k + s − r)(j + 1) = n + k − 1, i.e., ri + j(k + s) = n − 1 − s. The number of compositions of i + j + 1 of length j + 1 is \binom{i+j}{j}. Therefore the desired formula for b_{k,n}^{r,s} holds.

Theorem 10 recovers Theorem 8 when (r, s) = (1, 0). The following is another special case as mentioned in Remark 11.

Corollary 12. Suppose r > s ≥ 0 and k = r − s. Then b_{k,n}^{r,s} = 1 if n = s + 1 and b_{k,n}^{r,s} = 0 if n ≠ s + 1.

Proof. This can be derived from the formula of b_{k,n}^{r,s} in Theorem 10 or by using the generating function

\frac{1 − x^{r}}{1 − x^{r} + x^{k+s}} = 1 − x^{r}

in the proof of Theorem 10 when k = r − s.

We give one more corollary of Theorem 10 below, which resembles Legendre’s theorem and recovers Theorem 5 when (k, r, s) = (2, 1, 0).

Corollary 13. Given integers r > s ≥ 0 and k = 2r − s, we have d_{k,n}^{r,s} = (−1)^{j} if n ∈ {3rj + s + 1, 3rj + r + s + 1} for some integer j ≥ 0 or d_{k,n}^{r,s} = 0 otherwise.

Proof. Suppose k = 2r − s. It follows from the proof of Theorem 10 that

1 − ∑_{n≥1} b_{k,n}^{r,s}x^{n+k−1} = \frac{1 − x^{r}}{1 − x^{r} + x^{2r}} = \frac{1 − x^{2r}}{1 + x^{3r}}

= ∑_{i≥0}(−1)^{i}x^{3ri} − ∑_{j≥0}(−1)^{j}x^{2r+3rj}.

Extracting the coefficient of x^{n+k−1} after replacing i with j + 1 for i ≥ 1 gives the desired formula for d_{k,n}^{r,s}.

By Corollary 13, if k = 2r − s then the sequence (d_{k,n}^{r,s} : n ≥ 1) has period 6r and, upon a backward shift of r terms, its generating function becomes (1 − x^{r} + x^{2r})^{−1}. This generating function is the inverse of the 6rth cyclotomic polynomial at least when k + s = 2r = 4, 6, 8; see \underline{A014021}, \underline{A014027}, and \underline{A014033}.

4 A relaxation for restricted parts

The following result of Franklin [4] recovers Glaisher’s theorem (Theorem 6) when m = 0.

Theorem 14 (Franklin). Given integers k ≥ 1 and m ≥ 0, the number of partitions of n with m distinct parts each occurring k or more times equals the number of partitions of n with exactly m distinct parts divisible by k.

In our recent work [7], we obtained a composition analogue of Franklin’s theorem.

Theorem 15 (Huang). For any integers k ≥ 1 and m ≥ 0, the number of compositions of n with exactly m parts not congruent to 1 modulo k, each of which is greater than k, equals the number of compositions of n + k − 1 with exactly m parts less than k, each of which is preceded by a part at least k and followed by either the last part or a part greater than k.

Theorem 15 recovers Munagi’s theorem when m = 0. Our proof for Theorem 15 was based on the bijective proof of Theorem 4 by Sills [12]. We also established two closed formulae [7, Theorem 1.7] for the two equal numbers in Theorem 15:

a_{k,n}^{(m)} = ∑_{\begin{matrix}λ⊆(k−2)^{m} \\ i+(k+1)m+jk+|λ|=n \end{matrix}} \binom{i}{m}\binom{i + j − 1}{j}m_{λ}(1^{m})

= ∑_{i+(k+1)m+jk+ℓ(k−1)+h=n}(−1)^{ℓ}\binom{i}{m}\binom{i + j − 1}{j}\binom{m}{ℓ}\binom{m + h − 1}{h}.

Here λ ⊆ r^{d} means λ is a partition with no more than d parts, each at most r, and m_{λ}(1^{d}) is the specialization of the monomial symmetric function indexed by the partition λ evaluated at the vector (\underbrace{1, …, 1}_{d}), i.e., with m_{i} denoting the number of parts of the partition λ ⊆ r^{d}

that are equal to i for i = 0, 1, …, r,

m_{λ}(1^{d}) = \binom{m}{m_{0}, …, m_{r}} = \frac{m!}{m_{0}! ⋯ m_{r}!}.

Now we provide a signed version of the above formulae of the number a_{k,n}^{(m)}.

Theorem 16. Let b_{k,n}^{(m)} := c_{k,n,o}^{(m)} − c_{k,n,e}^{(m)}, where c_{k,n,o}^{(m)} (resp., c_{k,n,e}^{(m)}) is the numbers of odd (resp., even) compositions of n + k − 1 with exactly m parts less than k, each of which is preceded by a part at least k and followed by either the last part or a part greater than k. Then

b_{k,n}^{(m)} = ∑_{\begin{matrix}λ⊆(k−2)^{m} \\ i+(k+1)m+jk+|λ|=n \end{matrix}}(−1)^{j}\binom{i}{m}\binom{i + j − 1}{j}m_{λ}(1^{m})

= ∑_{i+(k+1)m+jk+ℓ(k−1)+h=n}(−1)^{ℓ+j}\binom{i}{m}\binom{i + j − 1}{j}\binom{m}{ℓ}\binom{m + h − 1}{h}.

Proof. Both the analytic and combinatorial proofs of the above formulae of a_{k,n}^{(m)} given in our previous work [7, Theorem 1.7] were based on the interpretation of a_{k,n}^{(m)} as the number of the first kind of compositions in Theorem 15. However, we can apply the bijective proof of Theorem 15 [7, Theorem 1.6] to the combinatorial proof of the above formulae of a_{k,n}^{(m)} and obtain that the length of each of the second kind of compositions in Theorem 15 is given by 2m + j + 1, where m and j are as in the above formulae of a_{k,n}^{(m)}. Thus we have the desired formulae for b_{k,n}^{(m)}.

Theorem 16 provides a new interpretation for a known sequence \underline{A281862}, which coincides with b_{k,n}^{(m)} when k = m = 2. We also have a variation of b_{k,n}^{(m)} with simplified restrictions on the parts of a composition.

Theorem 17. Let b̄_{k,n}^{(m)} := c̄_{k,n,o}^{(m)}−c̄_{k,n,e}^{(m)}, where c̄_{k,n,o}^{(m)} (resp., c̄_{k,n,e}^{(m)}) is the number of odd (resp., even) compositions of n + k − 1 with exactly m parts less than k. Then

b̄_{k,n}^{(m)} = ∑_{i+j+(k−1)(ℓ+i−m−1)=n}(−1)^{i+ℓ+1}\binom{i + j − 1}{j}\binom{i}{m}\binom{m}{ℓ}

Proof. We have

− ∑_{n≥1−k} b̄_{k,n}^{(m)}x^{n+k−1}y^{m} = ∑_{i≥0} (−y(x + x^{2} + ⋯ + x^{k−1}) − x^{k} − x^{k+1} − ⋯)^{i}

= ∑_{i≥0} (\frac{−xy(1 − x^{k−1})}{1 − x} + \frac{−x^{k}}{1 − x})^{i}

= ∑_{i≥0} (\frac{−xy + x^{k}y − x^{k}}{1 − x} )^{i}

= ∑_{i≥0}(−x)^{i} ∑_{j≥0} \binom{i + j − 1}{j}x^{j} ∑_{m=0}^{i} \binom{i}{m}y^{m}(1 − x^{k−1})^{m}x^{(k−1)(i−m)}

= ∑_{i,j≥0}(−x)^{i}\binom{i + j − 1}{j}x^{j} ∑_{m=0}^{i} \binom{i}{m}y^{m} ∑_{ℓ=0}^{m} \binom{m}{ℓ}(−x^{k−1})^{ℓ}x^{(k−1)(i−m)}.

Extracting the coefficient of x^{n+k−1}y^{m} gives the desired formula for b̄_{k,n}^{(m)}.

We find a sequence \underline{A122918} in the OEIS [13] that coincides with (−1)^{n}b̄_{k,n}^{(m)} when m = 2 and k = 1.

5 Questions

Andrews [1] defined a partition of n to have initial k-repetitions if every part less than j is repeated at least k times whenever a part j is repeated at least k times; taking k = 1 in this definition gives partitions without gaps, which were first studied by Fine [3]. Andrews [1] established the following results on partitions with initial k-repetitions.

• The number of partitions of n with initial k-repetitions equals the number of partitions of n into parts indivisible by 2k and by Glaisher’s theorem, also equals the number of partitions of n with no parts occurring 2k or more times.

• Let D_{e}(m, n) (resp., D_{o}(m, n)) denote the number of partitions of n with initial 2repetitions and with m different parts, of which an even (resp., odd) number have multiplicity one. Then

D_{e}(m, n) − D_{o}(m, n) = \begin{cases}(−1)^{j}, & if m = j, n = j(j + 1)/2, and j ≥ 0; \\ 0, & otherwise. \end{cases}

Since the last result resembles Legendre’s theorem, we ask for a composition analogue, which may require an appropriate definition of compositions with “initial k-repetitions.” If this could be done, it would also be interesting to search for composition analogues of various Legendre-type theorems obtained recently by Nyirenda and Mugwangwavari [11] based on work of Andrews [1].

6 Acknowledgment

The author uses SageMath to help verify the closed formulae obtained in this paper. He thanks the anonymous referee for helpful comments and suggestions.

References

[1] G. E. Andrews, Partitions with initial repetitions, Acta Math. Sin. (Engl. Ser.) 25 (2009), 1437–1442.

[2] A. Cayley, Theorems in trigonometry and on partitions, Messenger of Math. 5 (1876), 164, 188. Reprinted in A. Cayley, Collected Mathematical Papers, Volume 10, p. 16.

[3] N. J. Fine, Basic Hypergeometric Series and Applications, Math. Surveys and Monographs, Vol. 27, Amer. Math. Soc., 1988.

[4] F. Franklin, On partitions, Johns Hopkins Univ. Cir. 2 (1883), 72.

[5] J. W. L. Glaisher, A theorem in partitions, Messenger of Math. 12 (1883), 158–170.

[6] J. Huang, A tableau approach to the representation theory of 0-Hecke algebras, Ann. Comb. 20 (2016), 831–868.

[7] J. Huang, Compositions with restricted parts, Discrete Math. 343 (2020), Paper No. 111875.

[8] A. M. Legendre, Théorie des Nombres, Vol. II, 3rd. ed., 1830. Reprinted by Blanchard, Paris, 1955.

[9] A. O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper No. A60.

[10] D. Nyirenda, On parity and recurrences for certain partition functions, Contrib. Discrete Math. 15 (2020), 72–79.

[11] D. Nyirenda and B. Mugwangwavari, Legendre theorems for a class of partitions with initial repetitions, arXiv preprint arXiv:2212.10756 [math.CO], 2022. Available

    at https://arxiv.org/abs/2212.10756.

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

[13] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, OEIS Foundation

    Inc., https://oeis.org.

[14] R. P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd edition. Cambridge Studies in Advanced Mathematics, Vol. 49, Cambridge University Press, 2012.

2020 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: composition, length, restricted parts.

(Concerned with sequences \underline{A000009}, \underline{A003269}, \underline{A010892}, \underline{A014021}, \underline{A014027}, \underline{A014033}, \underline{A050935}, \underline{A081360}, \underline{A099530}, \underline{A122918}, \underline{A281862}, and \underline{A339435}.)

Received May 14 2024; revised version received July 20 2024. Published in Journal of Integer Sequences, July 20 2024.

Return to Journal of Integer Sequences home page.