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.

Solution 1:

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).$$

Solution 2:

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
        admit := true;

        for s in p do
            if nops(s) = 1 then
                admit := false;
                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;

    add(binomial(n-1, k)*F(k), k=0..n-2);
end;

q := n -> (-1)^n*add(binomial(n, k)*(-1)^k*bell(k), k=0..n);