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.

IMPORTANT: This article is accompanied by the Maple package

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

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.

Doron Zeilberger's List of Papers