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

• November 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 $\{1,...,n\}$, such that no two consecutive integers appear in the same block of a partition is the Bell number $B_{n-1}$.

***

We know that the number of partitions of an $n$-element set is $B_n$. For example, if we have a 3-element set $\{1,2,3\}$ then ALL possible partitions of that set would be
$\{\{1,2,3\}\};\{\{1,2\},\{3\}\};\{\{1,3\},\{2\}\}; \{\{2,3\},\{1\}\};\{\{1\},\{2\},\{3\}\}$
and therefore $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 $\{\{1,3\},\{2\}\}$ and $\{\{1\},\{2\},\{3\}\}$ - there are two of them, which is exactly the second Bell number, $B_2$, and in fact there are only two partitions of a 2-element set, say, $\{1,2\}$; the first one is $\{\{1,2\}\}$ and the second one is $\{\{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 $B_2$. But, how to give a combinatorial proof that the number of such partitions of a $n$-element set is $B_{n-1}$?

Many thanks! :)
• November 8th 2008, 05:30 PM
PaulRS
Let $
f\left( {n,k} \right)
$
be the number of partitions of $

\left\{ {1,...,n} \right\}

$
into $k$ classes such that no 2 consecutive integers are in the same class.

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

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

From there we get $
f\left( {n,k} \right) = \left\{ {\begin{array}{*{20}c}
{n - 1} \\
{k - 1} \\

\end{array} } \right\}{\text{ }}$
where $
\left\{ {\begin{array}{*{20}c}
n \\
k \\

\end{array} } \right\}
$
are the Stirling numbers of the second kind $
{({\text{ }}n,k \geqslant 1)}
$
(*)

Now we directly sum over k: $
\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} }
$

(*)
$
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: $
\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: $
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 $
F_k \left( x \right) = \sum\limits_{n = 0}^\infty {f\left( {n,k} \right) \cdot x^n }
$
(considering the initial values)

From there: $
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 $
F_1 \left( x \right) = \sum\limits_{n = 0}^\infty {f\left( {n,1} \right) \cdot x^n } = x
$

It follows: $
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: $
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)}
$
• November 8th 2008, 08:05 PM
gusztav
Thanks a million, PaulRS!