Using GENERATINGFUNCTIONOLOGY to Enumerate DistinctMultiplicity Partitions
By
Doron Zeilberger
.pdf
.ps
.tex
(Exclusively published in the Personal Journal of
Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)
Written: Jan. 18, 2012
Last Update of this page (but not article): Sept. 11, 2012 [Thanks to Daniel Kane and Robert Rhoades]
Previous Updates: Feb. 1, 2012 [thanks to Daniel Kane], Feb. 4, 2012 (page and article) [Thanks to Vaclav Kotesovec],
Feb. 8, 2012 [Thanks to Mark Ward]
In Fond Memory of
Herbert Saul WILF (June 13, 1931 Jan. 7, 2012),
Who asked so many good questions,
and knew so well what is an ANSWER
ל ע ל ו י נ ש מ ת ו ש ל
ה ר ב ר ט ש א ו ל ו י ל ף
(
כ" ח ס י ו ן ה' ת ר צ"א  י"ב ט ב ת ה' ת ש ע"ב )
ז כ ר ג א ו ן ל ב ר כ ה
ש ש א ל ש א ל ו ת כ ל
כ ך ט ו ב ו ת
ו י ד ע ה י ט ב מ ה ז א ת
ת ש ו ב ה
Added Feb. 1, 2012: Daniel Kane seems to have found the true asymptotics of log f(n),
see the end of the current version of the article. As soon as Daniel would write it up,
I will put a link to it here. Meanwhile, he kindly allowed me to post his
Email message .
Added Feb. 4, 2012: According to Vaclav Kotesovec's numerics, Daniel Kane's proposed asymptotics does not seem to quite
fit, as stated (but the n^{1/3} part may still be right). See
Vaclav Kotesovec's graph .
Added Feb. 8, 2012: Mark Ward, in collaboration with Jim Fill and Svante Janson also found (private communication,
see Mark Ward's Email message)
the same asymptotics as Daniel Kane
(so it must be correct, apparently 508 terms do not suffice to see what is going on exactly)
and are working on refined asymptotics. I hope that they would join forces, and as soon as the article is posted
in the arxiv (and/or their websites), I will link to it here.
Added Sept. 11, 2012:
Daniel Kane and Robert Rhoades found a
more refined asymptitics!
Maple Package

DMP
[Version of Jan. 25, 2012, adding procedure RandDMP]
A Maple package for automatically generating the generating function for enumerating
integer partitions with distinct multiplicities whose parts are drawn from any given finite
set of positive integers, and for computing the beginning of the hardtocount
sequence enumerating unrestricted partitions with distinct (nonzero) multiplicity.
Webbooks

If you want to see the first 250 terms of
OEIS sequence A098859, the number of
partitions of an integer n with distinct multiplicities,
computed from scratch, the
input file
would yield the
output file

If you want to see the generating function, in q, a certain rational
function such that when you take its Maclaurin expansion, the coefficient
of q^{n} tells you the number of ways of making change from n cents
if you are allowed any number of pennies, nickels, dimes, and quarters,
such that you can't have the same number of coins of two different
denominations (if they do occur in the change, of course it is OK to have,
e.g., no pennies and no quarters), as well as the first 300 terms of this sequence, then the
input file
would yield the
output file

If you want to see the analog of the above
but now you are allowed to use halfdollars and dollarcoins in addition
to pennies, nickles, dimes, and quarters, and with the first 1000 terms of the sequence
input file
would yield the
output file

If you want to see the (rational, as it turns out, see the paper) generating functions
for multiplicityfree partitions whose largest part is m, for each of 1 ≤ m ≤ 8,
as well as the first 200 terms for each enumerating sequence
the
input file
would yield the
output file

If you want to see the first 508 sequences of the sequence, using Maciej Ireneusz Wilczynsk's precomputed table
Maciej Ireneusz Wilczynsk's precomputed table,
as well as comparing them to the unrestricted partitions, and a numerical estimate of the
asymptotics,
the
input file
would yield the
output file

[Added Jan. 25, 2012]
If you want to see ten (uniform) random distinctmultiplicity
partitions of 100, using the Wilf methodology for random selection
of random objects beautifully described in the NijenhuisWilf
classic text "Combinatorial Algorithms",
the
input file
would yield the
output file
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page