On the Coefficients of the Distinct Monomials in the Expansion of x_{1}(x_{1} + x_{2}) ⋯ (x_{1} + x_{2} + ⋯ + x_{n})

Sela Fried^{1} Department of Computer Science Ben-Gurion University of the Negev David Ben Gurion Blvd 1 Be’er Sheva Israel

                  friedsela@gmail.com

Abstract

We initiate the study of the coefficients of the distinct monomials in the expansion of the multivariate polynomials x_{1}(x_{1} + x_{2}) ⋯ (x_{1} + x_{2} + ⋯ + x_{n}), n ∈ ℕ, the number of which was shown by Shallit to be counted by the Catalan numbers C_{n}, n ∈ ℕ. In particular, we obtain an exact formula for the coefficients and reduce the complexity of the search for their maximum from the order of C_{n} to the order of the number of partitions of n with distinct parts.

1 Introduction

Let n ∈ ℕ and let x_{1}, …, x_{n} be indeterminates. It is well known that among the multitude of their combinatorial interpretations, the Catalan numbers also count the distinct monomials in the expansion of the multivariate polynomials

p_{n} = x_{1}(x_{1} + x_{2}) ⋯ (x_{1} + x_{2} + ⋯ + x_{n}), n ∈ ℕ,

1The author is a postdoctoral fellow in the Department of Computer Science at the Ben-Gurion University of the Negev and a teaching fellow in the Department of Computer Science at the Israel Academic College in Ramat Gan.

a result that goes back at least to [8]. It seems that despite the naturalness of these polynomials, the coefficients of their distinct monomials have not been studied extensively. In particular, to the best of our knowledge, a closed formula for their maximum is not known. In this work, we initiate the study of these coefficients and accomplish the following: upon establishing several elementary properties including a closed formula for the coefficients (Lemma 4), we show that, for every n ∈ ℕ, a maximal coefficient in the expansion of p_{n} is attained at a monomial belonging to a certain set M_{n} that has the same cardinality as the set of all partitions of n with distinct parts (Theorem 17 and Lemma 18). Finally, we provide an algorithm (Algorithm 1) that successively (and greedily) generates a sequence of monomials (r_{n})_{n∈ℕ} such that r_{n} ∈ M_{n} for every n ∈ ℕ and conjecture that the corresponding coefficients are actually maximal.

Our interest in the polynomials p_{n}, n ∈ ℕ, was triggered during our work [5] on the restrictiveness of stochastic orders in which we established a closed formula ([5, Lemma 3.6]) for the probability that a random probability distribution that is uniformly drawn from the probability n-simplex is greater than a fixed probability distribution, with respect to the usual stochastic order. The formula involves a sum over all distinct monomials of p_{n−1}. Thus, the distinct monomials of p_{n}, n ∈ ℕ, have a direct application in probability theory.

2 Main results

This section consists of two parts: in the first, we establish several elementary properties of the coefficients of p_{n}, n ∈ ℕ, including a closed formula for them and, in the second, we address the problem of finding the maximal coefficients of p_{n}, n ∈ ℕ. Before we begin, let us, for completeness, prove the claim stated in the introduction that the distinct monomials in the expansion of p_{n}, n ∈ ℕ, are counted by the Catalan numbers which have the explicit formula C_{n} = \frac{1}{n+1} \binom{2n}{n} for every n ∈ ℕ_{0} where ℕ_{0} = ℕ ∪ \{0\} (e.g., [9, Theorem 1.4.1]). To simplify formulations throughout this work, whenever we refer to a monomial of p_{n}, we mean a monomial in the expansion of p_{n} after combining like terms. In particular, in our terminology, the monomials of p_{n} are distinct. Likewise, whenever we refer to a coefficient (of a monomial) of p_{n}, we mean the coefficient (of the monomial) after expanding p_{n} and combining like terms. Finally, unless stated otherwise, n ∈ ℕ.

Lemma 1. Let P_{n} denote the set of all monomials of p_{n}. Then |P_{n}| = C_{n}.

Proof. The Catalan numbers have several fundamental interpretations. Thus, it suffices to construct a bijection between P_{n} and a set consisting of the elements in one of these interpretations. Following [9], we shall prove that there is a bijection between P_{n} and the set T_{n} of plane trees with n + 1 vertices (cf. [9, p. 6 and Theorem 1.5.1]). The bijection goes through two auxiliary sets A_{n} and B_{n}.

Let us define

A_{n} = {(a_{1}, …, a_{n}) ∈ ℕ_{0}^{n} | ∑_{i=1}^{n} a_{i} = n and ∑_{i=k+1}^{n} a_{i} ≤ n − k for every 1 ≤ k ≤ n − 1 } .

We shall show that there are two maps Θ: A_{n} → P_{n} and Φ: P_{n} → A_{n} such that Θ∘Φ = id_{P_{n}} and Φ ∘ Θ = id_{A_{n}}. For (a_{1}, …, a_{n}) ∈ A_{n}, let

Θ((a_{1}, …, a_{n})) = x_{1}^{a_{1}} ⋯ x_{n}^{a_{n}}.

The proof that x_{1}^{a_{1}} ⋯ x_{n}^{a_{n}} ∈ P_{n} relies on the following observation: suppose i_{1}, …, i_{n} ∈ {1, …, n} are such that 1 ≤ i_{k} ≤ k for every 1 ≤ k ≤ n. Then x_{i_{1}} ⋯ x_{i_{n}} ∈ P_{n}. We define i_{1}, …, i_{n} as follows: first, if a_{n} = 1 then we set i_{n} = n. Now, suppose we have already defined i_{n+1−∑_{i=k}^{n} a_{i}}, …, i_{n} for some 1 < k ≤ n such that 1 ≤ i_{r} ≤ r for every n+1−∑_{i=k}^{n} a_{i} ≤ r ≤ n. Set i_{n+1−∑_{i=k−1}^{n} a_{i}} = ⋯ = i_{n−∑_{i=k}^{n} a_{i}} = k − 1. Since (a_{1}, …, a_{n}) ∈ A_{n}, we have

∑_{i=k−1}^{n} a_{i} ≤ n + 2 − k ⟺ n + 1 − ∑_{i=k−1}^{n} a_{i} ≥ k − 1.

It follows that 1 ≤ i_{r} ≤ r for n + 1 − ∑_{i=k−1}^{n} a_{i} ≤ r ≤ n.

In the other direction, for x_{1}^{a_{1}} ⋯ x_{n}^{a_{n}} ∈ P_{n} we let Φ(x_{1}^{a_{1}} ⋯ x_{n}^{a_{n}}) = (a_{1}, …, a_{n}). To see that (a_{1}, …, a_{n}) ∈ A_{n}, first notice that a_{n} ≤ 1 = n − (n − 1). Suppose now that we have already shown that ∑_{i=k+1}^{n} a_{i} ≤ n − k for some 1 < k ≤ n − 1. By definition of p_{n}, the indeterminate x_{k} can appear in at most n − k + 1 places, of which ∑_{i=k+1}^{n} a_{i} places are already taken. Thus,

a_{k} ≤ n − k + 1 − ∑_{i=k+1}^{n} a_{i} ⟺ ∑_{i=k}^{n} a_{i} ≤ n − (k − 1).

Now consider the set

B_{n} = {(b_{1}, …, b_{n}) ∈ ℕ_{0} ∪ {−1} | ∑_{i=1}^{n} b_{i} = 0 and ∑_{i=1}^{k} b_{i} ≥ 0 for every 1 ≤ k ≤ n − 1} .

One verifies immediately that the map (a_{1}, …, a_{n}) ↦ (a_{1} − 1, …, a_{n} − 1) gives a bijection between A_{n} and B_{n}.

It remains to show that there is a bijection between B_{n} and T_{n}. By [9, 82 on p. 71], the following procedure provides such a bijection: perform a depth-first search through a plane tree with n + 1 vertices and every time a vertex is encountered for the first time, record one less than its number of children, except that the last vertex is ignored. We prove by induction on n that the resulting sequence belongs to B_{n}: for n = 1, the plane tree has 2 vertices and the corresponding sequence is necessarily (0) which obviously belongs to B_{1}. Suppose that the claim holds for plane trees with n vertices and consider a plane tree T with n + 1 vertices together with the corresponding sequence (b_{1}, …, b_{n}). Deleting the last vertex from T gives a plane tree T′ with n vertices. Let 1 ≤ l ≤ n be the index of the parent of the last vertex of T. We distinguish between two cases:

1. Suppose that l = n. Then T must end with a sequence of three vertices that make a tree of depth two. Thus, b_{n} = 0 and (b_{1}, …, b_{n−1}) is the sequence corresponding to T′. Using the induction hypothesis and putting back b_{n} = 0, we see that (b_{1}, …, b_{n}) ∈ B_{n}.

2. Suppose that l < n. Then the nth vertex of T is a leaf and therefore b_{n} = −1. Now, b_{l} ≥ 0 and (b_{1}, …, b_{l−1}, b_{l}−1, b_{l+1}, …, b_{n−1}) is the sequence corresponding to T′, which, by the induction hypothesis, belongs to B_{n−1}. Putting back b_{n} = −1 and replacing b_{l} − 1 with b_{l}, we obtain the original sequence and conclude that it belongs to B_{n}.

One can show, again by induction, that any (b_{1}, …, b_{n}) ∈ B_{n} induces a unique plane tree with n + 1 vertices. We omit the details.

Remark 2. It follows from the proof of Lemma 1 that we may identify P_{n} with A_{n} and we shall exploit this equivalent representation freely throughout this work. In particular, we shall refer to the elements of A_{n} as ‘monomials’.

2.1 Elementary properties of the coefficients of p_{n}

Our first result is an explicit formula for the coefficients of p_{n}. We shall use the following notation:

Definition 3. For (a_{1}, …, a_{n}) ∈ A_{n}, we denote by c_{(a_{1},...,a_{n})} the corresponding coefficient.

Lemma 4. Let (a_{1}, …, a_{n}) ∈ A_{n}. Then

c_{(a_{1},...,a_{n})} = ∏_{k=1}^{n−1} \frac{n − k + 1 − ∑_{i=k+1}^{n} a_{i}}{a_{k}!} .

Proof. Beginning with a_{n}, we notice that x_{n} can be taken solely from the last term of the product in the definition of p_{n}. Thus, there are \binom{1}{a_{n}} possibilities to do that. Proceeding to a_{n−1}, we notice that x_{n−1} can be taken only from the last two terms of the product, but not from those that contributed x_{n}. This gives \binom{2−a_{n}}{a_{n−1}} possibilities. Continuing so until we reach a_{1}, we conclude that the number of possibilities to obtain (a_{1}, …, a_{n}) is given by

∏_{k=0}^{n−1} \binom{k + 1 − ∑_{i=n−k+1}^{n} a_{i}}{a_{n−k}} = ∏_{k=0}^{n−1} \frac{(k − ∑_{i=n−(k−1)}^{n} a_{i})! (k + 1 − ∑_{i=n−(k−1)}^{n} a_{i})}{a_{n−k}! (k + 1 − ∑_{i=n−k}^{n} a_{i})!}

= ∏_{k=0}^{n−1} \frac{k + 1 − ∑_{i=n−(k−1)}^{n} a_{i}}{a_{n−k}!}

= ∏_{k=1}^{n−1} \frac{n − k + 1 − ∑_{i=k+1}^{n} a_{i}}{a_{k}!} .

It is desirable, when writing down the expansion of the different p_{n}, n ∈ ℕ, to maintain consistency regarding the order of their terms. To this end, we define an ordering on A_{n}. This, of course, induces an ordering of the corresponding coefficients. A reasonable choice is lexicographic and in decreasing order:

Definition 5. Let a = (a_{1}, …, a_{n}), b = (b_{1}, …, b_{n}) ∈ A_{n} such that a ≠ b and let k = min{1 ≤ i ≤ n | a_{i} ≠ b_{i}}. We write a ≺ b if a_{k} > b_{k}.

Example 6. The elements of A_{3} are ordered as follows:

(3, 0, 0) ≺ (2, 1, 0) ≺ (2, 0, 1) ≺ (1, 2, 0) ≺ (1, 1, 1).

Example 7. In the following “triangle”, we present the coefficients of p_{1}, …, p_{5} ordered according to Definition 5 (cf. \underline{A347917} in the On-Line Encyclopedia of Integer Sequences (OEIS):

1

1 1
1 2 1 1 1
1 3 2 1 3 4 2 1 1 1 2 1 1 1
1 4 3 2 1 6 9 6 3 3 4 2 1 1 4 9 6 3 6 8 4 2 2 1 2 1 1 1 1 3 2 1 3 4 2 1 1 1 2 1 1 1.

Example 8. Consider c_{(n,0,...,0)} and c_{(1,...,1)} which are, respectively, the first and the last coefficients of p_{n}. Then

c_{(n,0,...,0)} = c_{(1,...,1)} = 1.

Indeed,

c_{(n,0,...,0)} = \frac{1}{n!} ∏_{k=1}^{n−1} (n − k + 1) = 1 and

c_{(1,...,1)} = ∏_{k=1}^{n−1} (n − k + 1 − (n − k)) = 1.

Lemma 9. The coefficients of p_{n+1} contain (at least) two copies of the coefficients of p_{n}.

Proof. Suppose that n ≥ 2 and let (a_{1}, …, a_{n−1}) ∈ A_{n−1}. Clearly,

(1, a_{1}, …, a_{n−1}), (a_{1}, …, a_{n−1}, 1) ∈ A_{n}.

Now,

c_{(a_{1},...,a_{n−1},1)} = ∏_{k=1}^{n−1} \frac{n − 1 − k + 1 − ∑_{i=k+1}^{n−1} a_{i}}{a_{k}!}

= ∏_{k=1}^{n−2} \frac{n − 1 − k + 1 − ∑_{i=k+1}^{n−1} a_{i}}{a_{k}!}

= c_{(a_{1},...,a_{n−1})},

where in the second equality we used that a_{n−1}! = 1. Similarly,

c_{(1,a_{1},...,a_{n−1})} = \frac{n − 1 + 1 − ∑_{i=1}^{n−1} a_{i}}{1!} ∏_{k=2}^{n−1} \frac{n − k + 1 − ∑_{i=k+1}^{n} a_{i−1}}{a_{k−1}!}

= (n − (n − 1)) ∏_{k=1}^{n−2} \frac{n − 1 − k + 1 − ∑_{i=k+1}^{n−1} a_{i}}{a_{k}!}

= c_{(a_{1},...,a_{n−1})}.

The coefficients of p_{n} sum to n!:

Lemma 10. We have ∑_{(a_{1},...,a_{n})∈A_{n}} c_{(a_{1},...,a_{n})} = n!.

Proof. The assertion follows immediately from specializing (x_{1}, …, x_{n}) ↦ (1, …, 1) in the definition of p_{n}.

In the following lemma, we calculate the sum of the coefficients of the monomials of p_{n} that contain x_{i}. It provides additional interpretation to several known sequences (cf. Table 1).

Lemma 11. Let 1 ≤ i ≤ n. Then

∑_{\begin{matrix}(a_{1},...,a_{n})∈A_{n} \\ a_{i}>0 \end{matrix}} c_{(a_{1},...,a_{n})} = (n − i + 1)(n − 1)!.

Proof. Specializing, f_{n}(x_{i}) := p_{n}(1, …, 1, x_{i}, 1, …, 1) is a (univariate) polynomial in x_{i} whose free coefficient r is the sum of the coefficients corresponding to the monomials that do not contain x_{i}. Thus,

r = f_{n}(0)
= p_{n}(1, …, 1, x_{i}, 1, …, 1)|_{x_{i}=0}
= p_{n}(1, …, 1, 0, 1, …, 1)
= 1 · 2 ⋯ (i − 1)(i − 1)i ⋯ (n − 1)
= (i − 1)(n − 1)!.  (1)

It follows that

∑_{\begin{matrix}(a_{1},...,a_{n})∈A_{n} \\ a_{i}>0 \end{matrix}} c_{(a_{1},...,a_{n})} = ∑_{(a_{1},...,a_{n})∈A_{n}} c_{(a_{1},...,a_{n})} − ∑_{\begin{matrix}(a_{1},...,a_{n})∈A_{n} \\ a_{i}=0 \end{matrix}} c_{(a_{1},...,a_{n})}

= n! − r = (n − i + 1)(n − 1)!,

where the second and third equalities are due to Lemma 10 and (1).

Sequence  OEIS Number
n!  \underline{A000142}
(n − 1)(n − 1)!  \underline{A001563}
(n − 2)(n − 1)!  \underline{A062119}
(n − 3)(n − 1)!  \underline{A052571}

Table 1: Several sequences for which Lemma 11 provides an additional interpretation.

Combining Lemma 1 together with Lemma 10 we immediately obtain the following result.

Corollary 12. The average of the coefficients of p_{n} is \frac{n!}{C_{n}}.

Remark 13. The sequence (\frac{n!}{C_{n}} )_{n∈ℕ} is rational and the sequences of the corresponding numerators and denominators are \underline{A144187} and \underline{A144186} in the OEIS, respectively. Corollary 12 provides an additional interpretation for these sequences that correspond to the denominator and numerator in the series expansion of the EGF for the Catalan numbers, respectively.

In the following lemma, we calculate the sum of the coefficients of p_{n} whose corresponding monomials have x_{i} as a variable with maximal index. This result seems to provides the first interpretation for \underline{A299504} in the OEIS. These monomials were used in the proof of [5, Lemma 3.6].

Lemma 14. Let 1 ≤ i ≤ n. Then

∑_{\begin{matrix}(a_{1},...,a_{n})∈A_{n} \\ a_{i+1}=···=a_{n}=0 \end{matrix}} c_{(a_{1},...,a_{n})} = i!i^{n−i}.

Proof. Clearly,

∑_{\begin{matrix}(a_{1},...,a_{n})∈A_{n} \\ a_{i+1}=···=a_{n}=0 \end{matrix}} = p_{n}(\overbrace{1, …, 1}^{i times}, \overbrace{0, …, 0}^{n−i times}) = i!i^{n−i}.

2.2 The maximal coefficients of p_{n}, n ∈ ℕ

Let m ∈ ℕ. The multinomial theorem (e.g., [3, Theorem 3.9]) states that

(x_{1} + ⋯ + x_{n})^{m} = ∑ \binom{m}{k_{1}, …, k_{n}}x_{1}^{k_{1}} ⋯ x_{n}^{k_{n}},  (2)

where the sum is over all nonnegative integers k_{1}, …, k_{n} such that k_{1} + ⋯ + k_{n} = m. It seems to be folklore that the maximal coefficient on the right-hand side of (2) is obtained whenever r of the k_{1}, …, k_{n} are equal to q + 1 and the rest are equal to q where m = qn + r, q ∈ ℕ_{0} and 0 ≤ r < n. In this section, we address the analogous problem of finding the maximal coefficients of p_{n}, n ∈ ℕ, the sequence of which we denote by (m_{n})_{n∈ℕ} (\underline{A349404} in the OEIS). For example,

(m_{n})_{n∈ℕ} = 1, 1, 2, 4, 9, 27, 96, 384, 1536, …

The quotients of consecutive elements of (m_{n})_{n∈ℕ} exhibit a nontrivial pattern and the induced sequence is denoted by (q_{n})_{n∈ℕ}, i.e., q_{n} = \frac{m_{n+1}}{m_{n}} , n ∈ ℕ. Table 2 lists (m_{n})_{n=1}^{29} and (q_{n})_{n=1}^{28}, which were established by brute force. The last column in the table lists a monomial of p_{n} whose coefficient is m_{n}. Notice that such a monomial is, in general, not unique and in Table 3 we list all other monomials of p_{1}, …, p_{29} whose coefficients are maximal.

The problem of finding a maximal coefficient of p_{n} may be formulated as a combinatorial optimization problem as follows:

maximize ∏_{k=1}^{n−1} \frac{n − k + 1 − ∑_{i=k+1}^{n} a_{i}}{a_{k}!}
subject to (a_{1}, …, a_{n}) ∈ A_{n}.

This problem is intractable already for small values of n since C_{n} is asymptotically \frac{4^{n}}{\sqrt{π}n^{3/2}} (e.g., [2, Problem 12-4]). The following two lemmas reduce the complexity of the problem. More precisely, in Lemma 15, we show that it suffices to perform the search over elements of (a_{1}, …, a_{n}) ∈ A_{n} such that a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{n} and, in Lemma 16, we show that the search may be performed over (a_{1}, …, a_{n}) ∈ A_{n} with consecutive differences bounded by 1, i.e., a_{i} − a_{i+1} ≤ 1 for every 1 ≤ i ≤ n − 1. In Lemma 18, we show that the subset M_{n} of A_{n} consisting of elements that have both properties has the same cardinality as the set of all partitions of n with distinct parts, reducing the complexity of the problem to the order of \frac{3^{3/4}}{12n^{3/4}} e^{π\sqrt{n/3}} (e.g., [4, (50) on p. 48]).

Lemma 15. Let (a_{1}, …, a_{n}) ∈ A_{n} such that a_{i} < a_{i+1} for some 1 ≤ i ≤ n − 1. For every 1 ≤ k ≤ n we define

a′_{k} = \begin{cases}a_{k}, & k ≠ i, i + 1; \\ a_{i+1}, & k = i; \\ a_{i}, & k = i + 1. \end{cases}

Then (a′_{1}, …, a′_{n}) ∈ A_{n} and c_{(a′_{1},...,a′_{n})} > c_{(a_{1},...,a_{n})}.

Proof. Clearly, ∏_{k=1}^{n} a_{k}! = ∏_{k=1}^{n} a′_{k}!. Furthermore, for every k ∈ {1, …, i − 1, i + 1, …, n}, we have

n − k + 1 − ∑_{j=k+1}^{n} a_{j} = n − k + 1 − ∑_{j=k+1}^{n} a′_{j}.

It follows from Lemma 4 that

c_{(a′_{1},...,a′_{n})} > c_{(a_{1},...,a_{n})} ⟺ n − i + 1 − ∑_{j=i+1}^{n} a′_{j} > n − i + 1 − ∑_{j=i+1}^{n} a_{j}

⟺ −a′_{i+1} − ∑_{j=i+2}^{n} a′_{j} > − ∑_{j=i+1}^{n} a_{j}

⟺ a_{i} < a_{i+1}.

Lemma 16. Let (a_{1}, …, a_{n}) ∈ A_{n} such that a_{i} > a_{i+1} + 1 for some 1 ≤ i ≤ n − 1. For every 1 ≤ k ≤ n we define

a′_{k} = \begin{cases}a_{k}, & k ≠ i, i + 1; \\ a_{i} − 1, & k = i; \\ a_{i+1} + 1, & k = i + 1. \end{cases}

Then (a′_{1}, …, a′_{n}) ∈ A_{n} and c_{(a′_{1},...,a′_{n})} ≥ c_{(a_{1},...,A_{n})}. Proof. Arguing as in the proof of Lemma 15, we have

c_{(a′_{1},...,a′_{n})} ≥ c_{(a_{1},...,a_{n})} ⟺ \frac{n − i − ∑_{j=i+1}^{n} a_{j}}{a_{i+1} + 1} ≥ \frac{n − i − ∑_{j=i+1}^{n} a_{j} + 1}{a_{i}}

⟺ n − i − ∑_{j=i+1}^{n} a_{j} ≥ \frac{a_{i+1} + 1}{a_{i} − (a_{i+1} + 1)}

⟺ n − (i − 1) − ∑_{j=i+1}^{n} a_{j} ≥ \frac{a_{i}}{a_{i} − (a_{i+1} + 1)}.

Since a_{i} − (a_{i+1} + 1) ≥ 1, it suffices to show that n − (i − 1) − ∑_{j=i+1}^{n} a_{j} ≥ a_{i} or, equivalently, that ∑_{j=i}^{n} a_{j} ≤ n − (i − 1), which holds true by the definition of A_{n}.

Combining Lemma 15 and Lemma 16, we obtain the following theorem. Theorem 17. A maximal coefficient of p_{n} is attained at a monomial belonging to M_{n}, where

M_{n} = {(a_{1}, …, a_{n}) ∈ A_{n} | a_{i+1} ≤ a_{i} ≤ a_{i+1} + 1 for every 1 ≤ i ≤ n − 1}. Lemma 18.

1. There is a bijection between the set

{(a_{1}, …, a_{n}) ∈ A_{n} | a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{n}} considered in Lemma 15 and the set of all partitions of n. In particular, Lemma 15 reduces the complexity of the problem to the order of \frac{1}{4n\sqrt{3}}e^{π\sqrt{2n/3}}.

2. There is a bijection between M_{n} and the set of all partitions of n with distinct parts. In

particular, Theorem 17 reduces the complexity of the problem to the order of \frac{3^{3/4}}{12n^{3/4}} e^{π\sqrt{n/3}}. Proof. Recall that, by definition (e.g., [1, Definition 1.1]), a partition of n is a nonincreasing sequence a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{r} of r ∈ ℕ natural numbers such that ∑_{i=1}^{r} a_{i} = n. One also writes (a_{1}, …, a_{r}) for such a partition.

1. Let (a_{1}, …, a_{n}) ∈ A_{n} such that a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{n} and let r = max{1 ≤ i ≤ n | a_{i} > 0}. Then (a_{1}, …, a_{r}) is a partition of n. Conversely, let a_{1}, …, a_{r} ∈ ℕ be a partition of n with r ∈ ℕ parts. Extend (a_{1}, …, a_{r}) with n − r zeros to obtain (a_{1}, …, a_{r}, 0, …, 0) ∈ ℕ_{0}^{n}. Let 1 ≤ l ≤ r − 1 and suppose ∑_{i=l+1}^{n} a_{i} > n − l. Since a_{r} ≥ 1, by monotonicity, also a_{1}, …, a_{r−1} ≥ 1. Thus,

n = ∑_{i=1}^{n} a_{i} = ∑_{i=1}^{l} a_{i} + ∑_{i=l+1}^{n} a_{i} > l + n − l = n,

a contradiction. This shows that (a_{1}, …, a_{r}, 0, …, 0) ∈ A_{n}. The claim regarding the complexity is due to [6, 7, 10].

2. Let (a_{1}, …, a_{n}) ∈ M_{n} and let r = max{1 ≤ i ≤ n | a_{i} > 0}. Then (a_{1}, …, a_{r}) is a partition of n such that a_{i} − a_{i+1} ≤ 1 for every 1 ≤ i ≤ r − 1 and a_{r} = 1. This means that each of the numbers 1, 2, …, a_{1} =: m appears as a part in (a_{1}, …, a_{r}). We claim that the conjugate (a′_{1}, …, a′_{m}) of (a_{1}, …, a_{r}) (cf. [1, Definition 1.8]) has distinct parts. To see that, let 1 ≤ i ≤ m and recall that a′_{i} is defined to be the number of parts of (a_{1}, …, a_{r}) that are ≥ i. Suppose a′_{k} = a′_{k+1} for some 1 ≤ k ≤ m − 1. This means that for every 1 ≤ i ≤ r, if a_{i} ≥ k, then also a_{i} ≥ k + 1. Thus, k cannot be a part of (a_{1}, …, a_{r}), a contradiction.

Conversely, let (a′_{1}, …, a′_{m}) be a partition of n with 1 ≤ m ≤ n distinct parts and let (a_{1}, …, a_{r}) be its conjugate, where 1 ≤ r ≤ n. Suppose that a_{i} ≥ a_{i+1} + 2 for some 1 ≤ i ≤ m − 1. Thus, there are distinct 1 ≤ k, l ≤ m such that i ≤ a′_{k} and a′_{l} < i + 1. It follows that a′_{k} = i = a′_{l}, a contradiction. It remains to show that a_{r} = 1. Since the parts of (a′_{1}, …, a′_{m}) are distinct, a′_{1} > a′_{i} for every 2 ≤ i ≤ m. Thus, r = a′_{1} and a_{r} = 1 since a_{r} is the number of parts of (a′_{1}, …, a′_{m}) that are ≥ r.

The claim regarding the complexity may be found, for example, in [4, (50) on p. 48].

Remark 19. The idea of the proof of the second statement in Lemma 18 is due to Grahl and Adams-Watters (see the comments to \underline{A000009} in the OEIS).

Despite the complexity reduction described above, the problem remains intractable. We provide a simple algorithm that for a prescribed l ∈ ℕ successively generates a sequence of monomials (r_{n})_{n=1}^{l} such that r_{n} ∈ A_{n} for every 1 ≤ n ≤ l. In Lemma 20, we show that actually r_{n} ∈ M_{n}. The algorithm also returns a sequence (s_{n})_{n=1}^{l} of the corresponding coefficients. It uses a method Coefficient(·) that upon receiving a monomial of p_{n} as input returns its corresponding coefficient, e.g., by using the formula given by Lemma 4. We applied the algorithm with l = 100 and Table 4 lists the elements of (s_{n})_{n=29}^{100} returned by the algorithm (the first 29 elements of (s_{n})_{n=1}^{100} coincide with (m_{n})_{n=1}^{29} that were already listed in Table 2). We consider the correctness of the first 29 numbers returned by the algorithm and the preservation of the pattern that the elements of (q_{n})_{n=1}^{28} exhibit (this is illustrated in the third column of Table 4) to be a strong indication that the algorithm actually returns the true sequence (m_{n})_{n∈ℕ}. Before we present the pseudocode of the algorithm, let us illustrate by an example its idea: assume that the algorithm arrived at, say, r_{15} = (3, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0). First, a zero is attached at the end of r_{15} and the result is denoted by r′_{16}. Thus, r′_{16} = (3, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0). Now, beginning at the end of r′_{16}, we iterate backwards and every time the value is about to increase, we add 1 at this point (actually, every time is wasteful and we also increase the first entry by 1 if it does not result in a gap of 2 between the first and the second entries). These are the candidates to pick r_{16} from. In our example, these are

(3,3,2,2,1,1,1,1,1,1,0,0,0,0,0,0), (3,3,2,2,2,1,1,1,1,0,0,0,0,0,0,0), (3,3,3,2,1,1,1,1,1,0,0,0,0,0,0,0), (4,3,2,2,1,1,1,1,1,0,0,0,0,0,0,0).

For each of the candidates we calculate the corresponding coefficient. Here, we obtain

370594350, 361267200, 321126400, 48168960.

We take r_{16} to be the monomial with the largest coefficient. In this case,

r_{16} = (3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0).

Now, we repeat the procedure described above with r_{16}.

Lemma 20. Let l ∈ ℕ and let (r_{n})_{n=1}^{l} be the sequence of monomials returned by Algorithm 1. Then r_{n} ∈ M_{n} for every 1 ≤ n ≤ l.

Proof. First notice that for each 2 ≤ n ≤ l the condition in the inner for loop is satisfied at least once. Indeed, if the first two conditions are not satisfied, then the third must be. Now, for n = 1 we have r_{1} = (1) ∈ M_{1}. Assume that r_{n} = (a_{1}, …, a_{n}) ∈ M_{n}. The monomial r_{n+1} is chosen from the set R and therefore it suffices to show that x ∈ M_{n+1} for every x ∈ R. By definition of M_{n}, we have a_{1} ≥ ⋯ ≥ a_{n} and a_{i} − a_{i+1} ≤ 1 for every 1 ≤ i ≤ n − 1. We give the details only in the case that x ∈ R due to i > 1, a_{i} ≠ a_{i−1} and a_{i} = a_{i+1}, the other two cases being similar. Let a_{n+1} = 0 and notice that, necessarily, a_{n} ∈ {0, 1}. Thus, a_{n} ≥ a_{n+1} and a_{n} − a_{n+1} ≤ 1. Conclude that x = (a_{1}, …, a_{i−1}, a_{i} + 1, a_{i+1}, …, a_{n+1}) ∈ A_{n+1}. By the assumptions, a_{i−1} = a_{i} + 1 and a_{i} + 1 − a_{i+1} = 1. Therefore, x ∈ M_{n+1}.

3 Open questions

The following questions remain open and are left for future research:

1. Is there a closed formula for the maximal coefficients (m_{n})_{n∈ℕ}?

2. Prove or disprove: the sequence (s_{n})_{n∈ℕ} returned by Algorithm 1 is equal to (m_{n})_{n∈ℕ}.

Algorithm 1: Generate a sequence of monomials. Input: The length l of the desired sequence Output: A sequence (r_{n})_{n=1}^{l} of monomials and the sequence (s_{n})_{n=1}^{l} of their

corresponding coefficients

r_{1} ← (1) s_{1} ← 1 for n ← 2 to l do

r′_{n} ← r_{n−1} ∪ 0 R ← {} S ← {} for i ← n to 1 do

if (i = n and r′_{n}[n] ≠ r′_{n}[n − 1]) or

(i > 1 and r′_{n}[i] ≠ r′_{n}[i − 1] and r′_{n}[i] = r′_{n}[i + 1]) or (i = 1 and r′_{n}[1] = r′_{n}[2]) then

temp ← r′_{n}

temp[i] ← temp[i] + 1

R ← R ∪ temp

S ← S ∪ Coefficient(temp)

k ← arg max S r_{n} ← R[k] s_{n} ← S[k]

return (r_{n})_{n=1}^{l}, (s_{n})_{n=1}^{l}

3. The sequence (q_{n})_{n∈ℕ} exhibits a nontrivial pattern. In particular, some of its elements are natural. Can we predict for which n ∈ ℕ this happens? Furthermore, certain natural numbers seem to be missing from (q_{n})_{n∈ℕ}. According to the output of Algorithm 1, for n ≤ 200, these numbers are 15, 51, 54 and 73. Is there a characterization for these numbers?

4. For n < 30, the maximal coefficient of p_{n} is not uniquely attained only for n = 2, 5, 6, 12, 13, 14 and 15. Are these the only cases when this happens? If not, can we predict when?

n  m_{n}  q_{n}  (a_{1}, …, a_{n})
1  1  1  (1)
2  1  2  (1, 1)
3  2  2  (2, 1, 0)
4  4  \frac{9}{4}  (2, 1, 1, 0)
5  9  3  (2, 2, 1, 0, 0)
6  27  \frac{32}{9}  (2, 2, 1, 1, 0, 0)
7  96  4  (3, 2, 1, 1, 0, 0, 0)
8  384  4  (3, 2, 1, 1, 1, 0, 0, 0)
9  1536  \frac{625}{128}  (3, 2, 1, 1, 1, 1, 0, 0, 0)
10  7500  5  (3, 2, 2, 1, 1, 1, 0, 0, 0, 0)
11  37500  \frac{648}{125}  (3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0)
12  194400  6  (3, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0)
13  1166400  \frac{16807}{2592}  (3, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0)
14  7563150  7  (3, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0)
15  52942050  \frac{262144}{36015} (3, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0)
16  385351680  8  (4, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0)
17  3082813440  \frac{531441}{65536} (4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0)
18  24998984640  9  (4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0)
19  224990861760  9  (4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0)
20  2024917755840  \frac{5000000}{531441} (4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0)
21  19051200000000  10  (4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
22  190512000000000  \frac{214358881}{21000000} (4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
23  1944663768432000  11  (4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
24  21391301452752000  \frac{214990848}{19487171} (4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
25 235998033739776000  12  (4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
26 2831976404877312000  12  (4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
27 33983716858527744000 \frac{10604499373}{859963392} (4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
28 419064703766444736000  13  (4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
29 5447841148963781568000  (4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

Table 2: The maximal coefficients of p_{n} and their consecutive quotients. The last column lists a monomial of p_{n} whose coefficient is equal to m_{n}.

\begin{matrix}n & (a_{1}, …, a_{n}) \\ 2 & (2, 0) \\ 5 & (3, 1, 1, 0, 0) \\ 6 & (3, 1, 1, 1, 0, 0) \\ 12 & (3, 3, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0), (4, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0) \\ 13 & (4, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0), (3, 3, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0) \\ 14 & (4, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0) \\ 15 & (4, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0) \end{matrix}

Table 3: Additional monomials of p_{n} whose coefficients are equal to m_{n} for n < 30.

n  s_{n}  \frac{s_{n+1}}{s_{n}}
30  5447841148963781568000  \frac{289254654976}{22024729467}
31  71547458245452693504000  14
32  1001664415436337709056000  14
33  14023301816108727926784000  \frac{8649755859375}{578509309952}
34  209673612792393750000000000  \frac{962072674304}{64072265625}
35  3148339635292233982279680000  16
36  50373434164675743716474880000  16
37  805974946634811899463598080000  \frac{582622237229761}{35184372088832}
38  13346235805315454304418995840000  17
39  226886008690362723175122929280000  \frac{46273255257047040}{2638936015687741}
40  3978404225024620607607354163200000  18
41  71611276050443170936932374937600000  \frac{42052983462257059}{2313662762852352}
42  1301601882440198387257545835699200000  19
43  24730435766363769357893370878284800000  19
44  469878279560911617799974046687411200000  \frac{32768000000000000000}{1640066355028025301}
45  9388017391765133721600000000000000000000  20
46  187760347835302674432000000000000000000000  \frac{68122318582951682301}{3276800000000000000}
47  3903402780908908402684872776385162240000000  21
48  81971458399087076456382328304088407040000000  \frac{68440034007706025984}{3243919932521508681}
49  1729429060270920090607276147799029186560000000  22
50  38047439325960241993360075251578642104320000000  22
51  837043665171125323853921655534730126295040000000  \frac{141050039560662968926103}{6159603060693542338560}
52  19167638064180062036564117435227926126077952000000  23
53  440855675476141426840974701010242300899792896000000  \frac{145398897491341278707712}{6132610415680998648961}
54  10452307389872489948744789613053673200242655232000000  24
55  250855377356939758769874950713288156805823725568000000  \frac{582076609134674072265625}{24233149581890213117952}
56  6025508444195271521816253662109375000000000000000000000  25
57  150637711104881788045406341552734375000000000000000000000  \frac{4116767537697256247666432}{162981450557708740234375}
58  3804975577941702545004131009801025732678899466240000000000  26
59  98929365026484266170107406254826669049651386122240000000000  26
60  2572163490688590920422792562625493395290936039178240000000000  \frac{1570042899082081611640534563}{58959020400027837728817152}
61  68495151317539451014974372699807632703067401288427560000000000  27
62  1849369085573565177404308062894806082982819834787544120000000000  \frac{43866262300411718040591269888}{1570042899082081611640534563}
63  51670504955929472544522433459271401555552182671108997120000000000  28
64  1446774138766025231246628136859599243555461114791051919360000000000  \frac{176994576151109753197786640401}{6266608900058816862941609984}
65  40862798295083655283632061806834793855899184040599487771040000000000  29
66  1185021150557426003225329792398209021821076337177385145360160000000000  29
67  34365613366165354093534563979548061632811213778144169215444640000000000  \frac{5230176601500000000000000000000}{176994576151109753197786640401}
68  1015501326834227574804448936477849769406960000000000000000000000000000000  30
69  30465039805026827244133468094335493082208800000000000000000000000000000000  \frac{645590698195138073036733040138561}{20920706406000000000000000000000}
70  940118652620125224647533652879072642271519651664470795263552602800000000000  31
71  29143678231223881964073543239251251910417109201598594653170130686800000000000  \frac{649037107316853453566312041152512}{20825506393391550743120420649631}
72  908277006976838893495396839720732975992938383907565812097329240473600000000000  32
73  29064864223258844591852698871063455231774028285042105987114535695155200000000000  32
74  930075655144283026939286363874030567416768905121347391587665142244966400000000000  \frac{2781855434090103443811378243892171521}{85165837925733364110154508149981184}
75  30379974863093055499068023870097652840716436890381792175415887077743001600000000000  33
76  1002539170482070831469244787713222543743642417382599141788724273565519052800000000000  \frac{2847501839779123940187735784914157568}{84298649517881922539738734663399137}
77  33864506118722234127534503334495450730573121152148488603345499618079355699200000000000  34
78  1151393208036555960336173113372845324839486119173048612513746987014698093772800000000000  \frac{399669593472470313551127910614013671875}{11557507467338797168997280538769227776}
79  39816271517312974256100509002896515744268277555434859054687500000000000000000000000000000  35
80  1393569503105954098963517815101378051049389714440220066914062500000000000000000000000000000  \frac{404140638732382030321569800228268146688}{11419131242070580387175083160400390625}
81  49320570642735368629992208025957484343031663764994032732691353227472207179939840000000000000  36
82  1775540543138473270679719488934469436349139895539785178376888716188999458477834240000000000000  36
83  63919459552985037744469901601640899708569036239432266421567993782803980505202032640000000000000  \frac{59325966985223687799599734398071581327609}{1616562554929528121286279200913072586752}
84  2345769877936484815469854363747603640274357258394513512999736861193926236361921658880000000000000  37
85  86793485483649938172384611458661334690151218560596999980990263864175270745391101378560000000000000  \frac{36807814606597472834439071501847169493876736}{970059730434063003209671332725224505491985}
86  3293280220294377971347467731349401295685328549014404380417498855020965676295207000211456000000000000  38
87  125144648371186362911203773791277249236042484862547366455864956490796695699217866008035328000000000000  \frac{9093778876146525519753713411306280250639479}{237357799848111043775597979581466351239168}
88  4794608647994409038997330943549548574735166856026307562390437024839722999393985472296755584000000000000  39
89  186989737271781952520895906798432394414671507385025994933227043968749196976365433419573467776000000000000  \frac{360287970189639680000000000000000000000000000}{9093778876146525519753713411306280250639479}
90  7408378167700986380828325883329584618472057265089496740817451089920000000000000000000000000000000000000000  40
91  296335126708039455233133035333183384738882290603579869632698043596800000000000000000000000000000000000000000  40
92  11853405068321578209325321413327335389555291624143194785307921743872000000000000000000000000000000000000000000  \frac{58983677299744401560074115672359981890669066761}{1441151880758558720000000000000000000000000000}
93  485137915571417159462028231314994899343248266747019135549714969297846930802852529386687060879513600000000000000  41
94  19890654538428103537943157483914790873073178936627784557538313741211724162916953704854169496060057600000000000000  \frac{11152795537017915251768561543888501580276393855418368}{267188865036464121457189393493879454552305181077725}
95  830260659007146007772745689466656164663688800918177680838519253171995494099296780078316846245644075008000000000000  42
96  34870947678300132326455318957599558915874929638563462595217808633223810752170464763289307542317051150336000000000000  \frac{10093776109231555797740541116805209814919811290249}{237279062189656720523796155594134696283911225344}
97  1483399063252167028338360029439804956347076714866041438488642548695961414227705961250855012767516543942656000000000000  43
98  63786159719843182218549481265911613122924298739239781855011629593926340811791356333786765549003211389534208000000000000  \frac{885182809206724429753029845421970028406525755654144}{20422291197747566381475048306094261718558687959341}
99 2764744244541327539828782867196968086879145195304124286644923210215005242351869797701380142664027856774889472000000000000  44
100 121648746759818411752466446156666595822682388593381468612376621249460230663482271098860726277217225698095136768000000000000

Table 4: s_{30}, …, s_{100} returned by Algorithm 1 and their consecutive quotients. 14

4 Acknowledgments

We thank the anonymous referee for the careful reading of the manuscript and for the helpful suggestions.

References

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

[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2009.

[3] D. DeTemple and W. Webb, Combinatorial Reasoning: An Introduction to the Art of Counting, John Wiley & Sons, 2014.

[4] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[5] S. Fried, On the restrictiveness of the usual stochastic order and the likelihood ratio order, Statist. Probab. Lett. 170 (2021), Article 109012.

[6] G. H. Hardy and S. Ramanujan, Asymptotic formulae in combinatory analysis, Proc. Lond. Math. Soc. 17 (1918), 75–115.

[7] H. Rademacher, On the partition function p(n), Proc. Lond. Math. Soc. 43 (1938), 241–254.

[8] J. O. Shallit, Elementary Problem E2972: Another appearance of the Catalan numbers, Amer. Math. Monthly 93 (1982), 217–218.

[9] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

[10] Y. V. Uspensky, Asymptotic expressions of numerical functions occurring in problems concerning the partition of numbers into summands, Bull. Acad. Sci. de Russie 14 (1920), 199–218.

2010 Mathematics Subject Classification: Primary 05A99; Secondary 11P81, 90C27.

Keywords: Catalan number, combinatorial optimization problem, integer partition, multivariate polynomial.

(Concerned with sequences \underline{A000009}, \underline{A000108}, \underline{A000142}, \underline{A001563}, \underline{A052571}, \underline{A062119}, \underline{A144186}, \underline{A144187}, \underline{A299504}, \underline{A347917} and \underline{A349404}.)

Received November 20 2021; revised versions received November 21 2021; March 28 2022. Published in Journal of Integer Sequences, March 30 2022.

Return to Journal of Integer Sequences home page.