Using GENERATINGFUNCTIONOLOGY to Enumerate Distinct-Multiplicity Partitions

Doron ZEILBERGER^{1}

In fond memory of Guru Herbert Saul WILF (28 Sivan 5691- 12 Tevet 5772) zecher gaon l’bracha

Preamble

About a year ago, Herb Wilf[W1] posed, on-line, eight intriguing problems. I don’t know the answer to any of them, but I will say something about the sixth question.

Herb Wilf’s 6th Question: Let T (n) be the set of partitions of n for which the (nonzero) multiplicities of its parts are all different, and write f(n) = |T (n)|. See Sloane’s sequence A098859 for a table of values. Find any interesting theorems about f(n) …

First, I will explain how to compute the first few terms of f(n). Shalosh can easily get the first 250 terms, but as n gets larger it gets harder and harder to compute, unlike its unrestricted cousin, p(n). I conjecture that the fastest algorithm takes exponential time, but I have no idea how to prove that claim. I am impressed that, according to Sloane, Maciej Ireneusz Wilczynsk computed 508 terms.

Recall that the generating function for the number of integer partitions of n whose largest part is ≤ m, p_{m}(n), is the very simple rational function

∑_{n=0}^{∞} p_{m}(n)q^{n} = \frac{1}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{m})} .

The main purpose of this note is to describe, using Generatingfunctionology, so vividly and lucidly preached in W’s classic book [W2], how to compute the generating function (that also turns out to be rational) for the number of partitions of n whose largest part is ≤ m and all its (nonzero) multiplicities are distinct, let’s call it f_{m}(n). As m gets larger, the formulas get more and more complicated, but we sure do have an answer, in the sense of the classic article [W3], for any fixed m, but of course not for a symbolic m.

Even more is true! Because, like \frac{1}{(1−q)(1−q^{2})···(1−q^{m})}, the generating function of f_{m}(n), ∑_{n=0}^{∞} f_{m}(n)q^{n}, turns out (as we will see) to only have roots-of-unity poles, whose highest order is m, it follows that f_{m}(n) is a quasi-polynomial of degree m − 1 in n. Now that’s a very good answer! (in W’s sense, albeit only for a fixed m).

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/ . First Version: Jan. 18, 2012. Last version, Feb. 4, 2012 [putting a link to Vaclav Kotesovec’s graph. Pervious Version: Feb. 1, 2012 [adding a comment of Daniel Kane at the end].

Accompanied by Maple package DMP downloadable from http://www.math.rutgers.edu/~zeilberg/tokhniot/DMP . Sample input and output files may be viewed in the front of this article:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/dmp.html . Supported in part by the USA National Science Foundation.

How to Compute Many terms of f(n)?

p_{m}(n) is very easy to compute. For example, one may use the recurrence

p_{m}(n) = p_{m−1}(n) + ∑_{i=1}^{⌊n/m⌋} p_{m−1}(n − mi) ,

together with the initial condition p_{1}(n) = 1, p_{m}(0) = 1.

How can we adapt this in order to compute f_{m}(n)? The contribution from the partitions counted by f_{m}(n) where m does not show up is f_{m−1}(n), in analogy with the p_{m−1}(n) term in the above recurrence. But if m does show up, it does so with a certain multiplicity, i, say, where 1 ≤ i ≤ ⌊n/m⌋, and removing these i copies of m results in a partition counted by f_{m−1}(n − mi) -so all its multiplicities are different- and in addition none of these multiplicities may be i. Continuing, we are forced to introduce a much more general discrete function f_{m}(n; S) whose arguments are m and n and a set of “forbidden multiplicities”, S.

So let’s define f_{m}(n; S) to be the number of partitions of n with parts ≤ m, with all its multiplicities distinct and none of these multiplicities belonging to S. Our intermediate object of desire, f_{m}(n), is simply f_{m}(n; ∅), and the ultimate object, f(n), is f_{n}(n; ∅).

The recurrence for f_{m}(n; S) is, naturally,

f_{m}(n; S) = f_{m−1}(n; S) + ∑_{i=1,i∉S}^{⌊n/m⌋} f_{m−1}(n − im; S ∪ {i}) ,

because once we decided on the number of times m shows up, let’s call it i, where i is between 1 and ⌊m/m⌋ and i ∉ S, the partition (of n − mi) obtained by removing these i copies of m must forbid the set of multiplicities S ∪ {i}.

In the Maple package DMP, procedure qnmS(n,m,S) implements f_{m}(n; S) and procedure qn(n) implements f(n).

Inclusion-Exclusion

Let P_{m}(n) be the set of partitions of n whose parts are all ≤ m, in other words, the set that p_{m}(n) is counting. Consider the set of all partitions whose largest part is ≤ m, where we write a partition in frequency notation:

P_{m} := {1^{a_{1}}2^{a_{2}} … m^{a_{m}} | a_{1}, …, a_{m} ≥ 0} .

For example 1^{3}2^{5}4^{2} is the partition of twenty-one usually written as 4422222111. Introducing symbols x_{1}, x_{2}, …, x_{m}, we define the Weight of a partition to be

W eight(1^{a_{1}}2^{a_{2}} … m^{a_{m}}) := x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{m}^{a_{m}} .

The weight-enumerator of P_{m} is, by ordinary-generatingfunctionology

W eight(P_{m}) = \frac{1}{(1 − x_{1})(1 − x_{2}) ⋯ (1 − x_{m})} ,

since we make m independent decisions:

• how many copies of 1?(Weight enumerator = 1 + x_{1} + x_{1}^{2} + … = (1 − x_{1})^{−1}) ,

• how many copies of 2? (Weight enumerator = 1 + x_{2} + x_{2}^{2} + … = (1 − x_{2})^{−1}) , …

• how many copies of m? (Weight enumerator = 1 + x_{m} + x_{m}^{2} + … = (1 − x_{m})^{−1}). But we want to find the weight-enumerator of the much-harder-to-weight-count set

F_{m} := {1^{a_{1}}2^{a_{2}} … m^{a_{m}} | a_{1}, …, a_{m} ≥ 0 ; a_{i} ≠ a_{j} (if a_{i} > 0, a_{j} > 0)} .

Calling the members of F_{m} good, we see that a member of P_{m} is good if it does not belong to any of the following \binom{m}{2} sets, S_{ij} 1 ≤ i < j ≤ m:

S_{ij} := {1^{a_{1}}2^{a_{2}} … m^{a_{m}} ∈ P_{m} |a_{i} = a_{j} > 0} .

By inclusion-exclusion, the weight-enumerator of F_{m} is

∑_{G}(−1)^{|G|}W eight ({∩ \atop ij ∈ G} S_{ij}) ,

where the summation ranges over all 2^{m(m−1)/2} subsets of {(i, j) | 1 ≤ i < j ≤ m}. But the G’s can be naturally viewed as labeled graphs on m vertices. Such a graph has several connected components, and together they naturally induce a set partition {C_{1}, C_{2}, …, C_{r}} of {1, 2, …, m}. We have:

W eight ({∩ \atop ij ∈ G} S_{ij}) = ∏_{i=1}^{r} weight(C_{i}) ,

where if |S| = 1, S = \{s\}, say, then weight(S) = \frac{1}{1−x_{s}}, and if |S| = d > 1, S = \{s_{1}, s_{2}, … s_{d}\}, say, then

weight(S) = \frac{x_{s_{1}}x_{s_{2}} ⋯ x_{s_{d}}}{1 − x_{s_{1}}x_{s_{2}} ⋯ x_{s_{d}}} .

To justify the latter, note that if vertices s_{1}, s_{2}, … s_{d} all belong to the same connected component of our graph then, by transitivity, we have that all a_{s_{1}} = a_{s_{2}} = … = … a_{s_{d}} > 0, and the weightenumerator is the infinite geometric series

∑_{α=1}^{∞}(x_{s_{1}} ⋯ x_{s_{d}})^{α} = \frac{x_{s_{1}}x_{s_{2}} ⋯ x_{s_{d}}}{1 − x_{s_{1}}x_{s_{2}} ⋯ x_{s_{d}}} .

But quite a few graphs correspond to any one set-partition. To find out the coefficients in front, for any set-partition {C_{1}, C_{2}, …, C_{r}} of {1, …, m} we must find

∑_{G}(−1)^{|G|} ,

summed over all the graphs that gives rise to the above set partition. But this is the product of the analogous sums where one focuses on one connected component at a time, and then multiplies everything together.

Let’s digress and figure out ∑_{G}(−1)^{|G|} over all connected labeled graphs on n vertices. For the sake of clarity, let’s, more generally, figure out ∑_{G} y^{|G|} with a general variable y.

By exponential-generatingfunctionology[W2] (see also [Z]), this sum is nothing but the coefficient of t^{n}/n! in

log (∑_{i=0}^{∞}(1 + y)^{\binom{i}{2}} \frac{t^{i}}{i!} ) .

Going back to y = −1, we see that we need the coefficient of t^{n}/n! in

log (∑_{i=0}^{∞}(1 + (−1))^{\binom{i}{2}} \frac{t^{i}}{i!} ) = log (∑_{i=0}^{∞} 0^{\binom{i}{2}} \frac{t^{i}}{i!} ) = log(1 + t)

= ∑_{n=1}^{∞}(−1)^{n−1} \frac{t^{n}}{n} = ∑_{n=1}^{∞}(−1)^{n−1}(n − 1)!\frac{t^{n}}{n!} .

So the desired sum is (−1)^{n−1}(n − 1)!.

Let’s define for any set of positive integers, S,

mishkal(S) = \{ \begin{matrix}1/(1 − x_{s}), & if |S| = 1 where S = \{s\} ; \\ (−1)^{d−1}(d − 1)!(x_{s_{1}} ⋯ x_{s_{d}})/(1 − x_{s_{1}} ⋯ x_{s_{d}}), & if |S| = d > 1 where S = \{s_{1}, … s_{d}\}. \end{matrix}

For any set partition C = {C_{1}, …, C_{r}} let’s define

Mishkal(C) = mishkal(C_{1}) ⋯ mishkal(C_{r}) .

It follows that the weight-enumerator of F_{m} according to W eight(1^{a_{1}}2^{a_{2}} … m^{a_{m}}) := x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{m}^{a_{m}} is

∑_{C} Mishkal(C) ,

where the sum has B_{m} terms (B_{m} being the Bell numbers), one for each set-partition of {1, …, m}.

Finally, to get an “explicit” formula (as a sum of B_{m} terms, each a simple rational function of q), for the generating function ∑_{n=0}^{∞} f_{m}(n)q^{n}, all we need is replace x_{i} by q^{i}, for i = 1 … m, getting

∑_{n=0}^{∞} f_{m}(n)q^{n} = ∑_{C} P oids(C) ,

where for a set partition C = {C_{1}, …, C_{r}}

P oids(C) = poids(C_{1}) ⋯ poids(C_{r}) ,

and where for an individual set S:

poids(S) = \{ \begin{matrix}1/(1 − q^{s}), & if |S| = 1 where S = \{s\} ; \\ (−1)^{d−1}(d − 1)!q^{s_{1}+...+s_{d}}/(1 − q^{s_{1}+...+s_{d}}), & if |S| = d > 1 where S = \{s_{1}, … s_{d}\}. \end{matrix} .

It follows that indeed f_{m}(n) is a quasi-polynomial of degree m − 1 in n. Furthermore, since the only pole that has multiplicity m is q = 1, it follows that the leading term (of degree m − 1) is a pure polynomial.

The generating function, ∑_{n=0}^{∞} f_{m}(n)q^{n}, for any desired positive integer m, is implemented in procedure GFmq(m,q) in the Maple package DMP. For the Weight-enumerator (or rather with x_{i} replaced by q^{i}x_{i}, for i = 1, …, m), see GFmxq(m,x,q). Since the Bell numbers grow very fast, the formulas get complicated rather fast, but in principle we do have a very nice answer for any specific m, but in practice, for large m it is only “nice” in principle. Of course it is anything but nice when viewed also as function of m, and that’s why f(n) = f_{n}(n) is probably very hard to compute for larger n.

To see the outputs of GFmq(m,q) for 1 ≤ m ≤ 8 see:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oDMP3 .

Asymptotics

Recall that Hardy and Ramanujan tell us that as n goes to infinity, p(n) is asymptotic to \frac{1}{4n\sqrt{3}}exp(C\sqrt{n}) where C = \sqrt{2/3}π = 2.565099661 …, and hence log p(n)/\sqrt{n} converges to C. By looking at the sequence log f(n)/\sqrt{n} for 1 ≤ n ≤ 508, it seems that this too converges to a limit, that appears to be a bit larger than 1.517 (but of course way less than 2.565099661 …). Let’s call that constant the Wilf constant.

The numerical evidence is here: http://www.math.rutgers.edu/~zeilberg/tokhniot/oDMP4 .

Let me conclude with two challenges.

• Prove that the Wilf constant exists.

• Determine the exact value of the Wilf constant (if it exists) in terms of π or other famous constants. Failing this, find non-trivial rigorous lower and upper bounds.

Added Feb. 1, 2012: According to Daniel Kane [so far private communication, hopefully he would write it up soon] the true asymptotics of log f(n) is (6n)^{1/3}log(n)/3.

Added Feb. 4, 2012: According to Vaclav Kotesovec, this does not agree with the numerics up to 518 terms [but of course, with asymptotics, one may never know for sure]. See

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/dmpKotesovec.gif .

References

[W1] Herbert Wilf, Some Unsolved problems,

http://www.math.upenn.edu/%7Ewilf/website/UnsolvedProblems.pdf, posted: Dec. 13, 2010.

(viewed Jan. 16, 2012)

[W2] Herbert S. Wilf, “Generatingfunctionology”, Academic Press, First edition 1990, Second Edition 1994. Third Edition: AK Peters, 2005. Second edition is freely downloadable from

http://www.math.upenn.edu/%7Ewilf/gfology2.pdf .

[W3] Herbert S. Wilf, What is an Answer?, Amer. Math. Monthly 89 (1982), 289-292.

[Z] Doron Zeilberger, Enumerative and Algebraic Combinatorics, in: “Princeton Companion to Mathematics” , (Timothy Gowers, ed.), Princeton University Press, 550-561. Available from:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enu.pdf