Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
It seems that your first question is a duplicate. – Matemáticos Chibchas Jan 28 '13 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! – amWhy Feb 4 '13 at 15:06
up vote 3 down vote accepted

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

share|cite|improve this answer

It is somewhat surprising that there was no answer in terms of generating function as these are quite straightforward. The species of set partitions is given by $$\mathfrak{P}(\mathfrak{P_{\ge 1}}(\mathcal{Z}))$$ and hence it has the exponential generating function $$G(z) = \exp(\exp(z)-1).$$ The species of set partitions excluding singletons is $$\mathfrak{P}(\mathfrak{P_{\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 :=
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;

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


F :=
    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);

q := n -> (-1)^n*add(binomial(n, k)*(-1)^k*bell(k), k=0..n);
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.