Enumerative and Algebraic Combinatorics

D. Zeilberger

Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA.

Enumeration, alias counting, is the oldest mathematical subject, while Algebraic Combinatorics is one of the youngest. Some cynics claim that Algebraic Combinatorics is not really a new subject but just a new name given to Enumerative Combinatorics in order to enhance its (former) poor image, but Algebraic Combinatorics is in fact the synthesis of two opposing trends: abstraction of the concrete and concretization of the abstract. The former trend dominated the first half of the 20th century, starting with Hilbert’s ‘theological’ proof of the fundamental theorem of invariants, while the latter trend is dominating contemporary mathematics, thanks in large part to Its Omnipresence, The Mighty Computer.

The abstraction trend, that consists of categorization, conceptualization, structuralization and fancification (in short ‘Bourbakisation’) of mathematics, did not escape enumeration, 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, structural and algebraic. On the other hand, the trend towards the explicit, concrete, and constructive revealed that many algebraic structures have hidden combinatorial underpinnings, and the attempts to unearth them lead to the other route towards the establishment of Algebraic Combinatorics as a full-fledged separate mathematical specialty.

Enumeration

The Fundamental Theorem of Enumeration, independently discovered by several anonymous cave-dwellers, states that

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

While this formula is still useful after all these years, enumerating specific finite sets is no longer considered mathematics. A genuine mathematical fact has to incorporate infinitely many facts, and the generic enumeration problem is:

Given an infinite sequence of sets {A(n)}_{n=0}^{∞}, parameterized by 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?

It was posed, and beautifully answered by Herbert Wilf. Before telling you Wilf’s meta-answer, 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}.

7. 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}) .

8. 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) =???.

In 1982, Herb Wilf defined an answer as follows.

Definition: An answer 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 8, and realizing 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 1 else 2a(n − 1)”, that takes O(n) steps. However using the algorithm: “if n = 0 then 1, else if n is odd, then 2a(n − 1), else, a(n/2)^{2}, takes O(log n) steps, much faster than Wilf demands. In other cases, like enumerating so-called Self-Avoiding Walks, where the best known algorithm is exponential, O(c^{n}), any lowering of the c is a major advance. Notwithstanding these exceptions, Wilf’s meta-answer is a very useful general guideline for evaluating answers.

The traditional customers of Enumeration were mainly 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. Also statistical physics is by and large weighted-enumeration of lattice models. About fifty 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.

METHODS

• Decomposition:

|A ∪ B| = |A| + |B| ,

( if A ∩ B = ∅)

|A × B| = |A| · |B| ,

|A^{B}| = |A|^{|B|} .

• Refinement: If

A(n) = ⋃_{k} B(n, k) (disjoint union) ,

and if b(n, k) := |B(n, k)| is ‘nice’ (and even if it isn’t), then

a(n) = ∑_{k} b(n, k) .

For example, the set A(n) of example 4, can be split into a disjoint union of the subsets B(n, k), consisting of those sequences with exactly k 2’s. Then there must be n − 2k 1’s and we have that b(n, k) equals \binom{n−k}{k}, yielding answer (ii).

• Recursion

Suppose that A(n) can be decomposed in such a way that it is a combination of fundamental operations applied to the sets A(n − 1), A(n − 2), …, A(0). Then a(n) satisfies an ‘explicit’ recursion

a(n) = P (a(n − 1), a(n − 2), …, a(0)) .

For example if A(n) is the set of ex. 4, then for any n ≥ 2,

A(n) ↔ A(n − 1) × {1} ∪ A(n − 2) × {2} ,

yielding answer (iii).

If A(n) is the set of (complete) binary trees on n leaves (ex. 3), then, by considering the number of leaves of the left subtree, we get A(n) = ⋃_{k=1}^{n−1} A(k) × A(n − k), and taking cardinalities, a(n) = ∑_{k=1}^{n−1} a(k) · a(n − k), a non-linear (quadratic) and non-local recurrence, but nevertheless one that satisfies Wilf’s dictum.

• Generatingfunctionology

According to Herb Wilf, who coined this neologism by making it the title of his classic book (a free download from his website, even though it is still in print!):

“A generating function is a clothesline in which we hang up a sequence of numbers for display”.

The method of Generating Functions is one of the most useful tools of the trade of Enumeration. The generating function of a sequence, sometimes called its z-transform, is a discrete analog of the Laplace Transform, and indeed goes back to Laplace himself.

{a_{n}}_{n=0}^{∞} → f(x) := ∑_{n=0}^{∞} a_{n}x^{n} .

Generating functions are so useful because information about a_{n} translates to information about f(x) that is often easier to process, getting additional information about f(x) that often translates back to information about the sequence. For example, a_{n} = a_{n−1} + a_{n−2} (n ≥ 2) together with the initial conditions a_{0} = 1, a_{1} = 1 translates to

f(x) := ∑_{n=0}^{∞} a_{n}x^{n} = a_{0} + a_{1}x + ∑_{n=2}^{∞} a_{n}x^{n} =

1 + x + ∑_{n=2}^{∞}(a_{n−1} + a_{n−2})x^{n} =

1 + x + ∑_{n=2}^{∞} a_{n−1}x^{n} + ∑_{n=2}^{∞} a_{n−2}x^{n}

1 + x + x ∑_{n=2}^{∞} a_{n−1}x^{n−1} + x^{2} ∑_{n=2}^{∞} a_{n−2}x^{n−2} =

1 + x + x(f(x) − 1) + x^{2}f(x) = 1 + (x + x^{2})f(x) .

Hence

f(x) = \frac{1}{1 − x − x^{2}} ,

that after performing a partial-fraction decomposition, and taylor-expanding the two resulting terms, would yield ans. (i) to ex. 4.

Weight-Enumeration

According to the modern approach, pioneered by Pólya, Tutte, and Schützenberger, generating functions are neither ‘generating’, nor are they functions. They are rather formal power series that are weight enumerators of (usually infinite) combinatorial sets.

Suppose that we want to study the age distribution of a finite population. One way would be to ask 121 questions. For each i between 0 and 120, we ask those whose age is i to raise their hand.

Then we count each of these age-groups one-by-one, compiling a table of a_{i}, (0 ≤ i ≤ 120), and finally computing the generating function

f(x) = ∑_{i=0}^{120} a_{i}x^{i} .

But if the size of the population is much less than 120, it would be much more efficient to ask every person their age and assign the weight of the person to be x^{age(person)}.

f(x) = ∑_{persons} x^{age(person)} ,

which is a natural extension of the caveman’s formula of naive counting. Once we have f(x) we can easily compute statistically interesting quantities, like the average, μ = f′(1)/f(1), and variance, σ^{2} = f′′(1)/f(1) + μ − μ^{2}.

The general scenario is that we have an interesting (finite of infinite) combinatorial set, let’s call it A and a certain numerical attribute: α : A → ℕ. Then the weight-enumerator of A w.r.t. to α is defined by

f(x) := |A|_{x} := ∑_{a∈A} x^{α(a)} .

Obviously, this equals

∑_{n=0}^{∞} a_{n}x^{n} ,

where a_{n} is the number of members of A whose α equals n. Hence if we have some kind of explicit expression for f(x), we immediately have an ‘explicit’ expression for the actual sequence a_{n} := Coeff_{x^{n}}f(x), that is, if one allows the operator ‘Coeff of x^{n}’ as a primitive (or equivalently, contour integrals in the complex x plane). Even if one doesn’t, then it is still often possible to get a ‘nice’ formula for a_{n}, and failing this, to extract the asymptotics, which is a deep current subspecialty in the hands of such masters as Ed Bender, Rod Canfield, Andrew Odlyzko, and the indefatigable Phillipe Flajolet.

The fundamental operations for naive counting also hold for weighted counting, just replace || by ||_{x}, to wit:

|A ∪ B|_{x} = |A|_{x} + |B|_{x} ,

( if A ∩ B = ∅) and

|A × B|_{x} = |A|_{x} · |B|_{x} .

For example, consider the infinite set A, of all words in {1, 2}, and let the attribute be ‘sum of entries’, so the weight of 1221. e.g., is x^{6}, and in general, weight(a_{1} … a_{r}) := x^{a_{1}+···+a_{k}}. The set A can be naturally decomposed as

A = {ϕ} ∪ 1A ∪ 2A ,

where ϕ is the empty word. Applying | · |_{x}, we get

|A|_{x} = 1 + x|A|_{x} + x^{2}|A|_{x} ,

which, in this simple case, can be solved explicitly, to yield, once again

|A|_{x} = \frac{1}{1 − x − x^{2}} .

A complete (ordered) binary tree is either the root alone (in which case it only has one vertex), or else the root has two children, called its leftchild and right-child, and the subtrees rooted at both of them are complete binary trees on their own right. A leaf is a vertex without children. Let B be the (infinite) set of all complete binary trees, and define the weight of such a tree to be x raised to the power ‘the number of leaves’. For example, the weight of () is x and the weight of (()(()())) is x^{3}. B decomposes naturally into

B = {·} ∪ B × B ,

which leads to the non-linear (quadratic) equation

|B|_{x} = x + |B|_{x}^{2} ,

that implies, thanks to the Babylonians, the explicit expression

|B|_{x} = \frac{1 − \sqrt{1 − 4x}}{2} ,

that in turn, via Newton’s binomial theorem, would yield the answer to ex. 3 above.

If instead of complete binary trees, where every vertex is allowed either zero or two children, we try to count penta-trees, where each vertex may only have exactly zero or five children, then the generating function, alias weight-enumerator, would satisfy the quintic equation

f = x + f^{5} ,

that according to Abel and Galois is not solvable by radicals. However the ansatz of solvability by radicals has its limitations. Count Joseph Lagrange, more than 200 years ago, devised a beautiful and extremely useful formula for extracting the coefficients of the generating function from the equation it satisfies, now called the Lagrange Inversion Formula. Using it one easily gets that the number of complete k-ary trees with (k − 1)m + 1 leaves is:

\frac{(km)!}{((k − 1)m + 1)!m!} .

A multivariate generalization of the Lagrange Inversion Formula, discovered by the great Bayesian probabilist I. J. Good, enables one to enumerate colored trees and many other extensions.

Enumeration Ansatzes

If one wants to turn Enumerative Combinatorics into a theory rather than a collection of solved problems, one needs to introduce classification, and enumeration paradigms for counting sequences. But since paradigm is such a pretentious word, let’s use the much humbler German word ansatz, that roughly means ‘form of solution’.

Let {a_{n}}_{n=0}^{∞} be a sequence, and let

f(x) = ∑_{n=0}^{∞} a_{n}x^{n} ,

be its generating function. If we know the ‘form’ of a_{n} we can often deduce the form of f(x) (and vice versa).

1. If a_{n} is a polynomial in n, then f(x) has the form

f(x) = \frac{P OLY (x)}{(1 − x)^{d+1}} ,

where d is the degree (in n) of the polynomial describing a_{n}.

2. If a_{n} is a quasi-polynomial in n (i.e. there exists an integer N such that for each r = 0, …, N − 1, a(mN +r) is a polynomial in m), then, for some (finitely-many ) integers d_{1}, d_{2}, …,

f(x) = \frac{P OLY (x)}{(1 − x)^{d_{1}}(1 − x^{2})^{d_{2}}(1 − x^{3})^{d_{3}} …} .

3. If a_{n} is C − recursive, i.e. satisfies a linear recurrence equation with constant coefficients (like the Fibonacci sequence)

a_{n} = c_{1}a_{n−1} + c_{2}a_{n−2} + ⋯ + c_{d}a_{n−d} ,

then

f(x) = RAT IONAL(x) = \frac{P OLY (x)}{P OLY (x)} .

4. If a_{n} is P − recursive, i.e. satisfies a linear recurrence equation with polynomial coefficients (e.g. a_{n} = n!):

c_{0}(n)a_{n} = c_{1}(n)a_{n−1}+c_{2}(n)a_{n−2}+⋯+c_{d}(n)a_{n−d} ,

where c_{i}(n) are polynomials in n, then f(x) is Dfinite, i.e. satisfies a linear differential equation with polynomial coefficients (in x) .

In the case of a_{n} = n! the recurrence is firstorder: a_{n} = na_{n−1}. A natural example of a P -recursive sequence satisfying a higher-order linear recurrence with polynomial coefficients is the sequence counting the number of involutions on {1, …, n} (i.e. permutations that equal their inverse), let’s call it {w_{n}}, that satisfies

w_{n} = w_{n−1} + (n − 1)w_{n−2} .

This recurrence follows from the fact that n is either in a 1-cycle, or in a 2-cycle, the former case accounting for w_{n−1} of the involutions, and the second for (n − 1)w_{n−2} of them (n − 1 ways of choosing the cycle-mate, i, say, of n, and deleting that cycle leaves an involution of the n−2 elements {1, …, i − 1, i + 1, …, n − 1}.

Bijective Methods

This last argument was a simple example of a bijective proof, in this case, of a recurrence for the number of involutions on n objects. Contrast this with the following proof.

The number of involutions of {1, …, n} with exactly k 2-cycles is \binom{n}{2k} \frac{(2k)!}{k!2^{k}}, because we must first choose the 2k elements that will participate in the k 2-cycles, and then match them up into (unordered) pairs, which can be done in (2k − 1)(2k − 3) ⋯ 1 = (2k)!/(k!2^{k}) ways. Hence w_{n} = ∑_{k} \binom{n}{2k} \frac{(2k)!}{k!2^{k}}. Nowadays such sums can be handled completely automatically, and if one inputs this sum to the Maple package EKHAD (downloadable from my website), one would get the recurrence w_{n} = w_{n−1} + (n − 1)w_{n−2} as the output, together with a (completely rigorous!) proof. While the so-called Wilf-Zeilberger (WZ) method can handle many such problems, there are even more cases where one still needs a human proof. In either case such proofs involve (algebraic, and sometimes analytic) manipulations. The great Combinatorialist Adriano Garsia derogatorily calls such proofs manipulatorics, and real enumerators do not manipulate, or at least try to avoid it whenever possible. The preferred method of proof is by bijection.

Suppose one has to prove that |A(n)| = |B(n)| for every n, where A(n) and B(n) are combinatorial families. The ‘ugly way’ is to get some (algebraic or analytic) expressions for a(n) := A(n), and b(n) := |B(n)|. Then one manipulates a(n) getting another expression a_{1}(n), which in turn leads to yet another expression a_{2}(n), and if one is patient enough, and clever enough, and in luck, or the problem is not too deep, one would hopefully arrive at b(n), and the result would follow from the transitivity of the equality relation.

On the other hand, the nice way of proving that |A(n)| = |B(n)| is by constructing (a preferably nice) bijection T (n) : A(n) → B(n), which immediately implies, as a corollary, that |A(n)| = |B(n)|.

In addition to being more aesthetically pleasing, a bijective proof is also philosophically more satisfactory. In fact the notion of (cardinal) number is a highly sophisticated derived notion based on the much more basic notion of ‘being in bijection’. Indeed, according to Frege, the cardinal numbers are equivalence classes, where the equivalence relation is ‘being bijective’. Saharon Shelah said that people have been exchanging objects, in a one-to-one way, long before they started to count. Also a bijective proof explains why the two sets are equinumerous, as opposed to just certifying the formal correctness of this fact.

For example, suppose that Noah wanted to prove that in his Ark, there were as many male as female creatures. One way of proving this was for him to actually have counted the number of males and the number of females, and check that these numbers are indeed the same. But a much better, conceptual, proof is to exhibit the bijection Males → F emales defined by ‘wife of’, whose inverse map F emales → Males is ‘husband of’.

A classic example of a bijective proof is Glashier’s proof of Euler’s Odd=Distinct partition theorem. A partition of an integer n is a way of writing it as a sum of positive integers, where order does not matter, hence for convenience’s sake it is written as λ_{1} … λ_{k} with λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{k} > 0, summing to n. For example, 6 has 11 partitions: 6, 51, 42, 411, 33, 321, 3111, 222, 2211, 21111, 111111.

A partition is called odd if all its parts are odd, and it is called distinct if all its parts are distinct. Let Odd(n) and Dis(n) be the sets of odd and distinct partitions of n respectively. For example Odd(6) = {51, 33, 3111, 111111} and Dis(6) = {6, 51, 42, 321}. Leonhard Euler proved that |Odd(n)| = |Dis(n)| for all n. His ‘manipulatorics’ proof goes as follows. Let o_{n} and d_{n} be the number of odd and distinct partitions of n respectively, and let’s define the generating functions f(q) = ∑_{n=0}^{∞} o_{n}q^{n} and g(q) = ∑_{n=0}^{∞} d_{n}q^{n}. Using the ‘multiplication principle’ for weighted counting, Euler noted that

f(q) = ∏_{i=0}^{∞} \frac{1}{1 − q^{2i+1}} ,

and

g(q) = ∏_{i=0}^{∞}(1 + q^{i}) .

Using the algebraic identity 1+y = (1−y^{2})/(1−y), we have

∏_{i=0}^{∞}(1 + q^{i}) = ∏_{i=0}^{∞} \frac{1 − q^{2i}}{1 − q^{i}} =

\frac{∏_{i=0}^{∞}(1 − q^{2i})}{∏_{i=0}^{∞}(1 − q^{2i}) ∏_{i=0}^{∞}(1 − q^{2i+1})}

= ∏_{i=0}^{∞} \frac{1}{1 − q^{2i+1}} .

Hence g(q) = f(q), and o_{n} = d_{n} follows by extracting the coefficient of q^{n}.

For a very long time, these kind of manipulations were considered to belong to the realm of analysis, and in order to justify the manipulations of the infinite series and products, one talked about the ‘region of convergence’, usually |q| < 1, and every step had to be justified by the appropriate analytical theorem. Only relatively recently people came to realize that there is no analysis involved, and every thing makes sense in the completely elementary and much more rigorous (from the philosophical viewpoint) algebra of formal power series. One still needs to worry about convergence, so as to exclude, for example, an infinite product like ∏_{i=0}^{∞}(1 + x), but the notion of convergence in the ring of formal power series is much more user-friendly than its analytical namesake.

Even though invoking analysis was a red herring, Euler’s proof, while purely algebraic and elementary, is nevertheless still manipulatorics. It would be much nicer to find a direct bijection between the set D(n) of distinct partitions and the set O(n) of odd partitions. Such a bijection was given by Glaisher. Given a distinct partition, write each of its parts as 2^{r} · s, where s is odd, and replace it by 2^{r} copies of s. The output is obviously a partition into odd parts of the same integer n. For example (10, 5, 4) goes to (5, 5, 5, 1, 1, 1, 1). To define the inverse, count for each odd part, a, how many times it shows up, say m times, write m in binary notation: m = 2^{s_{1}} + ⋯ + 2^{s_{k}}, and replace the m copies of a by the k parts : a·2^{s_{1}}, …, a·2^{s_{k}}.

When we perform algebraic (and logical, and even analytical) manipulations, we are really rearranging and combining symbols, hence doing combinatorics in disguise. In fact, everything is combinatorics. All we need to do is to take the combinatorics out of the closet, and make it explicit. The plus sign turns into (disjoint) union, the multiplication sign becomes Cartesian product, and induction turns into recursion. But what about the combinatorial counterpart of the minus sign? In 1982, Adriano Garsia and Steven Milne filled this gap by producing an ingenious ‘Involution principle’ that enables one to translate the implication

a = b and c = d ⇒ a − c = b − d ,

into a bijective argument, in the sense that if C ⊂ A and D ⊂ B, and there are natural bijections f : A → B and g : C → D establishing that a := |A| equals b := |B|, and c := |C| equals d := |D|, then it is possible to construct an explict bijection between A\C and B\D. Let’s define it in terms of people. Suppose that in a certain village all the adults are married, and hence there is a natural bijection between the set of married men to the set of married women, m → W ifeOf(m), with its inverse w → HusbandOf(w). In addition, some of the people have extra-marital affairs, (but only one per person, and all within the village). There is a natural bijection between the set of cheating men to the set of cheating women, called m → MistressOf(m), with its inverse w → LoverOf(w). It follows that there are as many faithful men as there are faithful women. How to match them up? (say if a faithful man wants a faithful woman to go to Church with him). A faithful man first asks his wife to come with him. If she is faithful, she agrees. If she is not, she has a lover, and that lover has a wife. So she tells her husband: sorry, hubby, but I am going to the pub with my lover, but my lover’s wife may be free, so the man asks the wife of the lover of his wife to go with him, and if she is faithful, she agrees. Is she is not he keeps asking the wife of the lover of the woman who just rejected his proposal, and since the village is finite, he will eventually get to a faithful woman.

The reaction of the combinatorial enumeration community to the Involution Principle was mixed. On the one hand it had the universal appeal of a general principle, that should be useful in many attempts to find bijective proofs of combinatorial identities. On the other hand, its universality is also a major drawback, since Involution Principle proofs usually do not give any insight into the specific structures involved, and one feels a bit cheated. Such a proof answers the letter of the question, but misses its spirit. In these cases one still hopes for a really natural, ‘Involution Principle- free proof’. This is the case with the celebrated Rogers-Ramanujan identity that states that the number of partitions of an integer into parts that leave remainder 1 or 4 when divided by 5 equals the number of partitions of that integer with the property that the difference between parts is at least 2. For example if n = 7 the cardinalities of {61, 4111, 1111111} and {7, 61, 52} are the same. Garsia and Milne invented their notorious Principle in order to give a Rogers-Ramanujan bijection, thereby winning a $50 prize from George Andrews. However, finding a really nice bijective proof is still an open problem.

A quintessential example of a bijective proof is Prüfer’s proof of Cayley’s celebrated result that there are n^{n−2} labeled trees on n vertices (ex. 5 above). Recall that a labeled tree is a labeled connected simple graph without cycles. Every tree has at least two vertices with only one neighbor (these are called leaves). The Prüfer bijection associates with every labeled tree T a vector of integers (a_{1}, …, a_{n−2}), with 1 ≤ a_{i} ≤ n. Since there are n^{n−2} such vectors, Cayley’s formula would follow once we define a mapping f : T rees → Codes and prove that it is indeed a bijection. This really entails four steps: defining f, defining its alleged inverse map g, and proving that g ∘ f and f ∘ g are the identity maps on their respective domains.

The mapping f is defined recursively as follows. If the tree has 2 vertices, then its code is the empty sequence, otherwise let a_{1} be the (sole) neighbor of the smallest leaf, and let (a_{2}, …, a_{n−2}) be the code of the smaller tree obtained by deleting that leaf. An even nicer bijective proof was given in 1980 by André Joyal, whose proof formed the iconic example of a gorgeous and deep combinatorial theory of species.

Many more bijections can be found in Dennis Stanton and Dennis White’s lively ‘Constructive Combinatorics’ (Springer). Bijective combinatorics has reached new summits in the hands of the members of the ecole bordelaise, uner the guruship of the great Bijectionist Xavier Viennot and his talented disciples: Mireille Bousquet-Mélou, Maylis Delest, and many others.

Exponential Generating Functions

We already talked above about ordinary generating functions (ogf) that are ideally suited for counting ordered structures like integer-partitions, ordered trees, and words. But many combinatorial families are really sets, where the order is immaterial. For these the natural concept is that of exponential generating function (egf).

The egf of a sequence {a(n)}_{n=0}^{∞} is

∑_{n=0}^{∞} \frac{a(n)}{n!}x^{n} .

Labeled objects can be often viewed as sets of smaller irreducible objects. For example, a permutation is the disjoint union of cycles, a set-partition is the disjoint union of non-empty sets, a (labeled) forest is the disjoint union of labeled trees, etc.

Suppose that we have two combinatorial families A and B, and there are a(n) labeled objects of size n in the A family, and b(n) in the B family. We can construct a new set of labeled objects C = A × B, where the labels are disjoint and distinct, and define the size of a pair to be the sum of the sizes of the components. We have

c(n) = ∑_{k=0}^{n} \binom{n}{k}a(k)b(n − k) ,

since we must decide (i) the size of the first component, k (k = 0 … n), which forces the size of the second component to be n − k. (ii) which of the n labels go to the first component (\binom{n}{k} ways). (iii) pick the objects for each component from the A and B family respectively, using the available labels (a(k)b(n − k) ways).

Multiplying both sides by x^{n}/n! and summing from n = 0 to n = ∞ yields

∑_{n=0}^{∞} \frac{c(n)}{n!}x^{n} = ∑_{n=0}^{∞} ∑_{k=0}^{n} \frac{a(k)}{k!}x^{k} \frac{b(n − k)}{(n − k)!}x^{n−k} =

(∑_{k=0}^{∞} \frac{a(k)}{k!}x^{k}) ( ∑_{n−k=0}^{∞} \frac{b(n − k)}{(n − k)!}x^{n−k}) .

Hence egf(C) = egf(A)egf(B). Iterating, we get

egf(A_{1} × A_{2} × ⋯ × A_{k}) = egf(A_{1}) ⋯ egf(A_{k}) .

In particular, if all the A_{i}’s are the same, we have that the egf of ordered k-tuples, A^{k}, equals [egf(A)]^{k}. But if ‘order does not matter’ then the efg of k-sets of A-objects is [egf(A)]^{k}/k!, since there are exactly k! ways of arranging a k-set into an ordered array (since all labels are distinct, all these objects are different). Summing from k = 0 to k = ∞ we get the

Fundamental Theorem of Exponential Generating Functions:

If B is a labeled combinatorial family that can be viewed as sets of ‘connected components’ that belong to a combinatorial family A then

egf(B) = exp[ egf(A) ] .

This useful theorem was part of the physics folklore for many years, and was also implicit in many older combinatorial proofs. However it was explicated only in the early 1970-ies. It was fully ‘categorized’ by means of Joyal’s theory of species, that grew to be a beautiful theory of enumeration in the hands of the ecole québecoise (the Labelle and Bergeron frères, Leroux, and others).

Here are some venerable examples. Let’s try to find the egf of set partitions, i.e. let’s try and figure out an expression for

∑_{n=0}^{∞} \frac{b(n)}{n!}x^{n} ,

where b(n), (the so-called Bell numbers) denote the number of set partitions of an n-element set.

Recall that a set partition of a set A is a set of pairwise-disjoint non-empty subsets of A, {A_{1}, …, A_{r}} such that the union of all the A_{i}’s equals A. For example, the set partitions of the 2-element set {1, 2} are {{1}, {2}} and {{1, 2}}.

The atomic objects are non-empty sets. Let a(n) be the number of non-empty sets of the form {1, 2, …, n}. Clearly when n = 0 there is no such (non-empty) set, and when n = 1 there is exactly one such set, so the egf is

A(x) = 0 + ∑_{n=1}^{∞} \frac{1}{n!}x^{n} = e^{x} − 1 ,

and we get immediately that

∑_{n=0}^{∞} \frac{b(n)}{n!}x^{n} = e^{e^{x}−1} .  (Bell)

Nowadays, with computer algebra systems, this can be used immediately to crank out the first hundred terms of the sequence b(n) by simply typing, e.g. in Maple:

taylor(exp(exp(x)-1),x=0,101); ,

so this is definitely an answer in the Wilfian sense. We can also easily derive recurrences (albeit needing at least O(n) memory), by differentiating both sides of (Bell) and comparing coefficients.

That was really easy, so let’s go on and prove something much deeper. How about an egf-style proof of Rabbi Levi Ben Gerson’s celebrated formula for the number of permutations on n objects, n!? (ex. 2 above). Every permutation can be decomposed into a disjoint union of cycles, hence the atomic objects are cycles. How many n-cycles are there? (n − 1)! of course, since (a_{1}, a_{2}, …, a_{n}) is the same as (a_{2}, a_{3}, …, a_{n}, a_{1}) which is the same as (a_{3}, …, a_{n}, a_{1}, a_{2}) etc., so we can pick the first entry arbitrarily, and then we have (n−1)! choices for placing remaining entries. Hence the egf for cycles is:

∑_{n=1}^{∞} \frac{(n − 1)!}{n!}x^{n} = ∑_{n=1}^{∞} \frac{1}{n}x^{n}

= − log(1 − x) = log(1 − x)^{−1} .

Using the Fundamental Theorem of Exponential Generating Functions, we get that the egf of permutations is

exp(log(1 − x)^{−1}) = (1 − x)^{−1} = ∑_{n=0}^{∞} x^{n}

= ∑_{n=0}^{∞} \frac{n!}{n!}x^{n} ,

and voilà we have a beautiful new proof that the number of permutations on n objects is n!.

Isn’t it a bit of an over-kill? Perhaps. But a slight modification leads immediately to the (ordinary) generating function for the number of permutations on {1, …, n} with exactly k cycles (let’s call it c(n, k)), with n fixed, C_{n}(α) = ∑_{k=0}^{n} c(n, k)α^{k}. All we have to do is go from naive counting to weighted counting, and assign to each permutation the weight α^{#cycles}. The Fundamental Theorem of Exponential Generating Functions goes verbatim to weighted counting. The weighted egf for cycles is α log(1 − x)^{−1}, and hence the weighted egf for permutations is

exp(α · log(1 − x)^{−1}) = (1 − x)^{−α} = ∑_{n=0}^{∞} \frac{(α)_{n}}{n!} x^{n} ,

where

(α)_{n} := α(α + 1) ⋯ (α + n − 1) ,

is the so-called rising factorial. Hence we derived the far less trivial result that the number of permutations of {1, …, n} with exactly k cycles equals the coefficient of α^{k} in (α)_{n}.

About ten years ago (American Mathematical onthly 101 (1994), p. 691) ), I used this technique to give a combinatorial proof of the Pythagorean theorem in the form

sin^{2} z + cos^{2} z = 1 .

sin z and cos z are the weighted egfs for increasing sequences of odd and even lengths respectively with weight (−1)^{[length/2]}. Hence the left side is the weighted egf for ordered pairs of increasing sequences

a_{1} < ⋯ < a_{k} ; b_{1} < ⋯ < b_{r} ,

such that k and r have the same parity , {a_{1}, …, a_{k}} is disjoint from {b_{1}, …, b_{r}}, and their union is {1, 2, …, k + r}. There is a killerinvolution on these sets of pairs defined as follows.

If a_{k} < b_{r} then map it to

a_{1} < ⋯ < a_{k} < b_{r} ; b_{1} < ⋯ < b_{r−1} .

and otherwise, map it to:

a_{1} < ⋯ < a_{k−1} ; b_{1} < ⋯ < b_{r} < a_{k} .

For example

1, 3, 5, 6 ; 2, 4, 7, 8, 9, 10, 11, 12 ,

whose sign is (−1)^{2} · (−1)^{4} = 1 goes to

1, 3, 5, 6, 12 ; 2, 4, 7, 8, 9, 10, 11 ,

whose sign is (−1)^{2} · (−1)^{3} = −1 (and vice versa). Since this mapping changes the sign, and is an involution, all such pairs can be paired-up into mutually cancelling pairs. But this mapping is undefined for one special pair, namely the pair (empty, empty), whose weight is 1, hence the egf for the sum of the weights of all pairs is 1, explaining the right hand side.

Yet another application of this method is to proving André’s generating function for the number of up-down permutations. A permutation of a_{1} … a_{n} is up-down (sometimes called zigzag) if a_{1} < a_{2} > a_{3} < a_{4} > a_{5} < . . .. Let a(n) be the number of up-down permutations then

∑_{n=0}^{∞} \frac{a(n)}{n!}x^{n} = sec x + tan x .

This is equivalent to

cos x · (∑_{n=0}^{∞} \frac{a(n)}{n!}x^{n}) = 1 + sin x .

Can you find the appropriate set and the killerinvolution?

Polyá-Redfield Enumeration

Often in enumeration it is easy enough to count labeled objects, but what about unlabeled ones? For example the number of labeled (simple) graphs on n vertices (ex. 6) is trivially 2^{n(n−1)/2}, but how many unlabeled graphs are there on n vertices? This is much harder, and in general there are no ‘nice’ answers, but the best known way is via a powerful technique initiated by George Polyá, that was largely anticipated by J.H. Redfield. Polyá enumeration lends itself very efficiently to counting chemical isomers, since, for example, all the Carbon atoms ‘look the same’. Indeed counting isomers was Polyá’s initial motivation.

The main idea it to view unlabeled objects as equivalence classes of easy-to-count labeled objects, and count these equivalence classes. But ‘what equivalence’? There is always a (sometimes hidden) symmetry group, let’s call it G, ‘acting’ on the set of labeled objects, let’s call it A, by a group action G × A → A, (g, a) → g(a), and two objects a and b of A are equivalent if b = g(a) for some member g of the group G. This is obviously an equivalence relation and the equivalence classes are the orbits

Orbit(a) := {g(a) | g ∈ G} , a ∈ A .

Calling each orbit a ‘family’, we have the task of counting the number of families. Note that G is a subgroup of the group of permutations on the finite set A.

Suppose that there is picnic consisting of many families, and we want to count the number of families. One way would be to define some ‘canonical head’ of a family, say ‘mother’ and count the number of mothers. But some daughters look like mothers, so it is not so easy. On the other hand, you can’t just literally count people, since then you would get a gross overcount. But ‘naive’ counting of people (or objects) is giving a credit of 1 to each person. If we asked each person: ‘How big is your family’, and add to our count the reciprocal of that number, then things would come out just right, since a family of size k would get credit 1/k for each of its members, hence would be counted exactly once. Going back to counting orbits, we see that their number is

∑_{a∈A} \frac{1}{|Orbit(a)|} .

The conceptual opposite of ‘orbit of a’ is the subgroup of members of G that fix a,

F ix(a) = {g ∈ G | g(a) = a} .

There is a natural one-to-one correspondence between the cosets of F ix(a) in G and the orbit of a, hence the size of Orbit(a) is |G/F ix(a)|, and we get (Let χ(statement) be 1 or 0 according to whether it is true or false, respectively).

#Orbits = \frac{1}{|G|} ∑_{a∈A} |F ix(a)| =

\frac{1}{|G|} ∑_{a∈A} ∑_{g∈G} χ(g(a) = a)

= \frac{1}{|G|} ∑_{g∈G} ∑_{a∈A} χ(g(a) = a) = \frac{1}{|G|} ∑_{g∈G} fix(g) ,

where fix(g) is the number of fixed points of g (viewed as a permutation of A). We have just proved what used to be called Burnside’s lemma but goes back to Cauchy and Frobenius, that states that the number of orbits in the action of G on A equals the average number of fixed points over G. If the group G is the full symmetric group of all the permutations of A, we get that the average number of fixed points equals 1 (in this trivial case there is only one orbit!).

Enter George Polyà. The objects that he was interested in counting (e.g. chemical isomers, or colorings of the faces of the cube) were all naturally functions from an underlying set, let’s call it U to a set of colors (or atoms), let’s call it C. The group of symmetry of U naturally acts on the set of functions f : U → C by the induced action: g(f)(u) := f(g(u)). To find the number of fixed points of g in the set of C-colorings of U simply decompose g into cycles. Such a coloring must have the same color on the members of each cycle, hence if there are c := |C| colors, the number of different colorings of U (up to G-equivalence) is

\frac{1}{|G|} ∑_{g∈G} c^{#Cycles(g)} .

Here is a simple application. How many necklaces (without a clasp) are there consisting of p beads (p prime), using a different colors? The underlying set is {0, …, p − 1}, and the symmetry group is Z_{p}, the cyclic group of order p. Since p is a prime, there are p−1 elements with one cycle (of length p) and one element (the identity permutation) with p cycles (all of length 1). It follows that the number of necklaces is

\frac{1}{p}((p − 1) · a + 1 · a^{p}) = a + \frac{a^{p} − a}{p} .

In particular, since this number is necessarily an integer, we get as a bonus a combinatorial proof of Fermat’s Little Theorem. Who knows? Perhaps one day there would be an equally nice combinatorial proof of Fermat’s Last theorem? All one has to do is to prove that there is no bijection between the union of the sets of straight necklaces of size n using x colors, and that set using y colors, with that set using z colors (with n > 2, of course).

If one wants to keep track of how many beads there are of each color, we simply replace straight counting by weighted counting, and c^{#Cycles(g)} is replaced by (assuming that g has α_{1} 1-cycles, α_{2} 2-cycles, etc.)

(x_{1} + ⋯ + x_{c})^{α_{1}} · (x_{1}^{2} + ⋯ + x_{c}^{2})^{α_{2}} · · · .

The resulting expression is the celebrated cycleindex polynomial.

The Principle of Inclusion-Exclusion and Möbius Inversion

Another pillar of enumeration is the Principle of Inclusion-Exclusion (nicknamed PIE). Suppose that there are n sins, s_{1}, …, s_{n} that a person may succumb to, and suppose that for each set of sins S, A_{S} is the set of people who have all the sins in S (and possibly others). Then the number of good people (without sins) is

∑_{S}(−1)^{|S|}|A_{S}| .  (P IE)

For example, if the set A is the set of all permutations π of {1, …, n} and the i^{th} sin is having π[i] = i, then |A_{S}| = (n − |S|)!, and we get that the number of derangements (permutations without fixed points) is

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}(n − k)! = n! ∑_{k=0}^{n}(−1)^{k} \frac{1}{k!} ,

that yields the answer: ‘closest integer to n!/e’.

PIE is but a special case of Möbius inversion on general Partially Ordered Sets (posets) where the poset happens to be the Boolean lattice. This realization, made in 1964, by Gian-Carlo Rota, in his seminal paper ‘On the Foundations of Combinatorial Theory I. Theory of Möbius functions’, (reprinted in Rota’s Collected Works) is considered by many to be the big bang that started modern algebraic combinatorics. Möbius’s original inversion formula is gotten back when the partially ordered set is ℕ and the partial order is divisibility.

A contemporary account of Enumeration from the ‘algebraic’ point of view can be found in Richard Stanley’s marvelous two-volume set ‘Enumerative Combinatorics’ (Cambridge Univ. Press), that I strongly recommend.

Algebraic Combinatorics

So far I described one of the routes to Algebraic Combinatorics: abstraction and conceptualization of classical enumeration. The other route, ‘concretization of the abstract’ is almost everywhere dense in mathematics, and cannot be described in a few pages. Let me quote from the preface of the excellent volume ‘New Perspectives in Algebraic Combinatorics’ by Billera, Björner, Greene, Simion, and Stanley (Cambridge University Press).

“Algebraic combinatorics involves the use of techniques from algebra, topology, and geometry in the solution of combinatorial problems, or the use of combinatorial methods to attack problems in these areas. Problems amenable to the methods of algebraic combinatorics arise in these or other areas of mathematics or from diverse parts of applied mathematics. Because of this interplay with many fields of mathematics, algebraic combinatorics is an area in which a wide variety of ideas and methods come together.”

Tableaux

An interesting class of objects that initially came up in group representation theory, but that turned out to be useful in many other areas, for example, the theory of algorithms, are Young Tableaux. They were first used by Rev. Alfred Young to construct explicit bases for the irreducible representations of the symmetric group. For any partition λ = λ_{1} … λ_{k} of n, a Young tableau of shape λ is an array of k left-justified rows with λ_{1} entries in the first row, λ_{2} entries in the second row, and so on, such that every row and every column is increasing, and the set of entries is {1, 2, …, n}. For example there are two Standard Young Tableaux whose shape is 22:

1 2 3 4 , 1 3 2 4 .

Let f_{λ} be the number of Standard Young Tableaux of shape λ. For example for n = 4 f_{4} = 1, f_{31} = 3, f_{22} = 2, f_{211} = 3, and f_{1111} = 1. The sum of the squares of these numbers is 1^{2} +3^{2} +2^{2} +3^{2} +1^{2} = 24 = 4!.

Since f_{λ} is the dimension of the irreducible representation parametrized by λ, it follows by socalled Frobenius reciprocity that the above is true for all n, in other words:

∑_{λ⊢n} f_{λ}^{2} = n! .  (Y − F)

A gorgeous bijective proof of this identity, that has many beautiful properties, was given by Gilbert Robinson and Craige Schenstead and later extended by Donald Knuth, and is now known as the Robinson-Schenstead-Knuth Correspondence. It inputs a permutation π = π_{1}π_{2} … π_{n}, and outputs a pair of Young Tableaux of the same shape, thereby proving (Y − F).

Algebraic combinatorics is currently a very active field, and as mathematics is becoming more and more concrete, constructive and algorithmic, there are going to be many more combinatorial structures discovered in all areas of mathematics (and science!) and this will guarantee that algebraic combinatorialists will stay very busy for a long time to come.

Biography of contributor

Doron Zeilberger was born, as a person, on July 2, 1950. He was born, as a mathematician, in 1976, when he got his Ph.D. under the direction of Harry Dym (in analysis). He was born-again, as a combinatorialist, two years later, when he read a lovely proof of the so-called Hook-Length Formula (enumerating Standard Young Tableaux) by Curtis Greene, Albert Nijenhuis, and Herb Wilf. He lived happily ever after.