# Finding the number of partitions without consecutive integers in each block

• Nov 8th 2008, 04:44 AM
gusztav
Finding the number of partitions without consecutive integers in each block
Hello, I'd be really grateful for any help with this problem:

Show that the number of partitions of the set $\displaystyle \{1,...,n\}$, such that no two consecutive integers appear in the same block of a partition is the Bell number $\displaystyle B_{n-1}$.

***

We know that the number of partitions of an $\displaystyle n$-element set is $\displaystyle B_n$. For example, if we have a 3-element set $\displaystyle \{1,2,3\}$ then ALL possible partitions of that set would be
$\displaystyle \{\{1,2,3\}\};\{\{1,2\},\{3\}\};\{\{1,3\},\{2\}\}; \{\{2,3\},\{1\}\};\{\{1\},\{2\},\{3\}\}$
and therefore $\displaystyle B_3=5$. But in our problem, we are interested only in those partitions of a set which consist of blocks without any consecutive integers. So, in the above example, we would only be interested in partitions $\displaystyle \{\{1,3\},\{2\}\}$ and $\displaystyle \{\{1\},\{2\},\{3\}\}$ - there are two of them, which is exactly the second Bell number, $\displaystyle B_2$, and in fact there are only two partitions of a 2-element set, say, $\displaystyle \{1,2\}$; the first one is $\displaystyle \{\{1,2\}\}$ and the second one is $\displaystyle \{\{1\},\{2\}\}$.

Here, we have shown that the number of partitions of a 3-element set such that there are no consecutive integers in any block is $\displaystyle B_2$. But, how to give a combinatorial proof that the number of such partitions of a $\displaystyle n$-element set is $\displaystyle B_{n-1}$?

Many thanks! :)
• Nov 8th 2008, 05:30 PM
PaulRS
Let $\displaystyle f\left( {n,k} \right)$ be the number of partitions of $\displaystyle \left\{ {1,...,n} \right\}$ into $\displaystyle k$ classes such that no 2 consecutive integers are in the same class.

We'll see that: $\displaystyle f\left( {n,k} \right) = f\left( {n - 1,k - 1} \right) + \left( {k - 1} \right) \cdot f\left( {n - 1,k} \right)$ holds. $\displaystyle {({\text{ }}n,k \geqslant 1)}$

Indeed, the first term corresponds to the number of cases in which $\displaystyle n$ lives alone in its own class, otherwise, if we have built a partition of $\displaystyle \left\{ {1,...,n - 1} \right\}$ into $\displaystyle k$ classes where no 2 integers in a same class are consecutive, the number $\displaystyle n$ may be placed in $\displaystyle k-1$ of them, since it can't go where $\displaystyle n-1$ is.

From there we get $\displaystyle f\left( {n,k} \right) = \left\{ {\begin{array}{*{20}c} {n - 1} \\ {k - 1} \\ \end{array} } \right\}{\text{ }}$ where $\displaystyle \left\{ {\begin{array}{*{20}c} n \\ k \\ \end{array} } \right\}$ are the Stirling numbers of the second kind $\displaystyle {({\text{ }}n,k \geqslant 1)}$ (*)

Now we directly sum over k: $\displaystyle \sum\limits_k {f\left( {n,k} \right)} = \sum\limits_k {\left\{ {\begin{array}{*{20}c} {n - 1} \\ {k - 1} \\ \end{array} } \right\} = B_{n - 1} }$

(*)
$\displaystyle f\left( {n,k} \right) \cdot x^n = x \cdot \left[ {f\left( {n - 1,k - 1} \right) \cdot x^{n - 1} + \left( {k - 1} \right) \cdot f\left( {n - 1,k} \right) \cdot x^{n - 1} } \right]$

Sum: $\displaystyle \sum\limits_{n = 1}^\infty {f\left( {n,k} \right) \cdot x^n } = x \cdot \left( {\sum\limits_{n = 0}^\infty {f\left( {n,k - 1} \right) \cdot x^n } + \left( {k - 1} \right) \cdot \sum\limits_{n = 0}^\infty {f\left( {n,k} \right) \cdot x^n } } \right)$

Thus: $\displaystyle F_k \left( x \right) = x \cdot \left[ {F_{k - 1} \left( x \right) + \left( {k - 1} \right) \cdot F_k \left( x \right)} \right]{\text{ ( }}k \geqslant 1)$ where $\displaystyle F_k \left( x \right) = \sum\limits_{n = 0}^\infty {f\left( {n,k} \right) \cdot x^n }$ (considering the initial values)

From there: $\displaystyle F_k \left( x \right) = \tfrac{{x^{k - 1} }} {{\left[ {1 - \left( {k - 1} \right) \cdot x} \right] \cdot ...\left[ {1 - x} \right]}} \cdot F_1 \left( x \right){\text{ ( }}k \geqslant 1)$ and since $\displaystyle F_1 \left( x \right) = \sum\limits_{n = 0}^\infty {f\left( {n,1} \right) \cdot x^n } = x$

It follows: $\displaystyle F_k \left( x \right) = \tfrac{{x^{k - 1} }} {{\left[ {1 - \left( {k - 1} \right) \cdot x} \right] \cdot ...\left[ {1 - x} \right]}} \cdot x = \left( {\sum\limits_{n = 0}^\infty {\left\{ {\begin{array}{*{20}c} n \\ {k - 1} \\ \end{array} } \right\} \cdot x^n } } \right) \cdot x$ (in the same way we can get the Generating function for the Stirling numbers of the second kind)

Thus: $\displaystyle F_k \left( x \right) = \sum\limits_{n = 1}^\infty {\left\{ {\begin{array}{*{20}c} {n - 1} \\ {k - 1} \\ \end{array} } \right\} \cdot x^n {\text{ }}({\text{ }}n,k \geqslant 1)}$
• Nov 8th 2008, 08:05 PM
gusztav
Thanks a million, PaulRS!