Take the 2-minute tour ×
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.

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|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.