Derivatives and Integrals of Polynomials Associated with Integer Partitions

Madeline Locus Dawsey, Tyler Russell, and Dannie Urban Department of Mathematics University of Texas at Tyler Tyler, TX 75799 USA

                  mdawsey@uttyler.edu
            trussell12@patriots.uttyler.edu
              durban@patriots.uttyler.edu

Abstract

Integer partitions express the different ways that a positive integer may be written as a sum of positive integers. Here we explore the analytic properties of a new polynomial f_{λ}(x) that we call the partition polynomial for the partition λ, with the aim to learn new properties of partitions. We prove a recursive formula for the derivatives of f_{λ}(x) involving Stirling numbers of the second kind, show that the set of integrals from 0 to 1 of a normalized version of f_{λ}(x) is dense in [0, 1/2], pose a few open questions, and formulate a conjecture relating the integral to the length of the partition. We also provide specific examples throughout to support our speculation that an indepth analysis of partition polynomials could further strengthen our understanding of partitions.

1 Introduction and statement of results

A partition λ of a nonnegative integer n is a non-increasing sequence (λ_{1}, λ_{2}, λ_{3}, …) of positive integers, called the parts of the partition, which sum to n. The sum n is called the size of the partition. By convention, the only partition of size n = 0 is the empty partition with no parts. Although partitions are classical objects and simple to define, they are also complex additive structures with elusive analytic properties and are still a significant topic of study in number theory today [1, 2, 5]. Hardy, Rademacher, Ramanujan, and many other well-known number theorists of the twentieth century made major breakthroughs in our understanding of partitions via the generating function of p(n), the partition function [12, \underline{A000041}], which counts the number of partitions of size n. These results include the famous Hardy-Ramanujan asymptotic formula which was proven analytically using the circle method [4]:

p(n) ∼ \frac{1}{4n\sqrt{3}}e^{π\sqrt{\frac{2n}{3}}} as n → ∞;

and the Ramanujan congruences which can be proven using the theory of modular forms [9, 10]:

p(5n + 4) ≡ 0 (mod 5), p(7n + 5) ≡ 0 (mod 7), and p(11n + 6) ≡ 0 (mod 11)

for all integers n ≥ 0. Rademacher’s main contribution was an exact formula for p(n) as an absolutely convergent infinite series involving Kloosterman sums and the I-Bessel function [8]. Most of the discoveries that have been made about partitions so far have resulted from studying p(n).

Recent work by the first author, Just, and Schneider [3] takes a different approach to studying partitions. They define a map from the set of all partitions to the set of natural numbers called the supernorm of a partition, previously called the Heinz number: [12, \underline{A305078}], which sheds more light on properties of partitions by relating them to the multiplicative structure of prime factorizations of integers. For notational convenience, their work utilizes frequency notation λ = ⟨1^{m_{1}}, 2^{m_{2}}, …, k^{m_{k}}⟩, where m_{i} is the multiplicity of the part i in the partition λ and k is the largest part of λ, as opposed to the traditional additive notation. The supernorm of a partition λ = ⟨1^{m_{1}}, 2^{m_{2}}, …, k^{m_{k}}⟩ is defined by

N̂(λ) = ∏_{i=1}^{k} p_{i}^{m_{i}},

where p_{i} denotes the ith prime. In an attempt to further understand the parts of a partition λ and their multiplicities, the length ℓ(λ) (the number of parts), the size |λ|, the norm N(λ) (the product of the parts), and the supernorm N̂(λ), among other partition statistics, Just [6] defined a polynomial to which one can apply calculus and analysis in order to analyze properties of partitions. To define this new polynomial, let λ = ⟨1^{m_{1}}, 2^{m_{2}}, …, k^{m_{k}}⟩ be a partition written in frequency notation. We define the partition polynomial f_{λ} by

f_{λ}(x) = ∑_{i=1}^{k} m_{i}x^{i}.  (1)

Differentiation and integration of the partition polynomial both have the potential to reveal certain properties of partitions. The most basic observations one can make in the direction of differentiation are that f_{λ}(1) = ℓ(λ) and f′_{λ}(1) = |λ|. It is natural to then ask what the higher derivatives of f_{λ} tell us about λ when we evaluate at x = 1. Does f′′_{λ}(1) give some generalization of the size or the length of λ? We first determine what the higher derivatives look like in general, and then we can make some progress toward answering this question by calculating a few specific examples which lead to some open questions.

Theorem 1. Given a partition λ = ⟨1^{m_{1}}, 2^{m_{2}}, …, k^{m_{k}}⟩, the dth derivative of its partition polynomial is

f_{λ}^{(d)}(x) = ∑_{i=1}^{k} i^{d}m_{i}x^{i−d} − ∑_{j=0}^{d−1} \left\{{d \atop j}\right\}x^{j−d}f_{λ}^{(j)}(x)  (2)

for all 0 ≤ d ≤ k, where \left\{{d \atop j}\right\} is the Stirling number of the second kind.

The d = 0 derivative f_{λ}^{(0)} denotes the partition polynomial itself. Note that the second sum is empty when d = 0 and that f_{λ}^{(d)}(x) = 0 for all d > k. For background on Stirling numbers of the second kind, see [13] and [12, \underline{A008277}], for example. We prove Theorem 1 in Section 2 and provide further discussion, examples, and some open questions about derivatives of partition polynomials in Section 3.

In addition to studying derivatives, one may also attempt to understand partitions further by studying integrals. Before taking integrals of partition polynomials, we first normalize them and restrict their domain as follows in order to more easily compare partitions. The normalized partition polynomial f̂_{λ} : [0, 1] → ℝ of the partition λ = ⟨1^{m_{1}}, 2^{m_{2}}, …, k^{m_{k}}⟩ is defined by

f̂_{λ}(x) = \frac{1}{ℓ(λ)} ∑_{i=1}^{k} m_{i}x^{i}.  (3)

It is straightforward to see that the integral of a normalized partition polynomial must have a value between 0 and 1/2 as illustrated in Figure 1 (see Section 4 for more details). Knowing this, it is natural to ask which values in the interval [0, 1/2] can be the integral of a normalized partition polynomial. The following theorem shows that one can find normalized partition polynomials whose integrals take any value in the interval [0, 1/2].

Theorem 2. The integrals of normalized partition polynomials are dense in [0, 1/2].

We provide more basic results on integrals of normalized partition polynomials in Section 4, and we prove Theorem 2 in Section 5. The remaining question is what the value of the integral tells us about the partition, and this question is still open, for the most part.

Question 3. Is there a combinatorial interpretation of ∫_{0}^{1}f̂_{λ}(x) dx?

Question 3 leads to many other related open questions. For example, it is natural to study integrals of all normalized partition polynomials for partitions of fixed size n, but it is still an open problem to obtain a readily accessible combinatorial interpretation of these

Figure 1: Some normalized partition polynomials.

integrals. This turns out to be difficult, but one could obtain results about partitions of large size n which rely on asymptotic results. It would be desirable to prove a result for all partition sizes n that does not rely on asymptotics.

One could also ask whether certain types of partitions of fixed size n generally yield larger or smaller integrals. Some computation indicates that although fewer parts do not always correspond to smaller integrals, this trend may hold on average.

Conjecture 4. Let n ∈ ℕ, and let Avg(n, ℓ) denote the average of all integrals of normalized partition polynomials over all partitions of size n into ℓ parts. Then we expect that

Avg(n, 1) ≤ Avg(n, 2) ≤ ⋯ ≤ Avg(n, n).

Numerical computation confirms that Conjecture 4 holds for n ≤ 50. We partially prove the conjecture by proving the first inequality Avg(n, 1) ≤ Avg(n, 2) for all n and the second inequality Avg(n, 2) ≤ Avg(n, 3) in an asymptotic sense for large values of n.

Theorem 5. Let n ∈ ℕ. Then Avg(n, 1) ≤ Avg(n, 2).

Note that Avg(n, ℓ) may be computed by averaging all of the integrals for partitions of size n with ℓ parts, but alternatively it may be computed by evaluating the integral of the sum of all partitions of size n with ℓ parts (see Section 4.2 for more details). Instead of considering each individual integral, we can evaluate a single integral involving all of the parts. Although this method uses and produces the same information, it simplifies the estimation. The larger, combined partition has length ℓ times the number of partitions of size n into ℓ parts.

The proof of Theorem 5 requires one to know the exact form of all partitions of size n and length ℓ when ℓ = 1 and ℓ = 2. This is a difficult problem in general, so we instead rely on asymptotic approximations for the second inequality. For this reason, the result is only guaranteed for sufficiently large n.

Theorem 6. For sufficiently large n, Avg(n, 2) ≤ Avg(n, 3).

Proving Conjecture 4 in general seems difficult. More progress could possibly be made in an asymptotic sense using the same method as the proof of Theorem 6. To fully generalize these results, one may need to find a general formula for the number of parts of size i among all partitions of size n, or among all partitions of size n and length ℓ.

We prove Theorems 5 and 6 in Section 6.

2 Proof of Theorem 1

Let λ = ⟨1^{m_{1}}, 2^{m_{2}}, …, k^{m_{k}}⟩. We will prove the derivative formula (2) for f_{λ} by induction. First note that when d = 0, (2) is trivially true. When d = 1, we have that

f_{λ}^{(1)}(x) = ∑_{i=1}^{k} im_{i}x^{i−1},

which satisfies (2) since \left\{{d \atop 0}\right\} = 0. Next, when d = 2, we have that

f_{λ}^{(2)}(x) = ∑_{i=2}^{k} i(i − 1)m_{i}x^{i−2}

= ∑_{i=2}^{k} i^{2}m_{i}x^{i−2} − ∑_{i=2}^{k} im_{i}x^{i−2}.

Adding and subtracting 1m_{1}x^{−1}, we have

f_{λ}^{(2)}(x) = ∑_{i=2}^{k} i^{2}m_{i}x^{i−2} − ∑_{i=1}^{k} im_{i}x^{i−2} + 1m_{1}x^{−1},

which yields the following when 1m_{1}x^{−1} is absorbed into the first sum:

f_{λ}^{(2)}(x) = ∑_{i=1}^{k} i^{2}m_{i}x^{i−2} − x^{−1} ∑_{i=1}^{k} im_{i}x^{i−1}.

The second sum above contains the first derivative f_{λ}^{(1)}(x), so we have that

f_{λ}^{(2)}(x) = ∑_{i=1}^{k} i^{2}m_{i}x^{i−2} − x^{−1}f_{λ}^{(1)}(x),

which also satisfies (2). Now, let N ∈ ℕ and suppose (2) holds for d = N. We rewrite the Nth derivative as follows:

f_{λ}^{(N)}(x) = ∑_{i=N}^{k} i^{N}m_{i}x^{i−N} + ∑_{i=1}^{N−1} i^{N}m_{i}x^{−(N−i)} − ∑_{j=0}^{N−1} \left\{{N \atop j}\right\}x^{j−N}f_{λ}^{(j)}(x) .  (4)

We take the derivative to obtain

f_{λ}^{(N+1)}(x) = ∑_{i=N+1}^{k} i^{N}(i − N)m_{i}x^{i−N−1} − ∑_{i=1}^{N−1} i^{N}(N − i)m_{i}x^{−(N−i)−1}

− ∑_{j=0}^{N−1} \left\{{N \atop j}\right\}(j − N)x^{j−N−1}f_{λ}^{(j)}(x) − ∑_{j=0}^{N−1} \left\{{N \atop j}\right\}x^{j−N}f_{λ}^{(j+1)}(x). (5)

We use (4) to rewrite the first sum in (5) as

∑_{i=N+1}^{k} i^{N}(i − N)m_{i}x^{i−N−1} = ∑_{i=N+1}^{k} i^{N+1}m_{i}x^{i−(N+1)} − Nx^{−1}f_{λ}^{(N)}(x) + N ∑_{i=1}^{N−1} i^{N}m_{i}x^{−(N−i)−1}

− N ∑_{j=0}^{N−1} \left\{{N \atop j}\right\}x^{j−N−1}f_{λ}^{(j)}(x) + N^{N+1}m_{N}x^{−1} .  (6)

Distributing in the second and third sums of (5), we have that

− ∑_{i=1}^{N−1} i^{N}(N − i)m_{i}x^{−(N−i)−1} = −N ∑_{i=1}^{N−1} i^{N}m_{i}x^{−N+i−1} + ∑_{i=1}^{N−1} i^{N+1}m_{i}x^{−N+i−1}  (7)

and

− ∑_{j=0}^{N−1} \left\{{N \atop j}\right\}(j − N)x^{j−N−1}f_{λ}^{(j)}(x) = N ∑_{j=0}^{N−1} \left\{{N \atop j}\right\}x^{−N+j−1}f_{λ}^{(j)}(x)

− ∑_{j=0}^{N−1} j\left\{{N \atop j}\right\}x^{−N+j−1}f_{λ}^{(j)}(x).  (8)

Shifting the indices of the fourth sum of (5), we have that

− ∑_{j=0}^{N−1} \left\{{N \atop j}\right\}x^{j−N}f_{λ}^{(j+1)}(x) = − ∑_{j=1}^{(N−1)+1} \left\{{N \atop j − 1}\right\}x^{−N+j−1}f_{λ}^{(j)}(x).  (9)

Putting together (6), (7), (8), and (9), rearranging, and using the fact that \left\{{N \atop N}\right\} = 1, we then have that

f_{λ}^{(N+1)}(x) = ∑_{i=N+1}^{k} i^{N+1}m_{i}x^{i−(N+1)} + (N^{N+1}m_{N}x^{−1} + ∑_{i=1}^{N−1} i^{N+1}m_{i}x^{−(N+1−i)})

+ (−N\left\{{N \atop N}\right\}x^{−1}f_{λ}^{(N)}(x) − ∑_{j=0}^{N−1} j\left\{{N \atop j}\right\}x^{j−N−1}f_{λ}^{(j)}(x))

+ (N ∑_{i=1}^{N−1} i^{N}m_{i}x^{−(N+1−i)} − N ∑_{j=0}^{N−1} \left\{{N \atop j}\right\}x^{j−N−1}f_{λ}^{(j)}(x)

− N ∑_{i=1}^{N−1} i^{N}m_{i}x^{−(N+1−i)} + N ∑_{j=0}^{N−1} \left\{{N \atop j}\right\}x^{j−N−1}f_{λ}^{(j)}(x))

− ∑_{j=1}^{(N+1)−1} \left\{{N \atop j − 1}\right\}x^{j−N−1}f_{λ}^{(j)}(x) .

Combining the terms in the grouped expressions above, we obtain

f_{λ}^{(N+1)}(x) = ∑_{i=N+1}^{k} i^{N+1}m_{i}x^{i−(N+1)} + ∑_{i=1}^{(N+1)−1} i^{N+1}m_{i}x^{i−(N+1)}

− ∑_{j=0}^{(N+1)−1} j\left\{{N \atop j}\right\}x^{j−N−1}f_{λ}^{(j)}(x) − ∑_{j=1}^{(N+1)−1} \left\{{N \atop j − 1}\right\}x^{j−N−1}f_{λ}^{(j)}(x). (10)

Notice that the third sum in (10) can be rewritten as the sum from j = 1 to (N + 1) − 1, since the j = 0 term is zero. We combine the first two sums and the last two sums as follows:

f_{λ}^{(N+1)}(x) = ∑_{i=1}^{k} i^{N+1}m_{i}x^{i−(N+1)} − ∑_{j=1}^{(N+1)−1} (j\left\{{N \atop j}\right\} + \left\{{N \atop j − 1}\right\}) x^{j−N−1}f_{λ}^{(j)}(x)

= ∑_{i=1}^{k} i^{N+1}m_{i}x^{i−(N+1)} − ∑_{j=1}^{(N+1)−1} \left\{{N + 1 \atop j}\right\}x^{j−(N+1)}f_{λ}^{(j)}(x),

where this last equality uses a classical recurrence relation for Stirling numbers of the second kind [13]. Notice again that the last sum can be rewritten as the sum from j = 0 to (N + 1) − 1, since the j = 0 term includes \left\{{N+1 \atop 0}\right\} = 0. This completes the proof of Theorem 1.

3 Derivatives of partition polynomials

There are many open questions that arise when studying the derivatives of partition polynomials. It is clear that f_{λ}^{(d)}(1) ≥ 0 for all d ≥ 0, since all of the parts of partitions are positive and all of their multiplicities are nonnegative. It is also clear that evaluating the first few derivatives at x = 1 yields

f_{λ}^{(0)}(1) = ℓ(λ),
f_{λ}^{(1)}(1) = |λ|,
f_{λ}^{(2)}(1) = ∑_{i=1}^{k} i^{2}m_{i} − \left\{{2 \atop 1}\right\}|λ|,

f_{λ}^{(3)}(1) = ∑_{i=1}^{k} i^{3}m_{i} − \left\{{3 \atop 2}\right\} ∑_{i=1}^{k} i^{2}m_{i} − (\left\{{3 \atop 1}\right\} − \left\{{3 \atop 2}\right\}\left\{{2 \atop 1}\right\}) |λ|,

f_{λ}^{(4)}(1) = ∑_{i=1}^{k} i^{4}m_{i} − \left\{{4 \atop 3}\right\} ∑_{i=1}^{k} i^{3}m_{i} − (\left\{{4 \atop 2}\right\} − \left\{{4 \atop 3}\right\}\left\{{3 \atop 2}\right\}) ∑_{i=1}^{k} i^{2}m_{i}

− (\left\{{4 \atop 1}\right\} − \left\{{4 \atop 2}\right\}\left\{{2 \atop 1}\right\} − \left\{{4 \atop 3}\right\}\left\{{3 \atop 1}\right\} + \left\{{4 \atop 3}\right\}\left\{{3 \atop 2}\right\}\left\{{2 \atop 1}\right\}) |λ|.

It would be nice to find a combinatorial interpretation of the dth derivative of the partition polynomial at x = 1. As a result, properties of the derivatives could potentially provide new information about the partition. A good start would be to find an explicit formula for f_{λ}^{(d)}(1) for all 0 ≤ d ≤ k that is more enlightening than simply plugging x = 1 into (2). It may be helpful to consider kth moments of partitions, defined by Zemel [14] as

p_{k}(λ) := ∑_{i≥1} i^{k}m_{i},

as these moments appear in the higher derivatives of f_{λ}.

Question 7. Is there a nice combinatorial interpretation of f_{λ}^{(d)}(1)?

We now provide an explicit example of the derivatives of the partition polynomials for two specific partitions of the same length and size.

Example 8. Let λ_{1} = ⟨1^{1}, 2^{2}, 3^{0}, 4^{0}, 5^{1}⟩ and λ_{2} = ⟨1^{1}, 2^{1}, 3^{1}, 4^{1}⟩. Here are the partition polynomial, its derivatives, and their evaluations at x = 1 for λ_{1}:

\begin{aligned}f_{λ_{1}}^{(0)}(x) & = x^{5} + 2x^{2} + x \\ f_{λ_{1}}^{(1)}(x) & = 5x^{4} + 4x + 1 \\ f_{λ_{1}}^{(2)}(x) & = 20x^{3} + 4 \\ f_{λ_{1}}^{(3)}(x) & = 60x^{2} \\ f_{λ_{1}}^{(4)}(x) & = 120x \\ f_{λ_{1}}^{(5)}(x) & = 120 \end{aligned}  \begin{aligned}f_{λ_{1}}^{(0)}(1) & = 4 \\ f_{λ_{1}}^{(1)}(1) & = 10 \\ f_{λ_{1}}^{(2)}(1) & = 24 \\ f_{λ_{1}}^{(3)}(1) & = 60 \\ f_{λ_{1}}^{(4)}(1) & = 120 \\ f_{λ_{1}}^{(5)}(1) & = 120 \end{aligned}

Here are the partition polynomial, its derivatives, and their evaluations at x = 1 for λ_{2}:

\begin{aligned}f_{λ_{2}}^{(0)}(x) & = x^{4} + x^{3} + x^{2} + x \\ f_{λ_{2}}^{(1)}(x) & = 4x^{3} + 3x^{2} + 2x + 1 \\ f_{λ_{2}}^{(2)}(x) & = 12x^{2} + 6x + 2 \\ f_{λ_{2}}^{(3)}(x) & = 24x + 6 \\ f_{λ_{2}}^{(4)}(x) & = 24 \end{aligned}  \begin{aligned}f_{λ_{2}}^{(0)}(1) & = 4 \\ f_{λ_{2}}^{(1)}(1) & = 10 \\ f_{λ_{2}}^{(2)}(1) & = 20 \\ f_{λ_{2}}^{(3)}(1) & = 30 \\ f_{λ_{2}}^{(4)}(1) & = 24 \end{aligned}

Although λ_{1} and λ_{2} share the same length ℓ(λ_{1}) = ℓ(λ_{2}) = 4 and the same size |λ_{1}| = |λ_{2}| = 10, the evaluations of their partition polynomial derivatives at x = 1 yield different numbers starting at the second derivative.

Obviously the evaluation of the partition polynomial at x = 1 can distinguish any two partitions of different lengths, and the evaluation of its first derivative can distinguish any two partitions of the same length and different sizes. A natural open question that arises from Example 8 is whether the evaluation of its second derivative, or third derivative, or dth derivative for some positive integer d, can distinguish any two unequal partitions, even if they have the same length and size. Answering this question could possibly shed more light on a combinatorial interpretation of the higher derivatives, or vice versa. For the following question, let lg(λ) denote the largest part of the partition λ, and recall that f_{λ}^{(d)}(x) = 0 for all d > lg(λ).

Question 9. If λ, λ′ are any two unequal partitions, is it true that f_{λ}^{(d)}(1) ≠ f_{λ′}^{(d)}(1) for some positive integer d ≤ min{lg(λ), lg(λ′)}?

One specific direction in which to investigate Question 9 is to search for a counterexample for a fixed positive integer d: a pair of unequal partitions λ, λ′ for which f_{λ}^{(r)}(1) = f_{λ′}^{(r)}(1) for all r ≤ d. We provide a partial answer to this question: the second derivative evaluation does not necessarily distinguish two unequal partitions of the same length and size.

Proposition 10. There exists a positive integer N such that if n ≥ N, then there are two unequal partitions λ_{1}, λ_{2} with ℓ(λ_{1}) = ℓ(λ_{2}) and |λ_{1}| = |λ_{2}| = n such that f_{λ_{1}}^{(2)}(1) = f_{λ_{2}}^{(2)}(1).

Proof. We use the pigeonhole principle to prove the proposition. Denote the number of partitions of n into s parts by p(n, s). It can be shown [7] that

p(n, s) ∼ \frac{n^{s−1}}{s((s − 1)!)^{2}}

as n → ∞ for s = O(1). In particular, we have that p(n, 5) ∼ n^{4}/2880. It suffices to show that f_{λ}^{(2)}(1) is bounded by an asymptotically smaller expression. Suppose λ = ⟨1^{m_{1}}, 2^{m_{2}}, …, k^{m_{k}}⟩ is a partition of size n and length 5. Then we have that

f_{λ}^{(2)}(1) = ∑_{i=1}^{k} i^{2}m_{i} − n ≤ k^{2}n − n ≤ n^{3} − n.

Since (n^{3} − n)/p(n, 5) → 0 as n → ∞, there must be two unequal partitions of the same size and length 5 with equal second derivative evaluations.

In fact, this argument holds for all s ≥ 5, so the second derivative evaluation fails to distinguish unequal partitions of the same size and length at least 5. One could also refine the question to ask how many derivatives are necessary in order to distinguish any two unequal partitions of fixed size n and length s.

Another interesting observation is that taking the derivative of the partition polynomial of one partition yields the partition polynomial of a different partition. Explicitly, if we define the partition λ = λ^{(0)} = ⟨1^{m_{1}}, 2^{m_{2}}, …, k^{m_{k}}⟩, then f_{λ}^{(1)}(x) is the partition polynomial of the new partition λ^{(1)} defined by λ^{(1)} = ⟨1^{2m_{2}}, 2^{3m_{3}}, …, (k − 1)^{km_{k}}⟩. Continuing in this way, we obtain the following (finite) sequence of partitions (λ^{(d)})_{0≤d<k} whose partition polynomials are related by differentiation:

λ^{(d)} = ⟨1^{(d+1)!m_{d+1}/1!}, 2^{(d+2)!m_{d+2}/2!}, …, (k − d)^{k!m_{k}/(k−d)!}⟩ for all 0 ≤ d < k. (11)

Strictly speaking, these partitions also have parts of size zero which we exclude, and parts of negative size which occur with multiplicity zero. We have that for all 0 ≤ d < k,

ℓ (λ^{(d)}) = ∑_{i=d+1}^{k} \frac{i!}{(i − d)!}m_{i}  and  |λ^{(d)}| = ∑_{i=d+1}^{k} \frac{i!}{(i − d − 1)!}m_{i}.  (12)

Therefore, the process of differentiation guarantees that the following relationship between the sizes and lengths of the partitions in the sequence (11) holds for all 1 ≤ d ≤ k:

|λ^{(d−1)}| = ℓ (λ^{(d)}) + d!m_{d},  (13)

where ℓ (λ^{(k)}) = 0 since λ^{(k)} is the empty partition.

Example 11. Let λ = ⟨1^{1}, 2^{0}, 3^{3}, 4^{1}⟩. Then we have

λ^{(0)} = ⟨1^{1}, 2^{0}, 3^{3}, 4^{1}⟩,
λ^{(1)} = ⟨1^{0}, 2^{9}, 3^{4}⟩,
λ^{(2)} = ⟨1^{18}, 2^{12}⟩,
λ^{(3)} = ⟨1^{24}⟩.

We also see that ℓ (λ^{(0)}) = 5, |λ^{(3)}| = 4!m_{4} = 24, and

|λ^{(0)}| = ℓ (λ^{(1)}) + 1!m_{1} = 14,
|λ^{(1)}| = ℓ (λ^{(2)}) + 2!m_{2} = 30,
|λ^{(2)}| = ℓ (λ^{(3)}) + 3!m_{3} = 42.

It would be interesting to investigate other relationships among partitions in the sequence (11) which are related by differentiation of partition polynomials, such as patterns in the sequence of lengths or the sequence of sizes from (12) or (13), the zeros of the polynomials, relationships among the polynomials associated with other sequences of partitions, etc.

4 Integrals of normalized partition polynomials

As Figure 1 suggests, there are a few properties that all normalized partition polynomials have in common. Namely, they all start at the point (0, 0), end at the point (1, 1), and are bounded above by the line y = x. In the following proposition, recall that normalized partition polynomials are defined as functions from [0, 1] to ℝ.

Proposition 12. Let f̂_{λ}(x) be a normalized partition polynomial. Then following properties hold.

1. f̂_{λ}(0) = 0 and f_{λ}(1) = 1.

2. f̂_{λ}(x) ≤ x.

Proof. We omit the proof of part 1, and we prove part 2 here. Since 0 ≤ x ≤ 1, we have that x^{i} ≤ x for all i ≥ 1. Then we see that

f̂_{λ}(x) = \frac{1}{ℓ(λ)} ∑_{i=1}^{k} m_{i}x^{i} ≤ \frac{1}{ℓ(λ)} ∑_{i=1}^{k} m_{i}x.

The observation that ∑_{i=1}^{k} m_{i} = ℓ(λ) completes the proof.

Additionally, we can characterize completely the cases when f̂_{λ} has more than two fixed points.

Proposition 13. Let f̂_{λ} be a normalized partition polynomial. Then f̂_{λ}(x) = x if and only if m_{1} = ℓ(λ); that is, λ only contains parts of size 1.

Proof. Suppose m_{1} = ℓ(λ). Then f̂_{λ}(x) = \frac{1}{ℓ(λ)} · ℓ(λ)x = x. Now suppose m_{j} > 0 for some j > 1. Then, using the fact that x^{j} < x when 0 < x < 1, we have that

f̂_{λ}(x) = \frac{1}{ℓ(λ)} ∑_{i=1}^{k} m_{i}x^{i} < \frac{1}{ℓ(λ)} ∑_{i=1}^{k} m_{i}x = x.

This completes the proof.

4.1 Integration basics

In this subsection, we show some basic integration results for normalized partition polynomials. We first show that integration on the interval [0, 1] may be viewed as a finite sum of “harmonic-like” numbers.

Theorem 14. Let f̂_{λ} be a normalized partition polynomial. Then we have that

∫_{0}^{1} f̂_{λ}(x) dx = \frac{1}{ℓ(λ)} ∑_{i=1}^{k} \frac{m_{i}}{i + 1}.

Proof. We integrate directly to obtain

∫_{0}^{1} f̂_{λ}(x) dx = ∫_{0}^{1} \frac{1}{ℓ(λ)} ∑_{i=1}^{k} m_{i}x^{i} dx = \frac{1}{ℓ(λ)} ∑_{i=1}^{k} m_{i} · \frac{x^{i+1}}{i + 1}|_{0}^{1} = \frac{1}{ℓ(λ)} ∑_{i=1}^{k} \frac{m_{i}}{i + 1}.

We now obtain an elementary bound for integrals of normalized partition polynomials.

Proposition 15. Let f̂_{λ} be a normalized partition polynomial. Then

0 < ∫_{0}^{1} f̂_{λ}(x) dx ≤ \frac{1}{2}.

Proposition 15 follows directly from Proposition 12.

Proposition 13 and the discussion afterwards show that the right inequality in Proposition 15 is strict if a partition contains parts of size greater than 1. Despite this, one can find a sequence of normalized partition polynomials for partitions with parts greater than 1 whose integrals approach 1/2. We discuss this further in Section 5.

To make the distinction between partitions with parts greater than 1 and those which only have parts of size 1, we call the former non-trivial partitions.

4.2 Operations on partitions

In this subsection, unless otherwise stated, λ and γ are partitions whose multiplicities are given by the sequence (a_{i}) and (b_{i}) respectively. We denote the largest part of λ by k_{λ} and the largest part of γ by k_{γ}. We define the sum λ ⊕ γ as the partition with multiplicities a_{i} + b_{i} and largest part max{k_{λ}, k_{γ}}. In other words, we obtain the sum λ ⊕ γ by combining all of the parts of λ and γ into one combined partition. This operation ⊕ on partitions has been previously defined [1], and Schneider more recently named this operation the product of two partitions as part of his multiplicative partition theory [11, Def. 1.2.2].

The normalized partition polynomial of λ ⊕ γ is given by

f̂_{λ⊕γ}(x) = \frac{1}{ℓ(λ) + ℓ(γ)} (∑_{i=1}^{k_{λ}} a_{i}x^{i} + ∑_{i=1}^{k_{γ}} b_{i}x^{i}) .

The following proposition shows what happens when we integrate the normalized partition polynomial of the sum of two partitions.

Proposition 16. We have that

∫_{0}^{1} f̂_{λ⊕γ}(x) dx = \frac{ℓ(λ)}{ℓ(λ) + ℓ(γ)} ∫_{0}^{1} f̂_{λ}(x) dx + \frac{ℓ(γ)}{ℓ(λ) + ℓ(γ)} ∫_{0}^{1} f̂_{γ}(x) dx.

Proof. We proceed by direct computation.

∫_{0}^{1} f̂_{λ⊕γ}(x) dx = \frac{1}{ℓ(λ) + ℓ(γ)} (∑_{i=1}^{k_{1}} \frac{a_{i}}{i + 1} + ∑_{i=1}^{k_{2}} \frac{b_{i}}{i + 1})

= \frac{1}{ℓ(λ) + ℓ(γ)} (ℓ(λ)\frac{1}{ℓ(λ)} ∑_{i=1}^{k_{1}} \frac{a_{i}}{i + 1} + ℓ(γ)\frac{1}{ℓ(γ)} ∑_{i=1}^{k_{2}} \frac{b_{i}}{i + 1})

= \frac{1}{ℓ(λ) + ℓ(γ)} (ℓ(λ) ∫_{0}^{1} f̂_{λ}(x) dx + ℓ(γ) ∫_{0}^{1} f̂_{γ}(x) dx) .

The result follows.

A few important corollaries result from this proposition.

Corollary 17. We have that

∫_{0}^{1} f̂_{λ⊕λ}(x) dx = ∫_{0}^{1} f̂_{λ}(x) dx.

Proof. By Proposition 16, we have that

∫_{0}^{1} f̂_{λ⊕λ}(x) dx = \frac{ℓ(λ)}{ℓ(λ) + ℓ(λ)} ∫_{0}^{1} f̂_{λ}(x) dx + \frac{ℓ(λ)}{ℓ(λ) + ℓ(λ)} ∫_{0}^{1} f̂_{λ}(x) dx

= \frac{1}{2} ∫_{0}^{1} f̂_{λ}(x) dx + \frac{1}{2} ∫_{0}^{1} f̂_{λ}(x) dx

= ∫_{0}^{1} f̂_{λ}(x) dx.

Corollary 18. The sum of two partitions of the same length has integral equal to the average of the individual integrals. Explicitly, if ℓ(λ) = ℓ(γ), then we have that

∫_{0}^{1} f̂_{λ⊕γ}(x) dx = \frac{1}{2} (∫_{0}^{1} f̂_{λ}(x) dx + ∫_{0}^{1} f̂_{γ}(x) dx) .

The proof of Corollary 18 is similar to the proof of Corollary 17. These results will be used to prove Theorem 2 in Section 5 through a binary search type argument.

5 Proof of Theorem 2

In order to prove Theorem 2, it suffices to fix an arbitrary c ∈ [0, 1/2] and to show that there exists a sequence of partitions (δ_{s}) such that

lim_{s→∞} ∫_{0}^{1} f̂_{δ_{s}}(x) dx = c.

We first provide constructive proofs of the c = 0 and c = 1/2 cases of Theorem 2.

Lemma 19. There exists a sequence of non-trivial partitions (α_{s}) such that

lim_{s→∞} ∫_{0}^{1} f̂_{α_{s}}(x) dx = 0.

Proof. Define the partition α_{s} by ⟨1^{1}, 2^{0}, 3^{0}, …, s^{s−1}⟩. Then we observe that f̂_{α_{s}}(x) = \frac{1}{s}(x + (s − 1)x^{s}), and

lim_{s→∞} ∫_{0}^{1} f̂_{α_{s}}(x) dx = lim_{s→∞} \frac{1}{s} (\frac{1}{2} + \frac{s − 1}{s + 1}) = 0.

A similar result holds for non-trivial partitions whose integral approaches 1/2.

Lemma 20. There exists a sequence of non-trivial partitions (β_{s}) such that

lim_{s→∞} ∫_{0}^{1} f̂_{β_{s}}(x) dx = 1/2.

Proof. Define the partition β_{s} by ⟨1^{s−1}, 2^{0}, 3^{0}, …, (s − 1)^{0}, s^{1}⟩. Then we have that f̂_{β_{s}}(x) = \frac{1}{s}((s − 1)x + x^{s}), and

lim_{s→∞} ∫_{0}^{1} f̂_{β_{s}}(x) dx = lim_{s→∞} \frac{1}{s} (\frac{s − 1}{2} + \frac{1}{s + 1}) = 1/2.

The following theorem, combined with Lemmas 19 and 20, will give Theorem 2 immediately.

Theorem 21. Suppose that α and β are partitions such that

∫_{0}^{1} f̂_{α}(x) dx = a and ∫_{0}^{1} f̂_{β}(x) dx = b.

If 0 < a < b < 1/2 and ℓ(α) = ℓ(β), then for every c ∈ (a, b), there exists a sequence (δ_{s}) of partitions such that

lim_{s→∞} ∫_{0}^{1} f̂_{δ_{s}}(x) dx = c.

Proof. Let ϵ > 0 be given. We construct (δ_{s}) recursively by first constructing two sequences (β_{s}) and (α_{s}) of partitions such that each β_{s} approximates c from above and each α_{s} approximates c from below. Define β_{1} = β, α_{1} = α, and δ_{1} = α_{1} ⊕ β_{1}. The sequence (δ_{s}) will be defined by δ_{s} = α_{s} ⊕ β_{s}.

Let r ≥ 1. If c = ∫_{0}^{1}f̂_{δ_{r}}(x) dx, then define δ_{s} = δ_{r}. Otherwise, we have one of the

following two cases.

Case 1: c < ∫_{0}^{1}f̂_{δ_{r}} dx. Define β_{r+1} = δ_{r} and α_{r+1} = α_{r} ⊕ α_{r}. Since ℓ(β_{r+1}) = 2^{r+1}ℓ(α) =

ℓ(α_{r+1}), we see that

∫_{0}^{1} f̂_{δ_{r+1}}(x) dx = \frac{1}{2} (∫_{0}^{1} f̂_{β_{r+1}}(x) dx + ∫_{0}^{1} f̂_{α_{r+1}}(x) dx) .

Case 2: c > ∫_{0}^{1}f̂_{δ_{r}} dx. Define β_{r+1} = β_{r} ⊕ β_{r} and α_{r+1} = δ_{r}. Since ℓ(β_{r+1}) = 2^{r+1}ℓ(α) =

ℓ(α_{r+1}), we see that

∫_{0}^{1} f̂_{δ_{r+1}}(x) dx = \frac{1}{2} (∫_{0}^{1} f̂_{β_{r+1}}(x) dx + ∫_{0}^{1} f̂_{α_{r+1}}(x) dx) .

Note that by definition,

∫_{0}^{1} f̂_{δ_{s}}(x) dx = \frac{1}{2} (∫_{0}^{1} f̂_{β_{s}}(x) dx + ∫_{0}^{1} f̂_{α_{s}}(x) dx) .

Since the integral for α_{s} is less than the integral for β_{s}, we obtain the following inequality:

∫_{0}^{1} f̂_{α_{s}}(x) dx < ∫_{0}^{1} f̂_{δ_{s}}(x) dx < ∫_{0}^{1} f̂_{β_{s}}(x) dx.

Now let N > log_{2} (\frac{b−a}{ϵ}). The previous inequality, along with the fact that c is an upper bound for the integral for α_{s}, yields the following for all s ≥ N:

|∫_{0}^{1} f̂_{δ_{s}}(x) dx − c| < ∫_{0}^{1} f̂_{β_{s}}(x) dx − ∫_{0}^{1} f̂_{α_{s}}(x) dx ≤ \frac{b − a}{2^{s}} ≤ \frac{b − a}{2^{N}} < ϵ.

Therefore, lim_{s→∞} ∫_{0}^{1}f̂_{δ_{s}}(x) dx = c as desired.

We are now ready to prove Theorem 2.

Proof of Theorem 2. The edge cases c = 0 and c = 1/2 follow from Lemma 19 and Lemma 20, respectively. Thus, it suffices to show that the result holds for c ∈ (0, 1/2). Define the partitions

α_{s} = ⟨1^{1}, 2^{0}, 3^{0}, …, (s − 1)^{0}, s^{s−1}⟩ and β_{s} = ⟨1^{s−1}, 2^{0}, 3^{0}, …, (s − 1)^{0}, s^{1}⟩.

Then we have that

∫_{0}^{1} f̂_{α_{s}}(x) dx = \frac{1}{s} (\frac{1}{2} + \frac{s − 1}{s + 1}) ,
∫_{0}^{1} f̂_{β_{s}}(x) dx = \frac{1}{s} (\frac{s − 1}{2} + \frac{1}{s + 1}) .

Since ℓ(α_{s}) = ℓ(β_{s}) for all s ∈ ℕ, Theorem 21 shows that the result holds for all c with

∫_{0}^{1} f̂_{α_{s}}(x) dx < c < ∫_{0}^{1} f̂_{β_{s}}(x) dx.

For increasing s, these are nested intervals. The union of all such intervals is the set (0, 1/2). This proves Theorem 2.

6 Proofs of Theorems 5 and 6

Proof of Theorem 5. Recall that one may compute Avg(n, ℓ) by evaluating the integral of the sum of all partitions of n with ℓ parts. It is straightforward to enumerate all partitions of n into one part and all partitions of n into two parts. Adding all of the parts together for ℓ = 1 and ℓ = 2 gives the partition λ_{1} = ⟨1^{0}, 2^{0}, …, n^{1}⟩ for all n, and the partitions

λ_{2}^{odd} = ⟨1^{1}, 2^{1}, …, (n − 1)^{1}, n^{0}⟩

if n is odd or

λ_{2}^{even} = ⟨1^{1}, 2^{1}, …, ((n/2) − 1)^{1}, (n/2)^{2}, ((n/2) + 1)^{1}, …, (n − 1)^{1}, n^{0}⟩

if n is even. Let H_{n} denote the nth Harmonic number. Then the averages are

Avg(n, 1) = ∫_{0}^{1} f̂_{λ_{1}}(x) dx = \frac{1}{n + 1}

for all n; and

Avg(n, 2) = ∫_{0}^{1} f̂_{λ_{2}^{odd}}(x) dx = \frac{1}{2 · ⌊\frac{n}{2}⌋} (\frac{1}{2} + \frac{1}{3} + ⋯ + \frac{1}{n}) = \frac{1}{2 · ⌊\frac{n}{2}⌋}(H_{n} − 1)

if n is odd, or

Avg(n, 2) = ∫_{0}^{1} f̂_{λ_{2}^{even}}(x) dx = \frac{1}{2 · ⌊\frac{n}{2}⌋} (\frac{1}{2} + \frac{1}{3} + ⋯ + \frac{1}{n} + \frac{1}{n/2}) = \frac{1}{2 · ⌊\frac{n}{2}⌋} (H_{n} − 1 + \frac{2}{n})

if n is even. Noting that ⌊\frac{n}{2}⌋ ≤ \frac{n}{2}, we see that

Avg(n, 2) ≥ \frac{1}{2 · \frac{n}{2}} (H_{n} − 1) ≥ \frac{1}{n + 1}(H_{n} − 1) ≥ Avg(n, 1)

for all n ≥ 4. One can check by hand that the result also holds for n < 4. Thus, we have that Avg(n, 1) ≤ Avg(n, 2) for all n ∈ ℕ.

Note in the above proof that we have the asymptotic expression Avg(n, 2) ∼ ln(n)/n as n → ∞, since the nth harmonic number is asymptotic to ln(n).

Proof of Theorem 6. We will show that Avg(n, 3) is asymptotically bounded below by 2 ln(n)/n. Let n ∈ ℕ, and let λ_{3} be the sum of all partitions of n into 3 parts. To get a lower bound on the multiplicity of each part in λ_{3}, let 1 ≤ i ≤ n − 2, and note that the following sums give partitions of n into 3 parts:

1 + i + (n − (i + 1)) = 2 + i + (n − (i + 2)) = ⋯ = (i − 1) + i + (n − (2i − 1)),

i + i + (n − 2i) = i + (i + 1) + (n − (2i + 1)) = ⋯ = i + ⌊\frac{n − i}{2}⌋ + ⌈\frac{n − i}{2}⌉ .

Counting the number of times i appears, there are at least i − 1 instances in the first row and at least ⌊\frac{n−i}{2}⌋ − i + 1 in the second row. This gives a lower bound of

i − 1 + ⌊\frac{n − i}{2}⌋ − i + 1 = ⌊\frac{n − i}{2}⌋ ≥ \frac{n − i}{2} − 1

parts of size i among all partitions of n into 3 parts. Define the function g : [0, n − 2] → ℝ by g(x) = \frac{n}{2} − 1 − \frac{n/2}{n−2}x. We use this function to obtain a lower bound for the integral of f_{λ_{3}}, as it always lies below the bound achieved above. We see that

Avg(n, 3) = ∫_{0}^{1} f̂_{λ_{3}}(x) dx

≥ \frac{1}{ℓ(λ_{3})} ∫_{0}^{n−2} \frac{g(x)}{x + 1} dx

= \frac{1}{ℓ(λ_{3})} · ((\frac{n}{2} − 1) ln(n − 1) − ((n − 2) − ln(n − 1)) · \frac{n/2}{n − 2})

∼ \frac{1}{ℓ(λ_{3})} · \frac{n}{2} ln(n)

as n → ∞. Also, as n → ∞ we have that ℓ(λ_{3}) ∼ 3 · \frac{n^{2}}{12} , by a known asymptotic formula for the number of partitions of size n into 3 parts (see [7]). This yields

Avg(n, 3) ≥ \frac{1}{ℓ(λ_{3})} · \frac{n}{2} ln(n) ∼ \frac{1}{3 · \frac{n^{2}}{12}} · \frac{n}{2} ln(n) = \frac{2 ln(n)}{n} ∼ 2Avg(n, 2)

as n → ∞. Therefore, Avg(n, 3) ≥ Avg(n, 2) for sufficiently large n, as desired.

7 Acknowledgments

The authors would like to thank Matthew Just and Robert Schneider for many enlightening discussions regarding partition statistics, Ken Ono for helpful comments on the content of this paper, and Dario Mathiä for investigating a preliminary version of Question 9 and sharing insightful observations and calculations. The authors would also like to thank the referees for their suggestions which greatly improved this paper. The first author is supported by an AMS-Simons Travel Grant and an internal grant from the University of Texas at Tyler.

References

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

[2] G. E. Andrews and K. Eriksson, Integer Partitions, Cambridge University Press, 2004.

[3] M. L. Dawsey, M. Just, and R. Schneider, A “supernormal” partition statistic, preprint,

2021. Available at https://arxiv.org/abs/2107.14284.

[4] G. H. Hardy and S. Ramanujan, Asymptotic formulæ in combinatory analysis, Proc. London Math. Soc. 17 (1918), 75–115.

[5] G. H. Hardy and E. Wright, An Introduction to the Theory of Numbers, 6th edition, Oxford University Press, 2008.

[6] M. Just, Personal communication with the first author, September 18, 2020.

[7] C. Knessl and J. B. Keller, Partition asymptotics from recursion equations, SIAM Journal on Applied Mathematics 50 (1990), 323–338.

[8] H. Rademacher, A convergent series for the partition function p(n), Proc. Natl. Acad. Sci. U. S. A. 23 (1937), 78–84.

[9] S. Ramanujan, On certain arithmetical functions, Trans. Cambridge Philos. Soc. 22 (1916), 159–184.

[10] S. Ramanujan, Congruence properties of partitions, Math. Z. 9 (1921), 147–153.

[11] R. Schneider, Eulerian series, zeta functions and the arithmetic of partitions, Ph.D. thesis, Emory University, 2018. Available at https://arxiv.org/abs/2008.04243.

[12] N. J. A. Sloane et al. The On-Line Encyclopedia of Integer Sequences, 2020. Available

at https://oeis.org.

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

[14] S. Zemel, Moments of partitions and derivatives of higher order, J. Algebraic Combin. 54 (2021), 425–439.

2020 Mathematics Subject Classification: Primary 11P82; Secondary 05A17, 11C08. Keywords: partition, polynomial.

(Concerned with sequences \underline{A000041}, \underline{A008277}, and \underline{A305078}.)

Received August 2 2021; revised versions received March 9 2022; June 7 2022. Published in Journal of Integer Sequences, June 10 2022.

Return to Journal of Integer Sequences home page.