<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue3" %>
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
Annals of Combinatorics 8 (3) p.369-378 September, 2004
AMS Subject Classification: 05A05
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.
Keywords: restricted permutations, automated combinatorics, Wilf equivalence


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.