What is the relationship between the Bell numbers, the Bell polynomials, and the partition numbers? - MathOverflow

What is the relationship between the Bell numbers, the Bell polynomials, and the partition numbers?

2010-03-16T12:17:09Z

A friend of mine and I were wondering what relationship exists between the partition numbers $p_{n}$ and the Bell numbers $B_{n}$ (and also possibly the Bell polynomials $B_{n,k}(x_1,x_2,\dots,x_{n-k+1})$ )? Since integers are the decategorification of finite sets, it is appealing to think that there should be some relationship between the generating functions of the Bell numbers and the partition numbers. My friend pointed out the the equivalence classes of partitions of sets correspond to the conjugacy classes of the symmetric group $S_{n}$, but it was not clear how to convert that into a relationship between the two types of partitions.

One definite historical flavored question arose in our minds: why is there such a disconnect between the study of integer partitions -- which leads to things like the Ramanujan-Rademacher formula, and involves lots of clever q-series manipulations, and the study of set partitions, which involves things like Stirling numbers, Bell numbers, Bell polynomials and whatnot. Her book about integer partitions apparently didn't mention the Stirling numbers at all.

Answer by Martin Rubey for What is the relationship between the Bell numbers, the Bell polynomials, and the partition numbers?

2010-03-16T13:46:32Z

As you already remarked, integer partitions can be regarded as the isomorphismtypes of set partitions. The relationship between their generating functions is in my opinion best understood in the language of species. Let $E$ be the species of sets (ensembles in french :-), $E_{>0}$ the species of non-empty sets. Then the species of set partitions $P$ is

$P=E\circ E_{>0}$

(read: sets of non-empty sets). To understand the relationship between there generating functions, we need the cycle index series $Z_F(p_1, p_2,\dots)$ of a species F. The main points are:

1) The exponential generating function for the structures of $F$ (in our case: set partitions) $F(x)$ is

$$Z_F(x,0,0,\dots).$$

2) The ordinary generating function for the isomorphism types of $F$ (in our case: integer partitions) $\tilde F(x)$ is $$Z_F(x,x^2,x^3,\dots).$$

3) The cycle index series of $F\circ G$ is

$$Z_{F\circ G}(p_1, p_2,\dots) = Z_F(Z_G(p_1, p_2,\dots), Z_G(p_2, p_4,\dots), Z_G(p_3, p_6,\dots)\dots).$$

4) The cycle index series of sets is

$$Z_E(p_1,p_2,\dots)=\exp(p_1+\frac{p_2}{2}+\frac{p_3}{3}+\dots).$$

5) The cycle index series of the empty set 1, therefore the cycle index series of nonempty sets is

$$Z_{E_{>0}}(p_1,p_2,\dots)=\exp(p_1+\frac{p_2}{2}+\frac{p_3}{3}+\dots)-1.$$

6) Combining 3), 4) and 5) we obtain

$$Z_P(p_1,p_2,\dots)=\exp\sum_{k\geq 1}\frac{1}{k}(\exp(p_k+\frac{p_{2k}}{2}+\frac{p_{3k}}{3}+\dots)-1).$$

7) According to 1), we obtain

$$P(x)=\exp(\exp(x)-1).$$

8) According to 2), we obtain

$$\tilde P(x)=\prod_{k\geq 1}\frac{1}{1-x^k}.$$

See Bergeron, Labelle, Leroux, "Combinatorial Species and Tree-like Structures", Section 1.4, page 45.

But I suppose the real question is: what is the cycle index series? I'm afraid I can only point you to the wikipedia article, if you don't have access to the book by Bergeron, Labelle and Leroux...

Maybe some intuition helps: a species is a functor from the category of finite sets and bijections into the same category, that is -- roughly -- a machine that produces a finite set of objects (called "combinatorial structures") given a finite set (of "labels"), together with another machine that, given a bijection on the labels (a "relabelling") produces a bijection on the set of objects (that relabels all the objects).

The cycle index series captures the information which structures can be obtained from a given structure by permuting some of the labels, such that the permutation has given cycle type. But really, I think you need to look into the book.

Answer by JBL for What is the relationship between the Bell numbers, the Bell polynomials, and the partition numbers?

2010-03-16T14:20:50Z

A possible answer to the second question is that the Bell and Stirling numbers are easier to understand in some sense than the partition numbers, and so there's not as much theory to build around them because we can answer many of the natural questions relatively easily. For example: the generating functions for Stirling and Bell numbers are easy to write down and don't require any infinite products; the Stirling numbers satisfy a simple recursion; and the Stirling numbers are the coefficients of the change of basis between two natural bases of single-variable polynomials.

Answer by Douglas Zare for What is the relationship between the Bell numbers, the Bell polynomials, and the partition numbers?

2010-03-16T14:53:03Z

This doesn't answer the question, but I would add another example to the Bell number side: The Bell number of a graph is the number of set partitions of the vertices into independent sets, so the Bell number of the empty graph on $n$ vertices is $B_n$.

Winston Yang proved that the Bell number of a tree on $n+1$ vertices is $B_n$, and the Bell number of the $1$-skeleton of a simplicial complex called a $k$-tree with $n+k$-vertices is also $B_n$.