Symbolic Moment Calculus I: Foundations
and Permutation Pattern Statistics

Doron Zeilberger

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

zeilberg@math.rutgers.edu

Annals of Combinatorics 8 (3) p.369-378 September, 2004

Abstract:

The old workhorse called * linearity
of expectation*, by which it is often very easy to compute the expectation
(alias first moment) of interesting combinatorial quantities, can also be used
to compute higher moments, as well as correlations, but then things get very
soon too complicated for mere humans. The computer, used as a symbol-cruncher,
can go much further (alas, only by a few orders of magnitude). In this article,
a methodology for using Computer Algebra Systems to *automatically* derive
higher moments of interesting combinatorial random variables is described, and
applied to Pattern Statistics of permutations. This would be hopefully followed
by sequels applied to other combinatorial objects like graph-colorings, Boolean
functions, and Random Walks. In addition to the intrinsic interest that the
actual results might have, it is also hoped that this work will serve as as
an *illustrative example* for conducting reliable mathematical experiments that
lead to completely rigorous results, by an Overlapping Stages approach.

References:

1. N. Alon and J.H. Spencer, The Probabilistic Method, 2nd Ed., Wiley, New York, 2000.

2. M. Bona, Combinatorics of Permutations, Chapman-Hall and CRC, Boca Raton, to appear.

3. J. Borwein and D. Bailey, Mathematics by Experiment, A.K. Peters, Natick, 2004.

4. P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947) 292--294.