By Doron Zeilberger
[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
.pdf
.ps
.tex
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