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’ equals 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.

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 is no ‘nice’ formulas, 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 Another special case of functional counting is f(x) := \frac{1}{x}. Fractional counting of lattice paths is dealt with in [FGZ], where stat(s) counts the number of times a path s intersects the diagonal. Baez and Dolan [BD] also studied a form of fractional counting called homotopy cardinality, where A_{n} is taken as the set of isomorphism classes for some family of objects and stat([a]) := |Aut(a)| is the order 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 …. 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. 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. 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’ (in the sense of [BD]) of the groupoid whose objects are finite permutations and whose isomorphisms are generated by conjugation.

Epilogue: We need yet another On-Line Encyclopedia

In addition to the great OEIS ([S]) 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)).

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 Mathematics Unlimited— 2001 and Beyond, Springer, 2001.

[BP] Jon 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 .

[S] N. J. A. 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 at gmail dot com .

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

Email: noam.zeilberger@gmail.com .

Written: Oct. 24, 2018.