MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 incorporate comment

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 categoryof finite sets, that is -- roughly -- a machine that produces a finite set of objects (called "combinatorial structures") given a finite set (of "labels").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.

3 expand
set partitions) $F(x)$ is

$Z_F(x,0,0,\dots)$.$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).Z_F(x,x^2,x^3,\dots).$$$Z_{F\circ $Z_{F\circ G}(p_1, p_2,\dots) = Z_F(Z_G(p_1, p_2,\dots), Z_G(p_3, p_6,\dots),\dots)$p_6,\dots)\dots).$$Z_E(p_1,p_2,\dots)=\exp(p_1+\frac{p_2}{2}+\frac{p_3}{3}+\dots)$$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 StructuresStructures", 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 into the category of finite sets, that is -- roughly -- a machine that produces a finite set of objects (called "combinatorial structures") given a finite set (of "labels").

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.

2 added 34 characters in body

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) is $Z_F(x,0,0,\dots)$.

2) The ordinary generating function for the isomorphism types of $F$ (in our case: integer partitions) 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)$

See Bergeron, Labelle, Leroux, "Combinatorial Species and Tree-like Structures"

1