Enumerative and Algebraic Combinatorics

Doron ZEILBERGER ^{1}

Enumeration (alias counting) is the oldest (mathematical) profession, while Algebraic Combinatorics is one of the youngest mathematical subjects. Indeed, only about ten years ago did the American Mathematical Society, in its official taxonomy of mathematics called ‘Mathematical Subject Classification’ add Algebraic Combinatorics to its list of official subjects, attaching to it the code name 05E, thereby setting it apart from the traditional ‘Enumerative Combinatorics’, whose code-name is 05A.

Is Algebraic combinatorics really a new subject, or is it just a new, fancy, name contrived for image-enhancing purposes, in an attempt to gnetrify a subject that used to be the slums of mathematics? The truth is somewhere in the middle. Algebraic combinatorics is the synthesis of two opposing trends: abstraction of the concrete and concretization of the abstract. Starting at the beginning of the 20th century, mathematics became more and more abstract, and there was a trend everywhere towards categorization, conceptualization, and fancification. Enumerative combinatorics did not escape this trend, and in the hands of such giants as Gian-Carlo Rota and Richard Stanley in America and Marco Schützenberger and Dominique Foata in France, classical, enumerative, combinatorics became more conceptual and algebraic. On the other side, staring at the last third of the 20th century, and inspired by the great power of electronic computers, there is a general trend in mathematics towards the explicit, and concrete, and a shift from the merely existential to the constructive. It turned out that many algebraic structures have natural combinatorial structures behind them, and it became necessary to understand these combinatorial structures and their relation to algebra, topology, and other parts of mathematics.

I. Enumeration

The Fundamental Theorem of Enumeration, probably independently discovered by several anonymous cave-dwellers (c. 100,000 B.C.) states

Thm (Anon.)

|A| = ∑_{a∈A} 1 .

It is still useful after all these years. As math became more abstract, algebra was invented, and hence symbolism. It was no longer respectable to count specific sets (this was left to accountants and census takers), and in order to qualify as mathematics a theorem had to be true for infinitely many cases. In order to account for infinitely many cases one used parameters, and the generic enumeration problem became:

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg@math.rutgers.edu , http://www.math.rutgers.edu/~zeilberg/.

First version: Jan. 25, 2004 . Supported in part by the NSF.

Given an infinite sequence of sets {A(n)}_{n=0}^{∞}, parameterized by positive integer n, of objects satisfying a set of combinatorial specifications, answer the following Question: What is a(n) := |A(n)|? But before we can learn how to answer this kind of questions, let’s consider a Meta-Question: What is an Answer? This meta-question was posed, and beautifully answered, in 1982, by Herbert Wilf. I will tell you Wilf’s meta-answer in a little while, but let’s first examine answers to some famous instances of enumeration questions.

1. (I Ching) If A(n) is the set of subsets of {1, …, n}, then a(n) = 2^{n}.

2. (Levi Ben Greson) If A(n) is the set of permutations on {1, …, n}, then a(n) = n!.

3. (Catalan) If A(n) is the set of complete binary trees with n leaves, then a(n) = \frac{(2n−2)!}{(n−1)!n!}.

4. (Leonardo of Pisa) If A(n) is the set of words in the alphabet {1, 2} that sum to n, then we have three answers. (i)

a(n) = \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{n+1} − (\frac{1 − \sqrt{5}}{2})^{n+1}) .

(ii)

a(n) = ∑_{k=0}^{n/2} \binom{n − k}{k} .

(iii) a(n) = F_{n+1}, where F_{n} is the sequence defined by the recurrence F_{n} = F_{n−1} + F_{n−2}, subject to the initial conditions F_{0} = 0, F_{1} = 1.

5. (Cayley) If A(n) is the set of labeled trees on n vertices, then a(n) = n^{n−2}.

6. If A(n) is the set of labeled simple graphs on n vertices, then a(n) = 2^{n(n−1)/2}.

6. If A(n) is the set of labeled connected simple graphs on n vertices, then a(n) is n! times the coefficient of x^{n} in the power series expansion of

log (∑_{k=0}^{∞} \frac{2^{k(k−1)/2}}{k!} x^{k}) .

7. If A(n) is the number of Latin Squares of size n (n × n matrices each of whose rows and column is a permutation of {1, …, n}), then a(n) =???.

8. If A(n) is the number of Self-Avoiding Walks on n steps, on the two dimensional square lattice (walks, starting at the origin, say, with unit steps either North, South, East, and West, such that no point gets visited more than once, for example SSEENW is self-avoiding, but SSENWW is not), then a(n) =???.

Herb Wilf defined an answer as follows.

Definition (Wilf [Wi]) An answer (at least a publishable one) is a polynomial-time algorithm (in n) for computing a(n).

Wilf arrived at this definition after he refereed a paper proposing a ‘formula’ for the answer to question 7, and realizng that its ‘computational complexity’ exceeds that of the caveman’s formula of direct counting.

What is a ‘formula’? It is really an algorithm that inputs n and outputs a(n). For example a(n) = 2^{n} is shorthand for the recursive algorithm:

if n = 0 then output 1 else output 2a(n − 1).

That takes O(n) steps. However by using the more clever algorithm

if n = 0 then output 1, if n is odd, output 2a(n − 1), if n > 0 is even output a(n/2)^{2},

that takes O(log n) steps.

Hence sometimes one can get a polynomial-time algorithm in the bit size, i.e. poly-log, in which case Wilf’s definition is too permissive. In other cases, like enumerating Self-Avoiding walks, where the best known algorithm is exponential O(c^{n}), devising a new exponential-time algorithm with a smaller constant is definitely of interest, so in this case Wilf’s answer to ‘what’s an answer?’ is too harsh. But as a general guiding principle, it is valid.

The Customers of Enumeration

The old customers are probability and statistics. In fact discrete probability is almost synonymous with enumerative combinatorics, since the probability of an event E occurring is the ratio of the number of successful cases divided by the total number. Alas, because enumeration is so hard, discrete probability gave way to continuous probability, where one gets away with hand-waving analysis, asymptotics and approximation. Statistical Mechanics is yet another customer, since the Gibbs Partition function of models like the Ising model is really the limit of weightenumerators of combinatorial sets.

About forty years ago, another important customer came along: computer science, where one is interested in computational complexity of algorithms, that is in the number of steps it takes to execute algorithms.