Using Rota's Umbral Calculus to Enumerate Stanley's P-Partitions
By Shalosh B. Ekhad and Doron Zeilberger
.pdf
.ps
.tex
[Appeared in Advances in Applied Mathematics v. 41 (2008), 206-217.]
Dedicated to Two Combinatorial Giants:
Gian-Carlo Rota ז צ " ל
(April 27, 1932-Apri 18, 1999)
and
Richard Stanley ש ל י" ט א
(b. June 23, 1944)
Written: June 12, 2007.
I didn't contribute anything for Gian-Carlo Rota's 64th birthday collection
or Richard Stanley's 60th birthday
collection, since at the time I didn't have anything relevant,
and I don't like to submit
a paper that is not closely related to the research interests of the honorees.
So this paper is my belated present to these two heroes of mine, and my
coauthor, Shalosh B. Ekhad, really enjoyed computing these lovely brainchildren
of Richard Stanley
using Gian-Carlo Rota's powerful method of the Umbral Calculus.
Important: This article is accompanied by Maple
package
RotaStanley that computes generating functions enumerating
P-partitions (in the sense of Stanley) directly, and more impressively,
indirectly, using Rota's Umbral Calculus as it is described in this
article.
Even more impressively, it finds computer-generated functional
recurrences for generating functions of P-partitions for
families of posets that are obtained by repeated "grafting".
Sample Input and Output For Generating Functions
of P-partitions for Specific Posets
-
In order to compute the generating functions (in q) for the
Boolean Lattices of dimensions n=1,2,3, the
input would yield the
output
-
In order to compute the generating function for P-partitions for
the lattice of partitions into distinct parts with largest part less than equal to n,
for n=1, 2,3,4, the
input would yield the
output
-
In order to compute the generating function for P-partitions for
the Gaussian Lattice G(a,b) (the lattice of partitions into at most
b parts, with each part at most a)
for a,b between 2 and 3, the
input would yield the
output
-
In order to compute the generating functions, and first few terms, for
solid partitions who live in a 2 by 2 by n by infinity box with n between 2 and 5,
the
input would yield the
output
-
In order to compute the generating functions, and first few terms, for
stair-case shapes (going in either direction), the
input would yield the
output
Sample Input and Output For Functional-Recurrences
for Generating Functions
of P-partitions for Powers of a Given Poset
Below are a few examples of computer-generated
functional-recurrence equations for powers of given posets.
Note that these are fully general theorems. We use
procedure UmbralRecurrenceSingle of the package RotaStanley.
-
In order to get the functional-recurrence equation for
powers of the two-dimensional Boolean-lattice (alias diamond)
where the last vertex of the previous
link is identified with the first one of the next,
the
input would yield the
output
-
In order to get the functional-recurrence equation for
powers of the two-dimensional Boolean-lattice (alias diamond)
where the last two vertices of the previous
link are identified with the first two of the next,
the
input would yield the
output
-
In order to get the functional-recurrence equation for
powers of the poset that is a 2-rowed tableau each
row with 3 cells, and the bottom row is shifted one
cell to the left,
where the last three vertices of the previous
link are identified with the first three of the next,
the
input would yield the
output
-
In order to get the functional-recurrence equation for
powers of the poset that is a 2-rowed tableau each
row with 3 cells, and no shift,
where the last three vertices of the previous
link are identified with the first three of the next,
the
input would yield the
output
-
In order to get the functional-recurrence equation for
powers of the poset that is a 2-rowed tableau each
row with 3 cells, and the bottom row is shifted one
cell to the right,
where the last three vertices of the previous
link are identified with the first three of the next,
the
input would yield the
output
-
In order to get the functional-recurrence equation for
powers of a certain hexagon
where the last vertex of the previous
link is identified with the first vertex of the next,
the
input would yield the
output
-
In order to get the functional-recurrence equation for
powers of a certain hexagon
where the last two vertices of the previous
link are identified with the first two vertices of the next,
the
input would yield the
output
-
In order to get the functional-recurrence equation for
powers of another hexagon where the last vertex of the previous
link is identified with the first vertex of the next, the
input would yield the
output
-
In order to get the functional-recurrence equation for
powers of that other hexagon
where the last two vertices of the previous
link are identified with the first two vertices of the next,
the
input would yield the
output
Doron Zeilberger's List of Papers
Doron Zeilberger's Home Page