Written: Oct. 25, 2002
Mathematicians are often amazed that certain mathematical objects (numbers, sequences, probability distributions, functions, representations, etc.) show up so often.
For example, in enumerative combinatorics we encounter the Fibonacci and Catalan sequences in many problems that seem to have nothing to do with each other. Henry Gould has a very long bibliography on these celebrated sequences, and more recently, Richard Stanley in his classic "Enumerative Combinatorics, vol. 2" had 66 distinct occurrences of the Catalan sequence, and his Catalan website keeps on expanding, and currently has 30 more instances. Other examples, of the `Ubiquity phenomenon' (or `Universality') are root systems that show up almost everywhere, Schur functions, Bessel functions, classical orthogonal polynomials, the classical probability distributions (as well as, more recently, the amazing Tracy-Widom distribution), and the Painleve transcendents.
The question then arises to `explain' and `understand' this ubiquity phenomenon. Very often one goes to excruciating lengths of find a `natural' bijection between two equinumerous combinatorial families, and what results is an `explanation' with very little explanatory power.
The facile, and usually wrong, meta-explanation to the ubiquity phenomenon is `just coincidence', like in `six-degrees-of-separation'. That what the skeptics told John McKay when he discovered Moonshine.
A better explanation for the ubiquity of ubiquity is a conceptual analog of Zipf's law in linguistics. Recall that Zipf's law states that the frequency of a word is inversely proportional to its frequency ranking. Hence it makes sense that the most frequently occurring object in a mathematical family will show up rather frequently.
But, why these particular sequences?, and not others? Why are the powers of 2, the Fibonacci numbers, and the Catalan numbers as common as `if and it'? Why is 2**n more frequent then 3**n, which, in turn, is much more frequent than 5**n? Why is Catalan much more common than Motzkin, which in turn is much more common than Fine?
The answer, once again, is our human predilection for triviality, or more politely, simplicity. 2**n, Fibonacci, and Catalan are the simplest (according to natural criteria) in their class. Since human research, by its very nature, is not very deep, it makes sense that these sequences will show up again and again.
For example, 2**n is the simplest sequence whose generating function is a genuine rational function (and the sequence itself is not a polynomial of n). The Fibonacci sequence is the simplest sequence (that is not a quasi-polynomial) whose generating function is a reciprocal of a non-linear polynomial in the generating variable. The Catalan sequence is the simplest sequence whose generating function is a (genuine) algebraic formal power series, and so on.
It is very possible that analogous explanations exist for the ubiquity of root systems, the Poisson and Normal distributions and countless other `amazing coincidences'.
Doron Zeilberger's Homepage