Two Questions about the Fractional Counting of Partitions

Doron ZEILBERGER and Noam ZEILBERGER

Abstract: We recall the notion of fractional enumeration and immediately focus on the fractional counting of integer partitions, where each partition gets ‘credit’ equal to the reciprocal of the product of its parts. We raise two intriguing questions regarding this count, and for each such question we are pledging a $100 donation to the OEIS, in honor of the first solver. In this revised version we announce that both questions have been answered. The first was first answered by Will Sawin and the second was answered by Christopher Ryba. A donation to the OEIS, of $100 each, in their honor has been made.

Update Oct. 31, 2018: Will Sawin has solved the first question. A donation to the OEIS, in his honor, has been made. His proof is given as an appendix to this revised version.]

Update 10am, Nov. 2, 2018: Fernando Chamizo has independently solved the first question, with an even shorter rendition. We give a reference to it in this revised version.]

Update 2:30pm, Nov. 2, 2018: Gjergji Zaimi kindly pointed out that Question 1 was posed and answered completely by D.H. Lehmer in Theorem 3 of his article “On reciprocally weighted partitions”, Acta Arithmetica XXI(1972), p. 379-388, that is available here:

http://matwbn.icm.edu.pl/ksiazki/aa/aa21/aa21123.pdf .

Update Nov. 8, 2018: Christopher Ryba solved Question 2 . His elegant article appeared here:

https://arxiv.org/abs/1811.03440 .

Preface: There are many ways to enumerate

Naive counting of combinatorial sets counts by 1. Generatingfunctionology counts by z^{stat}, where z is an indeterminate (i.e. symbolic), and stat is a certain statistic of interest. Statistical mechanics also ‘counts’ by z^{stat}, but now z is a continuous real (or complex) variable of physical significance. Sieve theory ‘counts’ by ±1.

The general scenario of naive enumeration is a sequence of combinatorial sets, A_{n}, naturally indexed by a non-negative integer n, and one wants a formula, or at least an efficient algorithm, to compute the number of elements of A_{n}, denoted by |A_{n}|.

For example,

• The sequence ‘set of subsets of {1, …, n}’, where |A_{n}| = 2^{n}.

It is: https://oeis.org/A000079 .

• The sequence ‘set of permutations of {1, …, n}’, where |A_{n}| = n!.

It is: https://oeis.org/A000142 .

• The sequence of integer partitions of n, where |A_{n}| = p(n). It is: https://oeis.org/A000041 .

There are no ‘nice’ formulas for p(n), but there exist efficient algorithms. One not so efficient ‘formula’ is ‘the coefficient of q^{n} in 1/((1 − q)(1 − q^{2}) ⋯ (1 − q^{n}))’ .

The general scenario of Generatingfunctionology enumeration is a sequence of combinatorial sets, A_{n}, naturally indexed by a non-negative integer n, and a certain ‘statistic’ defined on its objects s → stat(s), and one wants a formula, or at least an efficient algorithm, to compute the sequence of weight-enumerators, |A_{n}|_{z} := ∑_{s∈A_{n}} z^{stat(s)}.

For example,

• The sequence ‘set of subsets of {1, …, n}’, where the statistic is ‘cardinality’, and we have |A_{n}|_{z} = (1+z)^{n}.

• The sequence ‘set of permutations of {1, …, n}’, where the statistic is ‘number of inversions’, and we have |A_{n}|_{z} = 1 · (1 + z) · (1 + z + z^{2}) ⋯ (1 + z + … + z^{n−1}) .

• The sequence of integer partitions of n, where the statistic is ‘largest part’, for which, once again, there is no ‘nice’ formula, but there exist efficient algorithms. One, not so efficient ‘formula’ is the coefficient of q^{n} in 1/((1 − qz)(1 − q^{2}z) ⋯ (1 − q^{n}z))

Signed Counting

Let μ(n) be 1 if n is a product of an even number of distinct primes, −1 if it is a product of an odd number of distinct primes, and 0 otherwise. The signed enumeration of the set A(n) := {1, …, n}, whose naive count is n, is

M(n) := ∑_{i=1}^{n} μ(i) .

Exercise: Find a closed form formula for M(n) that would entail its asymptotic behavior. If you can’t, prove at least that it is O(n^{\frac{1}{2} +ϵ}) for any ϵ > 0. Failing this, prove at least that it is O(n^{0.99999999999999999999}).

Functional Counting

The function f(x) := z^{x}, that gives the generatingfunctionology count could be replaced by any function. So let’s define

a_{f}(n) := ∑_{s∈A_{n}} f(stat(s)) .

If f is a power f(x) := x^{k}, one gets the numerator of the k-th moment of stat.

Fractional Counting

This corresponds to the case f(x) := \frac{1}{x}. Fractional counting of lattice paths is dealt with in [FGZ]. Another natural form of fractional counting was described by Baez and Dolan [BD], called ‘homotopy cardinality’ (or ‘groupoid cardinality’). The homotopy cardinality

|X| = ∑_{[x]∈X/∼} \frac{1}{|Aut(x)|}

of a groupoid X counts the number of isomorphism classes of objects in X, but where each class is weighted inversely by the size of the automorphism group of any representative element.

Maple package

This article is accompanied by a Maple package, FCP.txt, obtainable from the front of this article:

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/fcp.html .

That page also contains sample input and output files, as well as a nice picture. Fractional Counting of Partitions From now we will focus on fractional counting of integer partitions where each partition gets ‘credit’ the reciprocal of the product of its parts. Definition: Let b(n) be defined by

b(n) := ∑_{{p_{1}+...+p_{k}=n \atop p_{1}≥p_{2}≥...≥p_{k}>0}} \frac{1}{p_{1}p_{2} … p_{k}} .

Let’s spell out the first few terms of the sequence of fractions b(n)

b(1) = \frac{1}{1} = 1 ,

b(2) = \frac{1}{1 · 1} + \frac{1}{2} = \frac{3}{2} ,

b(3) = \frac{1}{1 · 1 · 1} + \frac{1}{2 · 1} + \frac{1}{3} = \frac{11}{6} .

For the first 100 terms see

http://sites.math.rutgers.edu/~zeilberg/tokhniot/oFCP1.txt .

How to compute b(n) for many n? Let’s recall one of the many ways to compute a table of p(n), the naive count of the set of partitions of n, for many values of n. It is not the most efficient way, but the one easiest to adapt to the computation of the fractional count, that we called b(n). Let p(n, k) be the number of partitions of n whose largest part is k. Once we know p(n, k) for 1 ≤ k ≤ n ≤ N we would, of course, know p(n) for 1 ≤ n ≤ N, since

p(n) = ∑_{k=1}^{n} p(n, k) .

p(n, k) may be computed, recursively, via the dynamical programming recurrence

p(n, k) = ∑_{k′=1}^{k} p(n − k, k′) ,

since removing the largest part, k, of a partition of n results in a partition of n − k whose largest part is ≤ k. A more compact recursion, without the ∑, is obtained as follows. Replace, in the above equation, n and k by n − 1 and k − 1 respectively, to get

p(n − 1, k − 1) = ∑_{k′=1}^{k−1} p(n − k, k′) .

Subtracting gives

p(n, k) − p(n − 1, k − 1) = p(n − k, k) ,

leading to the recurrence

p(n, k) = p(n − 1, k − 1) + p(n − k, k) .

We now proceed analogously. Let b(n, k) be the fractional count of the set of partitions of n whose largest part is k. Once we know b(n, k) for 1 ≤ k ≤ n ≤ N we would, of course, know b(n) for 1 ≤ n ≤ N, since

b(n) = ∑_{k=1}^{n} b(n, k) .

b(n, k) may be computed via the dynamical programming recurrence

b(n, k) = \frac{1}{k} ∑_{k′=1}^{k} b(n − k, k′) ,

since removing the largest part, k, of a partition of n results in a partition of n − k whose largest part is ≤ k. Multiplying both sides by k yields

k b(n, k) = ∑_{k′=1}^{k} b(n − k, k′) .

Replacing n and k by n − 1 and k − 1 respectively, yields

(k − 1) b(n − 1, k − 1) = ∑_{k′=1}^{k−1} b(n − k, k′) .

Subtracting gives

k b(n, k) − (k − 1) b(n − 1, k − 1) = b(n − k, k) ,

leading to the recurrence

b(n, k) = \frac{k − 1}{k} b(n − 1, k − 1) + \frac{1}{k} b(n − k, k) ,

with the boundary conditions b(n, 1) = 1 and b(n, k) = 0 if k > n. Procedure bnk(n,k) implements this recurrence in the Maple package FCP.txt, and bnkF(n,k) is the much faster floating-point version. We believe that the following fact is easy to prove. Fact: C := lim_{n→∞} \frac{b(n)}{n} exists. The convergence is rather slow. Here are the values of \frac{b(n)}{n} for 15000 − 10 ≤ n ≤ 15000.

0.5611411658 , 0.5611411846 , 0.5611412033 , 0.5611412220 , 0.5611412407 , 0.5611412594,

0.5611412781 , 0.5611412968 , 0.5611413156 , 0.5611413344 , 0.5611413530 .

One of us (DZ) is pledging a $100 donation to the OEIS in honor of the first person to answer the following question.

Question 1: Identify C in terms of known mathematical constants. In particular, is C = e^{−γ}? Here γ is Euler’s constant. Note that e^{−γ} = 0.5614594835668851698 ….

Added Oct. 31, 2018: We are almost sure that C is indeed e^{−γ}. If you use the ‘ansatz’

\frac{b(n)}{n} = c_{0} + \frac{c_{1}}{n} ,

and plug-in n = 14999 and n = 15000, you would get two equations in the two unknowns c_{0} and c_{1}, whose solution is

{c_{0} = 0.5614203344, c_{1} = −4.184721000} ,

agreeing to four decimal places.

[Update Oct. 31, 2018: Will Sawin has solved Question 1. A donation to the OEIS, in his honor, has been made. His proof is given as an appendix to this article.]

[Update 10:30am, Nov. 2, 2018: Fernando Chamizo has independently solved the first question, with an even shorter rendition. It is available, with kind permission of Professor Chamizo, from

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/fcpFernandoChamizo.pdf .]

[Update 2:30pm, Nov. 2, 2018: Gjergji Zaimi kindly pointed out that Question 1 was posed and answered completely by D.H. Lehmer in Theorem 3 of his article “On reciprocally weighted partitions”, Acta Arithmetica XXI(1972), p. 379-388,

http://matwbn.icm.edu.pl/ksiazki/aa/aa21/aa21123.pdf ]

We also noticed, numerically, that for each real 0 < x < 1

f(x) := lim_{n→∞} b(n, ⌊nx⌋) ,

exists, and defines a nice, decreasing function. To see an approximation, using n = 2000, see

http://sites.math.rutgers.edu/~zeilberg/tokhniot/picsFCP/fcp1.html  .

We are also pledging a $100 donation to the OEIS in honor of the first person to answer the following question.

Question 2: Find a differential equation satisfied by f(x), and if possible, an explicit expression in terms of known functions.

Note that

C = ∫_{0}^{1} f(x) dx ,

so an answer to Question 2 may settle Question 1.

Update Nov. 8, 2018: Christopher Ryba solved Question 2 . His elegant article appeared here:

https://arxiv.org/abs/1811.03440 .

A natural approach

The asymptotic expression for the naive counting of partitions, the famous partition function p(n), https://oeis.org/A000041, is the subject of the celebrated Hardy-Ramanujan-Rademacher formula (See [A], Ch. 6). The proof uses the Circle method, that uses the Euler generating function

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

This enables one to express p(n) as a contour integral.

The analogous generating function for our sequence of interest is obviously

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

It is possible that a similar proof (possibly easier, since we do not want the full asymptotics only the leading term) would solve Question 1.

Regarding b(n, k), we obviously have

∑_{n=0}^{∞} b(n, k) q^{n} = \frac{q^{k}/k}{(1 − q) (1 − \frac{q^{2}}{2} ) (1 − \frac{q^{3}}{3} ) ⋯ (1 − \frac{q^{k}}{k})} .

Once again this implies a certain contour integral expression for b(n, k) that may lead to an answer to Question 2.

A much easier question

If you look at partitions in frequency notation 1^{a_{1}} … n^{a_{n}} and give each of them ‘credit’

\frac{1}{(1^{a_{1}}a_{1}!) ⋯ (n^{a_{n}}a_{n}!)} ,

and define c(n) as the sum of these over all partitions of n, then we have

∑_{n=0}^{∞} c(n)q^{n} = e^{q/1} e^{q^{2}/2} e^{q^{3}/3} ⋯ = exp (∑_{i=1}^{∞} \frac{q^{i}}{i} ) = exp(−log(1 − q)) = \frac{1}{1 − q} ,

and it follows that c(n) = 1 for all n.

Recall that \frac{n!}{(1^{a_{1}} a_{1}!)···(n^{an} a_{n}!)} is famously the number of permutations of n whose cycle structure is 1^{a_{1}} … n^{a_{n}}, i.e. the number of permutations of n whose expression into a product of disjoint cycles has a_{1} fixed points, a_{2} cycles of length 2 etc. Recall the easy proof of that fact. If you order each of the cycle-lengths, then the number of ways of distributing n ‘balls’ into the a_{1} + … + a_{n} ‘boxes’ is the multinomial coefficient \frac{n!}{1!^{a_{1}} 2!^{a_{2}} ···n!^{an}}. Since the order of cycles of the same length does not matter, we have to divide by a_{1}! ⋯ a_{n}!, getting \frac{n!}{(a_{1}!1!^{a_{1}} )(a_{2}!2!^{a_{2}} )···(a_{n}!n!^{an})}. But each box with, say, r ‘balls’, can be arranged into (r − 1)! cycles hence the desired number has to be multiplied by 1!^{a_{2}}2!^{a_{3}} ⋯ (n − 1)!^{a_{n}} proving this fact, that goes back, at least, to Cauchy and Cayley. Since the total number of permutations of length n is n!, adding up, and dividing by n! gives a ‘combinatorial proof’ that c(n) = 1 for every n. These coefficients also famously feature in the cycle index polynomial of the symmetric group in Polya-Redfield theory. A much less famous occurrence, kindly pointed to us by Andrew Sills, is due to Major Percy A. MacMahon ([M], p. 61ff), where these are the coefficients in a certain ‘partial fraction decomposition’, that has been beautifully extended by Sills([Si]) into a multivariate identity.

Incidentally, the expression for c(n) is precisely the homotopy cardinality |X| = 1 of the ‘action groupoid’ X = S_{n} // S_{n} whose objects are permutations of n and whose isomorphisms are generated by the conjugation action of S_{n} on itself. Isomorphism classes of objects in S_{n} // S_{n} are represented by partitions (since two permutations are conjugate just in case they have the same cycle lengths), and the formula (1^{a_{1}}a_{1}!) ⋯ (n^{a_{n}}a_{n}!) gives the order of the automorphism group (≅ stabilizer subgroup for the conjugation action) of any permutation with cycle structure 1^{a_{1}} … n^{a_{n}}.

Another easy question

If you look at partitions in frequency notation 1^{a_{1}} … n^{a_{n}} and now give each of them ‘credit’

\frac{1}{(1!^{a_{1}}a_{1}!) ⋯ (n!^{a_{n}}a_{n}!)} ,

and define d(n) as the sum of these over all partitions of n, then we have

∑_{n=0}^{∞} d(n)q^{n} = e^{q/1!} e^{q^{2}/2!} e^{q^{3}/3!} ⋯ = exp (∑_{i=1}^{∞} \frac{q^{i}}{i!} ) = exp(exp(q) − 1)) = ∑_{n=0}^{∞} \frac{B_{n}}{n!} q^{n} ,

where B_{n} are the Bell numbers, https://oeis.org/A000110. So d(n) = \frac{B_{n}}{n!} . In particular,

∑_{n=0}^{∞} d(n) = e^{e−1} = 5.5749415247608806 …

is the homotopy cardinality of the groupoid whose objects are finite sets equipped with a partition and whose isomorphisms are partition-respecting bijections.

The beautiful work of Robert Schneider

While we believe that Questions 1 and 2 are new, it turns out that our kind of ‘fractional counting’ of partitions showed up recently in a remarkable PhD thesis, written by Robert Schneider ([Sc1], see also [Sc2]), where the sum of the reciprocals of squares (and more general powers) of the ‘product of the parts’, (that he calls the norm), taken over all partitions into even parts (and more generally multiples of m, for any m ≥ 2) are very elegantly expressed in terms of values of the Riemann Zeta function at integer arguments. We thank Andrew Sills for bringing this to our attention.

Epilogue: We need yet another On-Line Encyclopedia

In addition to the great OEIS ([Sl]) that lets you identify integer sequences, and the very useful “Inverse Symbolic Calculator” ([BP]) that lets you identify constants, it would be useful to have a searchable database of continuous functions defined (for starters) on 0 < x < 1, given numerically with, say, a resolution of 0.01, so each function will have 100 values in floating point. If such a data-base existed, Question 2 may have been answered (but one would need to go pretty far to get good approximations for f(x)).

Note Added Oct. 31, 2018: A few hours after the posting of this article in the arxiv, Will Sawin, Columbia University, solved Question 1. A donation to the OEIS, in his honor, has been made. Below is his argument.

Appendix: Solution to Question 1

Will SAWIN

In this appendix, we show that in the series

∑_{n=0}^{∞} b(n)q^{n} = ∏_{n=1}^{∞} \frac{1}{1 − \frac{q^{n}}{n}} .

we have

lim_{n→∞} \frac{b(n)}{n} = e^{−γ}

Let us choose c(n) so that we have

∑_{n=0}^{∞} c(n)q^{n} = (1 − q)^{2} ∏_{n=1}^{∞} \frac{1}{1 − \frac{q^{n}}{n}} .

We will show that

∑_{n=0}^{∞} |c(n)|

is bounded and that

∑_{n=0}^{∞} c(n) = e^{γ}.

The result will then follow because the coefficients of \frac{1}{1−q} ∑_{n=0}^{∞} c(n)q^{n} are the partial sums of ∑_{n=0}^{∞} c(n)q^{n} and so converge to e^{−γ}, and thus the coefficients of \frac{1}{(1−q)^{2}} ∑_{n=0}^{∞} c(n)q^{n}, which are the partial sums of those coefficients, are asymptotic to e^{−γ}n.

To understand c(n), using the formal identity

\frac{1}{1 − q} = ∏_{n=1}^{∞} e^{\frac{q^{n}}{n}} ,

we have

(1 − q)^{2} ∏_{n=1}^{∞} \frac{1}{1 − \frac{q^{n}}{n}} = (1 − q) ∏_{n=2}^{∞} \frac{1}{1 − \frac{q^{n}}{n}} = e^{−q} ∏_{n=2}^{∞} \frac{e^{− \frac{q^{n}}{n}}}{1 − \frac{q^{n}}{n}} .

Let us first evaluate this infinite product with 1 substituted for q. This is

e^{−1} ∏_{n=2}^{∞} \frac{e^{−1/n}}{1 − 1/n} = lim_{m→∞} [exp(∑_{n=1}^{m} −\frac{1}{n}) ∏_{n=2}^{m} \frac{1}{1 − \frac{1}{n}} ] = lim_{m→∞} [(exp(∑_{n=1}^{m} −\frac{1}{n})) · m]

= lim_{m→∞} exp(log m − ∑_{n=1}^{m} \frac{1}{n}) = e^{−γ} .

Now using the corollary

\frac{1}{1 − \frac{q^{n}}{n}} = ∏_{d=1}^{∞} e^{( \frac{q^{n}}{n})^{d}/d} ,

of the same formal identity, we see that the terms except e^{−q} in the infinite product have nonnegative coefficients . Because we have already shown that the infinite product converges, it converges also if we take the absolute value of each coefficient, and so ∑_{n=0}^{∞} |c(n)| is bounded (in fact by e^{2−γ} as taking absolute values of coefficients turns the e^{−q} term into e^{q}). Because the product and sums converge absolutely, the partial sums converge to the limit of the product.

This research was conducted while Will Sawin was a Clay Research Fellow.

[Update 10:30am, Nov. 2, 2018: Fernando Chamizo has independently solved the first question, with an even shorter rendition. It is available, with kind permission of Professor Chamizo, from

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/fcpFernandoChamizo.pdf .]

[Update 2:30pm, Nov. 2, 2018: Gjergji Zaimi kindly pointed out that Question 1 was posed and answered completely by D.H. Lehmer in Theorem 3 of his article

( http://matwbn.icm.edu.pl/ksiazki/aa/aa21/aa21123.pdf ) “On reciprocally weighted partitions”,

Acta Arithmetica XXI(1972), p. 379-388.]

[Update Nov. 6, 2018: Laurent Habsieger has independently solved the first question. It is available, with kind permission of Professor Habsieger, from

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/fcpLaurentHabsieger.pdf .]

References

[A] George Andrews, “The Theory of Partitions”, Cambridge University Press, 1984. Originally published by Addison-Wesley, 1976.

[BD] John Baez and James Dolan, From finite sets to Feynman diagrams, in B. Engquist and W. Schmid, editors, Mathematics Unlimited—2001 and Beyond, 29–50, Springer, 2001.

[BP] Jonathan Borwein, Simon Plouffe et. al, The Inverse Symbolic Calculator,

https://isc.carma.newcastle.edu.au/ .

[FGZ] Jane Friedman, Ira Gessel and Doron Zeilberger, Talmudic lattice path counting, J. Combinatorial Theory (ser. A) 68 (1994), 215–217. Available from

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/talmud.html .

[M] Percy Alexander MacMahon, “Combinatory Analysis, vol. II,” Cambridge Univ. Press, 1916.

[Sc1] Robert Schneider, “Eulerian series, zeta functions and the arithmetic of partitions”, Ph.D. thesis, 2018. Available from

http://www.mathcs.emory.edu/~rpschne/ [accessed Oct. 26, 2018] .

[Sc2] Robert Schneider, Partition Zeta Functions, Research in Number Theory (2016) 2:9.

[Si] Andrew Sills, The combinatorics of MacMahon’s partial fractions, Annals of Combinatorics, to appear.

Available from

http://home.dimacs.rutgers.edu/~asills/MacMahon/MacMahon2017.pdf .

[Sl] Neil James Alexander Sloane, The On-Line Encyclopedia of Integer Sequences,

https://oeis.org .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil@gmail.com .

Noam Zeilberger, School of Computer Science, University of Birmingham, Birmingham, UK.

Email: noam.zeilberger@gmail.com .

First Written: Oct. 30, 2018. This version: Nov. 6, 2018.