Symbolic Moment Calculus I.: Foundations and Permutation Pattern Statistics

By Doron Zeilberger

.pdf   .ps   .tex

[Appeared in Annals of Combinatorics 8(2004), 369-378.]

Written: Jan. 11, 2004.

Our Sages, blessed be their memory, said: Send thy bread upon the water, since one day you shall find it. Computer Algebra Systems enable us to answer so many questions that before we didn't even dare ask, since there was no way we could do them by hand. So let's find out, even if we don't see right away `what it is good for?'. Don't worry, at least some of it, will be good for humanly `interesting' questions, and if not, so what? The act of programming will enhance our computer skills, and it is fun to get all these new general theorems, that are awesome, exactly because no humans can find them by themselves.

But, to be honest, I do have an `hidden agenda'. To improve the dismal lower bounds obtained by the Probablistic Method, whose first step involves computing the expectation, alias first moment. By automatically computing (symbolic!) expressions for higher moments, who knows? may be we can do better?

In this article I propose the methodology and apply it to Pattern statistics of permutations. These are not directly relevant to the probabilstic method, but the skill that I acquired hopefully will enable me, (or you!, if you read this paper carefuly), to apply it for improving the asymptotic lower bounds on Ramsey and other interesting combinatorial numbers.

SMCper, that automatically computers expression for variances, covariances, correlations, and higher moments for random variables counting the number of occurrences of patterns in permutations

## SAMPLE Input and Output Files

For Exact Expressions for the Third Moment about the mean for patterns of length 3: input     output.

For Asymptotic Expressions for all the variances for patterns of length 3 (divided by n**2): input     output.

For Asymptotic Expressions for all the variances for patterns of length 4 (divided by n**3): input      output.

For Asymptotic Expressions for all the variances for patterns of length 5 (divided by n**4): input     output.

For Asymptotic Expressions for all the variances for patterns of length 6 (divided by n**5): input     output.

For Asymptotic Expressions for all the variances for patterns of length 7 (divided by n**6): input     output.

For Asymptotic Expressions for all the variances for patterns of length 8 (divided by n**7): input     output.

For Asymptotic Correlations between patterns of the same length: input     output.

For Asymptotic Correlations between patterns of different lengths: input     output.