Exponential generating function of partitions of set [n]

Question

Find the exponential generating function of the partitions of the set [n], all of whose classes have a prime number of elements.

The only thing I came up with was

$$\sum\limits_{\textrm{t prime}} = \frac{f(t) x^{t}}{t!}$$ Where $f(t)$ is the number of partitions of size t. I'm not sure if this is correct though.

Answer 1

You want the following theorem, which I quote from Miklós Bóna, Introduction to Enumerative Combinatorics:

Theorem. Let $a_n$ be the number of ways to carry out a certain task on an $n$-element set, and set $a_0=0$. For $n\ge 1$, let $h_n$ be the number of ways to partition $[n]$ into an arbitrary number of non-empty blocks, and then to carry out the first task on each of these blocks. Set $h_0=1$. If $A(x)=\sum_{n\ge 0}a_n\frac{x^n}{n!}$ and $H(x)=\sum_{n\ge 0}h_n\frac{x^n}{n!}$, then $$H(x)=e^{A(x)}\;.$$

Suppose that we want the exponential generating function for the number of partitions of $[n]$ into parts of size $2$. The task of organizing an $n$-element set into a $2$-element block can be carried out in $1$ way if $n=2$ and in $0$ ways if $n\ne 2$, so $A(x)=\frac{x^2}{2!}$, and the exponential generating function for the number of ways to partition $[n]$ into $2$-element blocks is therefore

$$H(x)=e^{x^2/2!}=e^{x^2/2}\;.\tag{1}$$

As a check, we know that

$$e^{x^2/2}=\sum_{n\ge 0}\frac{x^{2n}}{2^nn!}=\sum_{n\ge 0}(2n-1)!!\frac{x^{2n}}{(2n)!}\;,$$

so $(1)$ implies that

$$h_n=\begin{cases} (2n-1)!!,&\text{if }n\text{ is even}\\ 0,&\text{if }n\text{ is odd}\;, \end{cases}$$

a result justified without generating functions here.

You also want the product theorem.

Theorem. Denote by $f_n$ the number of ways to carry out a task on $[n]$, and denote by $g_n$ the number of ways to carry out another task on $[n]$. Let $F(x)$ and $G(x)$ be the exponential generating functions of the sequences $\langle f_n:n\in\Bbb N\rangle$ and $\langle g_n:n\in\Bbb N\rangle$. Let $h_n$ be the number of ways to choose a subset $S$ of $[n]$, carry out the first task on $S$, and then carry out the second task on the set $[n]\setminus S$. Let $H(x)$ be the exponential generating function of the sequence $\langle h_n:n\in\Bbb N\rangle$. Then $H(x)=F(x)G(x)$.

Thus, the exponential generating function for the number of partitions of $[n]$ into parts of size $1,2$, or $3$ must be

$$g(x)=\left(e^{x^1/1!}\right)\left(e^{x^2/2!}\right)\left(e^{x^3/3!}\right)=\exp\left(x+\frac{x^2}2+\frac{x^3}6\right)\;.$$

Think about why the product theorem generalizes to an infinite number of tasks, and you’ll be able to get the exponential generating function that you want.