By Shalosh B. Ekhad and Doron Zeilberger
(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)
Written: March 21, 2014
Last Update: March 31, 2014 [Thanks to Cheyne Homberger]
The famous Catalan Numbers count zillions of combinatorial families (see Richard Stanley's compendium), and humans have fun trying to find `nice' bijections between family A and family B. While this may be fun for a while, sooner or later this game gets old, especially, since the real reason Catalan numbers are so ubiquitous is their simplicity (see DZ's 49-th opinion), and that humans can only grasp simple things.
According to that opinion, the reason for the ubiquity of the sequence of Catalan numbers, let's call them c(n), is that their generating function
C(z):=∑_{n ≥ 0} c(n)z^{n}
satisfies the SIMPLEST possible (non-linear) algebraic equation
C(z)=1+zC(z)^{2} ,
that is equivalent to the quadratic recurrence
c(n)=∑_{1 ≤ k ≤ n} c(k-1)c(n-k) , c(0)=1 .
Often, the members of the combinatorial family in question posses natural `statistics', for example for Dyck paths, the number of `inversions' (U (not necessarily immediately) ahead of D), or for 132-avoiding permutations, the number of occurrences of a given pattern, then it may happen that two different statistics amazingly have the same average! Wow! Let's find a bijection! (see e.g. this humanly-generated paper that appeared in the very prestigious and very selective Electronic journal of Combinatorics, that only accepts "the best papers".)
Humans can, with some effort, find closed-form expressions for the average (aka expectation, aka first moment), and if they try really hard, may be able to find the variance (aka second moment), but beyond that they should enlist their much superior silicon brethrern, and develop algorithms for discovering (and proving!) closed-form expressions for as many as possible moments. In addition to its intrinsic interest, it would also indicate whether the combinatorial statistic (`random variable') in question seems to be `asymptotically normal' (if the standardized moments, starting with the third, converge, as n goes to ∞, to 0,3,0,15,0,105,.. the famous moments of the normal distribution), or whether it is DEFINITELY not normal (if the expression for the skewness (aka as standardized 3rd moment) does not tend to zero, we are done!)
In this collaboration between a human (DZ) and computer (SBE) we do just that. The human wrote a Maple package, that once and for all can handle zillions of possible statistics defined on Catalan-families, and surprise-surprise, prove (rigorously!) asymptotic ABNORMALITY, by deriving (and proving!) closed-form expressions for the skewness, that turn out NOT to tend to zero, and at the same time derive both exact (and hence asymptotic) expressions for many higher moments.
It is true that, with great effort, by very smart humans, like Svante Janson, (e.g. this nice human-generated article) can do it by entirely human means, but they can only do the leading asymptotics! Not even Svante Janson can find, just by hand, e.g., an EXACT closed-form expression, in n, for the sixth moment of the random variable `number of occurrences of the pattern 213' in the set of 132-avoiding permutations.
But do we really care about the 6th moment of some stupid statistic defined on some stupid family of sets? Of course not! The Medium is the Message! This article is but a case-study in human-computer collaboration. The human teaching the computer how to do every conceivable problem in a wide class of combinatorial problems, by the human designing algorithms, then implementing them, and then letting the computer execute them. Once we get better and better at this kind of collaboration, we would be ready for the big time! Stand by (in 100 years or less) for a computer-generated proof of RH and NP ≠ P.
Added March 31, 2014: Cheyne Homberger just alerted me that the $100 conjecture (due to Kate Rudolph) that I made in the paper has already been solved (published a few days before this article) by Lynn Chua and Krishanu Roy Sankar, see their nice paper (that unfortunately was not in arxiv.org, or else we would have probably seen it). I have just made the donation, see here.
"total number of occurrences of a pattern p amongst all 132-avoiding permutations of length n"
for ALL patterns p of length 2 and 3
(BTW, the human Miklos Bona was only able to do the first moment in this
paper, that was published
in the very prestigious and very selective Electronic journal of Combinatorics).
the input
yields
the output
"number of occurrences of the pattern 213 in the set of permutations of length n avoiding the pattern 123",
the first moment (times the Catalan numbers C(n)) [reproducing much faster one of the main results in
Cheyne's Homberger's article],
the second moment (times the Catalan number C(n)), and a linear recurrence
equation of order 4 with polynomial coefficients of degree 4 for the
third moment (times C(n))
the input
yields
the output
"number of occurrences of the pattern 213 in the set of permutations of length n avoiding the pattern 123",
for n from 0 to 35,
the input
yields
the output
indicating that it is asymptotically ABNORMAL (since the skewness does not seem to tend to 0, neither the kurtosis to 3. BTW, with some effort, this can be proved rigorously, but we have better things to do!)