# Partitions and Bell numbers

Let $F(n)$ be the number of all partitions of $[n]$ with no singleton blocks.

1. Find the recursive formula for the numbers $F(n)$ in terms of the numbers $F(i)$, with $i ≤ n − 1$

2. Find a formula for $F(n)$ in terms of the Bell Numbers $B(n)$.

For the first question, it's obviously something like $F(n+1) = \sum_{i=0}^n {n \choose i} F(i)$, since that's what it is for Bell numbers, but I really can't see how I'd get to the correct formula.

For the second one, I believe I'm supposed to use inclusion-exclusion, but I'm a bit lost.

• It seems that your first question is a duplicate. Jan 28, 2013 at 17:53
• tijme: note that if you find an answer to be helpful, you may choose to accept one answer per question asked. To accept an answer, click on the "greyed out" check-mark to the left of the answer you want to accept. When you get a little more reputation (+30 or more), you can also "upvote" as many answers as you'd like! Feb 4, 2013 at 15:06

Say that a partition of $$[n]$$ is good if it has no singleton blocks and bad otherwise. $$B_n$$, the $$n$$-th Bell number, is the total number of partitions of $$[n]$$. If $$b(n)$$ is the number of bad partitions of $$[n]$$, $$F(n)=B_n-b(n)$$. As usual, a little data can’t hurt. By direct enumeration of $$F(n)$$ and $$b(n)$$ and a table of the Bell numbers I find

$$\begin{array}{cccc} n&F(n)&b(n)&B_n\\ \hline 0&0&1&1\\ 1&0&1&1\\ 2&1&1&2\\ 3&1&4&5\\ 4&4&11&15\\ 5&11&41&52\\ 6&41&162&203 \end{array}$$

This very strongly suggests that $$F(n+1)=b(n)$$ for $$n\ge 1$$. To see why this is true, suppose first that $$\pi$$ is a bad partition of $$[n]$$; then we can form a good partition of $$[n+1]$$ by gathering all of the singletons of $$\pi$$ into a single block and putting $$n+1$$ into that block. Conversely, if $$\pi$$ is a good partition of $$[n+1]$$, we can form a bad partition of $$[n]$$ by taking the block of $$\pi$$ containing $$n+1$$, throwing away $$n+1$$, and converting the rest of the block to singletons. These operations are clearly inverses of each other and thus establish a bijection between bad partitions of $$[n]$$ and good partitions of $$[n+1]$$.

This immediately gives us the recurrence $$F(n+1)=B_n-F(n)$$. Unwrapping the recurrence, we find that:

\begin{align*} F(n+1)&=B_n-F(n)\\ &=B_n-\big(B_{n-1}-F(n-1)\big)\\ &=B_n-B_{n-1}+F(n-1)\\ &=B_n-B_{n-1}+\big(B_{n-2}-F(n-2)\big)\\ &=B_n-B_{n-1}+B_{n-2}-F(n-2)\\ &\;\vdots\\ &=\sum_{i=0}^k(-1)^iB_{n-i}+(-1)^{k+1}F(n-k)\\ &\;\vdots\\ &=\sum_{i=0}^{n-1}(-1)^iB_{n-i}\;. \end{align*}

Added: For the first question, let $$\pi$$ be a good partition of $$[n+1]$$, and let $$B$$ be the block containing $$n+1$$. There is at least one element of $$[n]$$ in that block, so $$[n]\setminus B$$ is a proper subset of $$[n]$$. If $$|[n]\setminus B|=k$$, $$\pi\setminus\{B\}$$ can be any one of the $$F(k)$$ good partitions of $$[n]\setminus B$$. Conversely, all good partitions of $$[n+1]$$ can be obtained by choosing a proper subset $$S$$ of $$[n]$$, forming a good partition of $$S$$, and adding to it the block $$\{n+1\}\cup([n]\setminus S)$$. Since $$[n]$$ has $$\binom{n}k$$ subsets of cardinality $$k$$, $$[n+1]$$ has $$\binom{n}kF(k)$$ good partitions in which the block containing $$n+1$$ has $$n-k$$ other elements, and it follows that $$F(n+1)=\sum_{k=0}^{n-1}\binom{n}kF(k).$$

It is somewhat surprising that there was no answer in terms of generating function as these are quite straightforward. The combinatorial class of set partitions is given by $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}(\textsc{SET}_{\ge 1}(\mathcal{Z}))$$ and hence it has the exponential generating function $$G(z) = \exp(\exp(z)-1).$$ The combinatorial class of set partitions excluding singletons is $$\textsc{SET}(\textsc{SET}_{\ge 2}(\mathcal{Z}))$$ and hence it has the exponential generating function $$H(z) = \exp(\exp(z)-1-z).$$ To answer the first question differentiate $$H(z)$$ to get $$H'(z) = H(z) \times (\exp(z)-1).$$ Here is a useful observation which I have included in several of my posts. When we multiply two exponential generating functions of the sequences $$\{a_n\}$$ and $$\{b_n\}$$ we get that $$A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Therefore when we extract coefficients from the differentiated equation for $$H(z)$$ we get $$F(n+1) = \sum_{k=0}^{n-1} {n\choose k} F(k) \times 1 = \sum_{k=0}^{n-1} {n\choose k} F(k).$$ The upper limit is $$n-1$$ and not $$n$$ because $$\exp(z)-1$$ has no constant term. This is valid for $$n\ge 1.$$ The base cases are $$F(0)=1$$ and $$F(1)=0.$$

For the second part of the question rewrite the equation for $$H(z)$$ like this: $$H(z) = \exp(\exp(z)-1)\exp(-z).$$ Using the convolution of exponential generating functions one more time and recognising $$G(z)$$ from above we obtain that $$F(n) = \sum_{k=0}^n {n\choose k} B_k (-1)^{n-k} = (-1)^n \sum_{k=0}^n {n\choose k} (-1)^k B_k.$$

Here is some Maple code to explore these numbers.


with(combinat, bell);
with(combinat, setpartition);

nsb :=
proc(n)
option remember;
local p, admit, s, res, k;

res := 0;
for p in setpartition([seq(k, k=1..n)]) do

for s in p do
if nops(s) = 1 then
break;
fi;
od;

if admit then res := res+1; fi;
od;

res;
end;

F :=
proc(n)
option remember;

if n=0 then return 1 fi;
if n=1 then return 0 fi;