The product that deals the labels

A polynomial that counts rests on a single sentence: multiplying two series picks one term from each factor and adds the exponents, which is exactly choosing one value from each of two boxes and adding. Nothing was assumed about what the boxes held, and the same convolution turns up wherever independent things are combined — it is how the distribution of a sum is built from the distribution of one draw.

Something was assumed about what the objects are. They were assumed to be interchangeable — a domino is a domino, a part of size three is a part of size three, and two objects of the same size are the same object. A great many counting problems are not like that, and the difference is not a technicality. It changes which operation counts a combination.

What the labels do to a product #

Take two families of structures, and suppose a structure of size $n$ is built by choosing a first piece and a second piece whose sizes add to $n$. If the pieces are interchangeable lumps, that is the whole of the choice, and the count is the convolution the earlier essay is about: sum over the ways of splitting $n$, multiply the two counts.

If the objects carry labels — the numbers $1$ to $n$, or $n$ distinguishable people, or the vertices of a graph — then splitting the size is not splitting the object. A first piece of size two is a set of two particular labels, and which two matters. So the choice has three parts rather than two: how many labels go to the first piece, which ones, and then a structure on each side.

That middle part is the binomial coefficient, and it is all that separates the two dictionaries:

$$c_n = \sum_{k=0}^{n} \binom{n}{k} a_k\, b_{n-k}.$$

The hero figure is that sum’s middle factor at $n = 4$, $k = 2$, drawn as a list. Six splits, and the reason a picture is worth having here is that the six are not obviously six: a reader who has spent a page on ordinary convolution has been trained to see a split of the number four, of which there is one with parts two and two.

The six are also the reason the two dictionaries cannot be reconciled by a change of variable. Six is not a function of the sizes alone — it is $\binom{4}{2}$, and at $n=6$, $k=3$ it is twenty, and the ratio between the labelled count and the unlabelled one depends on where the split falls. A correction that varied with the split could not be absorbed into the series’ coefficients, which is why the repair has to be a change to what the coefficients are rather than a factor applied afterwards.

The sum that is not a convolution, in a grid #

The ordinary rule has a picture — a multiplication table whose anti-diagonals are the product’s coefficients — and the labelled rule has the same picture with one factor more in each cell.

The figure’s two numbers are worth reading as a pair. Both families here count one structure at every size, so the ordinary convolution at size four is $1+1+1+1+1 = 5$: five ways to split four into two ordered parts. The labelled convolution is $1+4+6+4+1 = 16$, which is $2^4$, and it should be — a pair of pieces on four labels is a decision about each label separately, and there are two places each label can go.

That is the cheapest possible check on the rule and it is the reason the figure computes the diagonal twice. A sum over splits that comes out at $2^n$ is a sum whose binomial factors have been put in the right place; one that came out at $n+1$ would be the unlabelled rule wearing a label.

Why dividing by n! is the repair #

The binomial coefficient in the sum is an obstacle rather than an insight: it means the coefficients of a labelled family do not multiply, so none of the apparatus of the earlier essay — solve an equation, read off a closed form — applies. The repair is to stop hanging the count on $x^n$ and hang it on $x^n/n!$ instead.

Write $\hat{A}(x) = \sum a_n x^n/n!$. Then the coefficient of $x^n/n!$ in $\hat{A}\hat{B}$ is

$$n!\sum_{k} \frac{a_k}{k!}\cdot\frac{b_{n-k}}{(n-k)!} = \sum_k \frac{n!}{k!\,(n-k)!}a_k b_{n-k} = \sum_k \binom{n}{k}a_k b_{n-k},$$

which is the labelled rule. The factorial in the denominator is exactly the factorial the deal puts in the numerator, and once it is cancelled the labelled families multiply as simply as the unlabelled ones did.

Such a series is an exponential generating function, and the name is not decoration. The series for “exactly one structure on every size”, which is the labelled analogue of the constant series $1, 1, 1, \ldots$, is $\sum x^n/n! = e^x$. Everything the second dictionary does is downstream of that one substitution.

Four constructions, and what each becomes #

The value of a dictionary is that a description of the objects turns into an expression without any counting at all. Both dictionaries have entries; they are different entries.

A pair multiplies, in both dictionaries. A sequence of pieces is a pair repeated, so it inverts: $1/(1 - A)$ in the ordinary dictionary and $1/(1 - \hat{A})$ in the exponential one. Those two rows look alike and the agreement is a coincidence of notation rather than of content — in the first, the sequence is an ordered list of interchangeable lumps; in the second, it is an ordered list of labelled pieces with the labels dealt among them, and the counts differ wildly. A sequence of singletons on $n$ labels is a permutation of them, so there are $n!$; a sequence of unlabelled singletons summing to $n$ is one object.

The rows that matter are the two the ordinary dictionary cannot fill. A set of pieces — the pieces unordered, so that swapping two of them is not a new structure — has no entry on the ordinary side, because an unlabelled set of unlabelled pieces is a partition and partitions do not factorise. On the labelled side it does have an entry, and the entry is an exponential:

$$\text{a set of pieces, each with series } \hat{C} \;\longrightarrow\; \exp\!\big(\hat{C}(x)\big).$$

The reason is the division. A set of $k$ pieces is an ordered list of $k$ pieces counted $k!$ times over, so the series for “a set of exactly $k$ pieces” is $\hat{C}^k/k!$, and adding over $k$ gives the exponential series. The $k!$ that has to be divided out is the same $k!$ the exponential’s own denominators supply, which is why the answer is a named function rather than an awkward sum.

What the exponential formula buys #

The entry above is one line and it settles several counting problems that are unpleasant by any other route.

A partition of a labelled set into blocks is a set of non-empty pieces, so the recipe applies with $\hat{C} = e^x - 1$: every non-empty set of labels is one piece, and $e^x - 1$ is the series that counts one structure on every positive size and none on size zero. The answer is $\exp(e^x - 1)$, whose coefficients are the Bell numbers $1, 1, 2, 5, 15, 52, 203, 877$.

Nothing in that derivation counted anything. The description — a set of non-empty blocks — was translated twice, once by the set rule and once by the piece’s own series, and the translation is the proof. What the figure adds is the check that the translation describes the objects: the second row is an enumeration, and a decomposition that double-counted or missed a case would show up there as a mismatch at the first size where it bites.

The same sentence covers permutations, which are a set of cycles. A cycle on $k$ labels can be written in $k$ rotations of one list, so there are $(k-1)!$ of them, and their series is $\sum_{k\ge1}(k-1)!\,x^k/k! = \sum x^k/k = \log\frac{1}{1-x}$. Then

$$\exp\left(\log\frac{1}{1-x}\right) = \frac{1}{1-x},$$

whose coefficient of $x^n/n!$ is $n!$.

The number of permutations of $n$ labelled things is $n!$, which nobody needed a dictionary to learn — and the point is that the dictionary got it right, through a logarithm and an exponential that cancel, which is the cheapest available test that the set rule and the cycle count are both correct.

Where the same machine gives something nobody would guess #

A permutation with no fixed point is a set of cycles of length at least two, so the cycle series loses its first term: $\log\frac{1}{1-x} - x$. Exponentiating,

$$\exp\left(\log\frac{1}{1-x} - x\right) = \frac{e^{-x}}{1-x},$$

and the coefficients are the derangement numbers. Two lines, and the second is a subtraction.

By any other route this is work. The standard derivation is inclusion–exclusion over which points are fixed, and the constant that counts what does not happen takes that route because the constant is what it is about. The dictionary reaches the same series by deleting one term from one factor, and the reason it can is that “no fixed point” is a condition on the pieces rather than on the whole — which is the shape of condition this dictionary handles and the shape it is worth looking for. The same deletion is available in the ordinary dictionary and does much less there, because the ordinary dictionary has no set rule to delete a term inside: forbidding a part of size one in a partition changes a product’s factors, which is the substitution Euler’s identity turns on, and it does not reach conditions on how the pieces relate.

The sibling case is as short. A permutation that undoes itself has every cycle of length one or two, so its series is $\exp(x + x^2/2)$, and the coefficients count those.

Three families, one recipe, and the only thing that changed was which cycle lengths the inner series was allowed. Set them all free and the answer is $n!$; forbid length one and the answer is the derangements; permit only one and two and the answer is the involutions. The condition on the objects became a condition on one factor, and the factor is short enough to write inside a bracket.

That is worth contrasting with how the same three counts are usually obtained. $n!$ is a product. The derangements come from inclusion–exclusion, which is a signed sum over subsets. The involutions come from a recurrence — either the last label is alone or it is paired with one of the other $n-1$ — and the recurrence has to be found. Three different arguments, and the dictionary replaces all three with one translation and three different inner series, which is what a good notation is for. It also predicts the ones nobody asked about: permutations all of whose cycles have odd length, or length a multiple of three, are the same recipe with a different sum inside the bracket, and their counts fall out without a new idea.

The place where both dictionaries are needed at once #

There is a temptation to treat the exponential version as the better one, since it has more entries. It is not better; it answers a different question, and the difference is visible in a case where the same objects can be counted either way.

Count the sequences of $n$ letters from an alphabet of three. Labelled, that is a sequence of positions each carrying a letter, and the exponential series for one letter at one position is $x$, so three letters give $3x$ — but a sequence of labelled pieces is not what is wanted, because the positions of a word are ordered by the word rather than dealt out. Unlabelled, the count is $3^n$ and the ordinary series is $1/(1-3x)$, which is correct and immediate.

There is a cleaner way to see why, and it is a statement about what a series is being asked to remember. The ordinary series remembers how many objects there are of each size. The exponential series remembers how many objects there are of each size on a fixed set of labels, which is more information when the labels can be permuted and exactly the same information when they cannot. A word’s positions cannot be permuted without changing the word, so for words the two counts coincide and the extra apparatus buys nothing; a set partition’s blocks can be, and there the apparatus is the whole argument.

The test is whether the labels are dealt or ordered. If a structure is assembled by distributing distinguishable atoms among pieces, the exponential dictionary applies. If it is assembled by placing interchangeable items in a fixed arrangement, the ordinary one does. A great many mistakes with this dictionary are one of those two sentences applied to the other kind of object, and the symptom is a count that is out by a factorial — which is the most recognisable error in the subject and the reason it is worth naming.

The same distinction settles a question the earlier essay left in the air. Pascal’s triangle is the coefficients of $(1+x)^n$, and it is an ordinary generating function — the objects counted are subsets of a fixed $n$-element set, and a subset of a fixed set is an unlabelled object as far as the variable is concerned, because the variable is tracking the subset’s size and nothing else. Change the question to how many ways to split $n$ labelled things into two named piles and the answer is $2^n$, which is the labelled convolution of the grid above. The triangle’s rows and the powers of two are two different readings of the same table, and which reading applies is decided by whether the labels are being dealt.

Labelled trees are the standing example of the first kind, and sixteen trees on four points counts them by an argument that is a bijection rather than a series. The exponential dictionary reaches $n^{n-1}$ rooted labelled trees too, by a route that needs one tool this essay does not carry — Lagrange’s inversion formula, which extracts the coefficients of a series defined by $T = xe^{T}$. That equation is the description a rooted tree is a root with a set of rooted trees hanging from it written in the dictionary, and the whole of the work is in the extraction.

What the second dictionary cannot do #

It does not help when the objects have their own symmetry. A set of pieces means unordered, and the division by $k!$ is exactly right because $k$ labelled pieces are all distinct. Unlabelled objects with symmetry — necklaces up to rotation, graphs up to isomorphism — need a different apparatus entirely, in which one divides by a group rather than by a factorial. Necklaces that prove a theorem is the smallest case of that, and it is a separate machine.

It does not make extraction easier. $\exp(e^x - 1)$ is a closed form and the Bell numbers have no closed form; the series is a compact description of a sequence, not a formula for its terms. What the closed form does give is the asymptotic behaviour, through the same analytic reading the earlier essay ends on — and for a function like this one the reading is harder rather than easier, since the singularity is not a pole. A series that converges nowhere is the standing warning about what a closed form does and does not promise: a compact expression can name a sequence perfectly and still be useless for computing with, and the two properties are independent.

And the division by $n!$ is bookkeeping, not analysis. Nothing here evaluates a series at a number, exactly as in the counting polynomial. $e^x$ is a name for the sequence of reciprocal factorials and $\log\frac{1}{1-x}$ is a name for the sequence of reciprocals; the identity $\exp\log = \text{id}$ used above is a statement about coefficients, proved by the composition rule for formal series, and it needs the inner series to have no constant term — which $\log\frac{1}{1-x}$ satisfies and $e^x$ does not. Substituting the wrong one produces an infinite sum for a single coefficient, which is the one way this arithmetic can fail.

What the pictures cannot show #

The figures draw the coefficients at sizes up to seven, and every claim is about all sizes. The enumerations are what makes the comparison worth drawing — 877 partitions of a seven-element set, counted by listing them — and the agreement at eight sizes is evidence rather than proof. The proof is always the decomposition, and a decomposition is a sentence.

The hero lists six deals and the general claim is about $\binom{n}{k}$ of them. A figure of the deals at $n = 10$ would have two hundred and fifty-two rows and would be less convincing rather than more, because the thing to be seen is that a deal is a choice — which is visible at four labels and merely repetitive at ten.

And no picture here shows the cancellation that the whole essay turns on. That the $k!$ in the set rule is the same $k!$ the exponential’s denominators supply is an identity between two factorials in two different places, and it is the sort of thing that can only be written down.

Still open: which descriptions have entries #

The dictionary as it stands has entries for pair, sequence, set and cycle, and for substituting one description into another. What it does not have is a rule for every construction anybody might write down, and the interesting question is which ones are missing.

Two are worth naming. A set of pieces, no two the same size has no entry, because the condition is a relation between the pieces rather than a property of each, and both dictionaries are built on the pieces being chosen independently. And a structure invariant under some rearrangement of its labels is outside both, which is the symmetry case above.

The direction that does have a general answer is substitution. A structure that is a $B$-structure whose atoms are themselves $A$-structures has series $\hat{B}(\hat{A}(x))$, and the exponential formula is that rule with $\hat{B} = e^x$. Following it through gives the modern form of the subject, in which a grammar of constructions is compiled into an equation and the equation is handed to an extraction routine — and the price of that generality is that the answer arrives without anybody having seen why it is true.

What the extra factorial was #

The whole of the difference between the two dictionaries is one binomial coefficient, and the whole of the repair is one factorial. That is a small amount of apparatus for what it settles, and the reason it settles so much is that the factorial was always there.

An ordinary generating function counts objects. An exponential one counts objects together with a labelling, and dividing by $n!$ is the statement that the labelling is not part of the object. Once that is said, the set rule follows, the exponential appears because a set of $k$ things is a list divided by $k!$, and a description written in English translates into an expression with no counting in it at all.

The lesson generalises past series. When a count comes out a factorial too large, the usual cause is not an error in the arithmetic but an object that has been described with a piece of bookkeeping attached to it — an ordering that nobody asked for, a labelling that is not part of the thing. Dividing it out is what this dictionary does once, systematically, and it is worth recognising in the cases where it has to be done by hand.