Automatic Proofs of Asymptotic ABNORMALITY (and much more!) of Natural Statistics Defined on Catalan-Counted Combinatorial Families

Shalosh B. XIV Ekhad, Doron Zeilberger

Publication date: 22 March 2014

Abstract: In this case-study in computer-human collaboration, we develop, implement, and execute symbolic-computational algorithms for the automatic discovery and proof of explicit expressions for the expectation, variance, and higher moments of a large class of natural combinatorial statistics defined on Catalan-counted objects, enabling, inter-alia, to prove that they are not asymptotically normal. In particular, we reproduce in 0.12 seconds results of Miklos Bona, and derive far deeper results, way beyond the scope of humans, concerning higher moments of the random variable "number of occurrences of a pattern" in the set of 132-avoiding permutations for all patterns of length 2 and 3, and, more impressively, explicit expressions for the averages for all patterns of lengths up to 10. The ample output inspired us to make an intriguing conjecture concerning the number of so-called Bona classes, and we pledge to donate 100 dollars to the OEIS Foundation in honor of the prover (or disprover).

This page was built for publication: Automatic Proofs of Asymptotic ABNORMALITY (and much more!) of Natural Statistics Defined on Catalan-Counted Combinatorial Families