Bell Polynomials

Trees with a single cycle

When counting combinatorial objects, it is often the case that we have two types of structure present at different levels. The aim of this post is to introduce the Bell polynomials, which provides the most natural notation for describing this sort of situation, and to mention some of the results that become easier to derive in this framework. This post is based on material and exercises from Chapter 1 of Jim Pitman’s book Combinatorial Stochastic Processes, which is great, and also available online here.

The structures that Bell polynomials enumerate are called composite structures in this account. Rather than give a definition right away, I shall give an example. An object I have been thinking about in the past few weeks are graphs on n vertices containing precisely one cycle. Some of the background for this has been explained in recent posts.

In a recent post on Prufer codes, I gave the classical argument showing that the number of trees on n vertices is $n^{n-2}$ . We might consider a unicyclic graph to be a tree with an extra edge. But if we consider the number of ways to add a further vertex to a tree, we get

$n^{n-2}\left[\binom{n}{2}-(n-1)\right]=n^{n-2}\binom{n-1}{2}.$

Obviously, we have overcounted. If the single cycle in a graph has length k, then the graph has been counted exactly k times in this enumeration. But it is not obvious how many graphs have a single cycle of length k.

Instead, we stop worrying about exactly how many of these there are, as there might not be a simple expression anyway. As soon as we start using them in any actual argument, it will be useful to know various properties about the graphs, but probably not exactly how many there are.

Let’s focus on this single cycle of length k say. If we remove the edges of the cycle, we are left with a collection of trees. Why? Well if there was a cycle in the remaining graph, then the original graph would have had at least two cycles. So we have a collection of trees, unsurprisingly called a forest. Remembering that some of the trees may in fact be a single vertex (on the cycle), it is clear that there is a bijection between these trees and the vertices of the cycle in the obvious way. We can think of the graph as a k-cycle, dressed with trees.

Alternatively, once we have specified its size, we can forget about the k-cycle altogether. The graph is precisely defined by a forest of k trees on n vertices, with a specified root in each tree indicating which vertex lies on the cycle, and a permutation specifying the cyclic ordering of the trees. We can write this as

$N_{n,k}=(k-1)!\sum_{(A_1,\ldots,A_k)\in\mathcal{P}^k(n)}a_1^{a_1-1}\cdot\ldots\cdot a_k^{a_k-1},\quad \text{for }a_i=|A_i|,$

where $\mathcal{P}^k(n)$ is the number of partitions of [n] with k blocks. Remember that the blocks in a partition are necessarily unordered. This makes sense in this setting as the cyclic permutation chosen from the (k-1)! possibilities specifies the order on the cycle.

Bell Polynomials

The key point about this description is that there are two types of combinatorial structure present. We have the rooted trees, and also a cyclic ordering of the rooted trees. Bell polynomials generalise this idea. It is helpful to be less specific and think of partitions of [n] into blocks. There are $w_j$ arrangements of any block of size j, and there are $v_k$ ways to arrange the blocks, if there are k of them. Note that we assume $v_k$ is independent of the arrangements within the collection of blocks. So in the previous example, $w_j=j^{j-2}$ , and $v_k=(k-1)!$ . Pitman denotes these sequences by $v_\bullet,w_\bullet$ . Then the (n,k)th partial Bell polynomial, $B_{n,k}(w_\bullet)$ gives the number of divisions into k blocks:

$B_{n,k}(w_\bullet):=\sum_{(A_1,\ldots,A_k)\in\mathcal{P}^k(n)}\prod_{i=1}^k w_{a_i}.$

The total number of arrangements is given by the Bell polynomial

$B_n(v_\bullet,w_\bullet):=\sum_{k=1}^n v_k B_{n,k}(w_\bullet).$

Here are some other examples of Bell polynomials. The Stirling numbers of the first kind $c_{n,k}$ give the number of permutations of [n] with k cycles. Since we don’t want to impose any combinatorial structure on the set of cycles, we don’t need to consider $v_\bullet$ , and the number of ways to make a j-cycle from a j-block is $w_j=(j-1)!$ , so $c_{n,k}:=B_{n,k}((\bullet-1)!)$ . Similarly, the Stirling numbers of the second kind $S_{n,k}$ give the number of permutations of [n] into k blocks. Almost by definition, $S_{n,k}:=B_{n,k}(1^\bullet)$ , where $1^\bullet$ is defined to be the sequence containing all 1s.

Applications

So far, this is just a definition that gives an abbreviated description for the sizes of several interesting sets of discrete objects. Having clean notation is always important, but there are further advantages of using Bell polynomials. I don’t want to reproduce the entirety of the chapter I’ve read, so my aim for this final section is to give a very vague outline of why this is a useful formulation.

Bell polynomials can be treated rather nicely via generating functions. The key to this is to take a sum not over partitions, but rather over ordered partitions, which are exactly the same, except now we also care about the order of the blocks. This has the advantage that there is a correspondence between ordered partitions with k blocks and compositions with k terms. If the composition is $n_1+\ldots+n_k=n$ , it is clear why there are $\binom{n}{n_1,\ldots,n_k}$ ordered partitions encoding this structure. This multinomial coefficient can be written as a product of factorials of $n_i$s over i, and so we can write:

$B_{n,k}(w_\bullet)=\frac{n!}{k!}\sum_{(n_1,\ldots,n_k)}\prod_{i=1}^k \frac{w_{n_i}}{n_i!}.$

This motivates considering the exponential generating function given by

$w(\xi)=\sum_{j=1}^\infty w_j\frac{\xi_j}{j!},$

as this leads to the neat expressions:

$B_{n,k}(w_\bullet)=n![\xi^n]\frac{w(\xi)^k}{k!},\quad B_n(v_\bullet,w_\bullet)=n![\xi^n]v(w(\xi)).$

The Bell polynomial $B_n(v_\bullet,w_\bullet)$ counts the number of partitions of [n] subject to some extra structure. If we choose uniformly from this set, we get a distribution on this combinatorial object, for which the Bell polynomial provides the normalising constant. If we then ignore the extra structure, the sequences $v_\bullet,w_\bullet$ induce a probability distribution on the set of partitions of n. This distribution is known as a Gibbs partition. It is interesting to consider when and whether it is possible to define a splitting mechanism such that the Gibbs partitions can be coupled to form a fragmentation process. This is the opposite of a coalescence process. Here, we have a sequence of masses, and at each integer time we have rules to determine which mass to pick, and a rule for how to break it into two pieces. It is certainly not the case that for an arbitrary splitting rule and sequences $v_\bullet,w_\bullet$ , the one-step fragmentation of the Gibbs partition on n gives the corresponding Gibbs partition on (n-1).

CLT for random permutations

For the final demonstration of the use of Bell polynomials, I am going to sketch the outline of a solution to exercise 1.5.4. which shows that the number of cycles in a uniformly chosen permutation has a CLT. This is not at all obvious, since the number of permutations of [n] with k cycles is given by $B_{n,k}((\bullet-1)!)$ and there is certainly no simple form for this, so the possibility of doing a technical limiting argument seems slim.

For ease of notation, we copy Pitman and write $c_{n,k}:=B_{n,k}((\bullet-1)!)$ as before. First we show exercise 1.2.3. which asserts that

$x(x+1)\ldots(x+(n-1))=\sum_{k=1}^n c_{n,k}x^k.$

We argue combinatorially. The RHS is the number of ways to choose $\sigma\in S_n$ and a colouring of [n] with k colours such that the orbits of $\sigma$ are monochromatic. We prove that the LHS also has this property by induction on the number of vertices. We claim there is a 1-to-(x+n) map from configurations on n vertices to configurations on (n+1) vertices. Given $\sigma\in S_n$ and colouring, for any $a\in[n]$ , we construct $\sigma_a\in S_{n+1}$ by $\sigma_a(a)=n+1$ , $\sigma_a(n)=\sigma(a)$ and for all other x, $\sigma_a(x)=\sigma(x)$ . We give n+1 the same colour as a. This gives us n possibilities. Alternatively, we can map (n+1) to itself and give it any colour we want. This gives us x possibilities. A slightly more careful argument shows that this is indeed a 1-to-(x+n) map, which is exactly what we require.

So the polynomial

$A_n(z)=\sum_{k=0}^nc_{n,k}z^k,$

has n real zeros, which allows us to write

$\frac{c_{n,k}}{A_n(1)}=\mathbb{P}(X_1+\ldots+X_n=k),$

where the Xs are independent but not identically distributed Bernoulli trials. The number of cycles is then given by this sum, and so becomes a simple matter to verify the CLT by checking a that the variances grows appropriately. As both mean and variance are asymptotically log n, we can conclude that:

$\frac{K_n - \log n}{\sqrt{\log n}}\stackrel{d}{\rightarrow} N(0,1).$

In a future post, I want to give a quick outline of section 1.3. which details how the Bell polynomials can be surprisingly useful to find the moments of infinitely divisible distributions.

Grassmann: The New Pythagorus (jehovajah.wordpress.com)

4 thoughts on “Bell Polynomials”

Pingback: Generating Functions for the IMO | Eventually Almost Everywhere
Pingback: Increments of Random Partitions | Eventually Almost Everywhere
Pingback: Random Mappings for Cycle Deletion | Eventually Almost Everywhere
Pingback: The Coupon Collector Problem | Eventually Almost Everywhere

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Bell Polynomials

4 thoughts on “Bell Polynomials”

Leave a Reply Cancel reply

Related articles

Share this:

Like this:

Related

4 thoughts on “Bell Polynomials”

Leave a Reply Cancel reply