Counting Young Tableaux
of Bounded Height*
François
Bergeron, and Francis Gascon
-
We show that formulas of Gessel, for the generating functions
for Young standard tableaux of height bounded by k (see [2]),
satisfy linear differential equations, with polynomial coefficients, equivalent
to P-recurrences conjectured by Favreau, Krob and the first author
(see [1]) for the number of bounded height tableaux
and pairs of bounded height tableaux.
Results
Let us first fix some notation. A partition of a positive integer 
is a sequence of positive integers
such that
We denote 
this fact, and say that 
is the height of 
.
The (Ferrers) diagram of a partition is the set of points
Clearly a partition is characterized by its diagram. The conjugate of
a partition is the partition with diagram
A Young standard tableau 
of shape
is an injective labeling of the Ferrers diagram of
by the elements of the set 
,
such that 
and 
when 
and 
.
For a given
, the number of tableau of shape
is given by the formula
where )
runs over the set of points in the diagram, and the hook length is defined
as
Other classical results in this context are
and
We are interested in the enumeration of tableaux of height bounded by some
integer ,
this is to say that we want to compute the numbers
as well as
For example, the first few sequences )
are
See sequences M0769, M1184, M1212 in [5]. For )
,
we have
See sequences M1459, M1666 in [5].
In [2] Gessel deduces, from a result of Gordon,
the following formulas
and
where
and
if
is positive integer, J-k = Jk and
I-k=
Ik.
However the resulting expressions rapidly become unwieldy. For example,
Using properties of Bessel functions, we can somewhat simplify these
in the following manner. Recalling the easily deduced relations
we get, after computation, the much simpler expressions
Similarly with the )
,
we get
A theoretical argument (see [2]) shows that the
generating functions )
and
are D-finite. This is to say that they satisfy linear differential
equations with polynomial coefficients. In fact, it is well known and classical
that one can translate such linear differential equations as recurrences,
with polynomial coefficients. More precisely, a P-recurrence for
a sequence 
is one of the form
We say that a sequence is P-recursive if it satisfies some
P-recurrence.
The class of P-recursive sequences is closed under point-wise product.
Since 
is easily seen to be P-recursive, it follows that, if
is
P-recursive then so are 
and 
.
The algorithmic translation from
D-finite to P-recursive
(and back) has been implemented in the package
gfunin Maple (see
[4]), as well as many other nice tools for handling
recurrences and generating functions.
Computer experiments made by Krob, Favreau and the first author led
to conjectures (see [1]) for an explicit form for
P-recurrence
for
and .
These conjectures can easily be (automatically) reformulated as linear
differential equations for
and .
We first observe that it is not to hard to show the existence of a polynomial
coefficients linear differential equation of order bounded by
admitting
as a solution. In fact, this follows readily from the following proposition.
Proof. Setting 
,
it is clear from our previous discussion that
lies in the span 
of the set of 
elements:
if
is even, and
if
is odd. Now,
is clearly closed under derivation, since we easily see that
from which we deduce that
as well as a similar expression for the derivative of 
.
Thus, 
is contained in ,
and hence its dimension is bounded by .
Setting for the moment, 
it clearly follows from the proposition above, that
hence
satisfies a homogeneous linear differential equation of order
with coefficients polynomials in 
.
However, a sharper relation seems to hold. In fact, we conjecture that
The first few cases
are
Equating coefficients of 
on both hand sides of these differential equations, one finds that they
are equivalent to the recurrences
Up to now, only these recurrences (meaning for 
),
have been implicitly known (see [3]). However, using the simplified expressions
for
given here, and a reformulation in term of linear differential equations,
with the help of gfun, we have been able to check (in the form of
a computer algebra proof) that the conjecture above is true for 
,
thus it follows that the corresponding recurrences hold. This computer
verification simply uses the derivation rules (1) for 
to simplify the expressions obtained by substitution of Gessel formulas
in the following differential equations.
However, these verifications rapidly become (computer) time consuming,
since, for example, we have to simplify the result of substituting in the
differential equation
the following expression
Similar considerations for the
case, with the differential equations below, settle the corresponding conjectures
for 
.
Acknowledgement
The Maple package gfun(available
as a shared library) was used extensively in the elaboration of the conjectures
and results in this note.
References
-
[1]
-
F. Bergeron,
L. Favreau and D. Krob, Conjectures on the Enumeration of Tableaux of
Bounded Height, Discrete Math.,
139, (1995), 463-468.
-
[2]
-
I. Gessel, Symmetric Functions and P-Recursiveness,
Jour.
of Comb. Th., Series A,
53, 1990, 257-285.
-
[3]
-
D. Gouyou Beauchamps, Codages par des mots
et des chemins: problèmes combinatoires et algorithmiques, Ph.
D. thesis, University of Bordeaux I, 1985.
-
[4]
-
B. Salvy and P. Zimmermann, GFUN: A maple Package
for the Manipulation of Generating Functions in one Variable, ACM Trans.
in Math. Software,
20, 1994, pages 163-177.
-
[5]
-
N.J.A Sloane and S. Plouffe, The Encyclopedia
of Integer Sequences, Academic Press, 1995.
Footnote: *With
support from NSERC and FCAR.