Results 1 to 3 of 3

Math Help - Finding the number of partitions without consecutive integers in each block

  1. #1
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    48
    Awards
    1

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Let <br />
f\left( {n,k} \right)<br />
be the number of partitions of <br /> <br />
\left\{ {1,...,n} \right\}<br /> <br />
into k classes such that no 2 consecutive integers are in the same class.

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

    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 <br />
\left\{ {1,...,n - 1} \right\}<br />
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 <br />
f\left( {n,k} \right) = \left\{ {\begin{array}{*{20}c}<br />
{n - 1} \\<br />
{k - 1} \\<br /> <br />
\end{array} } \right\}{\text{ }} where <br />
\left\{ {\begin{array}{*{20}c}<br />
n \\<br />
k \\<br /> <br />
\end{array} } \right\}<br />
are the Stirling numbers of the second kind <br />
{({\text{ }}n,k \geqslant 1)}<br />
(*)


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


    (*)
    <br />
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]<br />

    Sum: <br />
\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)<br />

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

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

    It follows: <br />
F_k \left( x \right) = \tfrac{{x^{k - 1} }}<br />
{{\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}<br />
   n  \\<br />
   {k - 1}  \\<br /> <br />
 \end{array} } \right\} \cdot x^n } } \right) \cdot x<br />
(in the same way we can get the Generating function for the Stirling numbers of the second kind)

    Thus: <br />
F_k \left( x \right) = \sum\limits_{n = 1}^\infty  {\left\{ {\begin{array}{*{20}c}<br />
   {n - 1}  \\<br />
   {k - 1}  \\<br /> <br />
 \end{array} } \right\} \cdot x^n {\text{  }}({\text{ }}n,k \geqslant 1)} <br />
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    48
    Awards
    1
    Thanks a million, PaulRS!

    Your post has been extremely helpful and illuminating.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Consecutive Integers
    Posted in the Algebra Forum
    Replies: 9
    Last Post: September 9th 2011, 05:30 AM
  2. Consecutive integers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 22nd 2010, 04:41 AM
  3. Consecutive integers help. Anyone?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 26th 2009, 09:46 PM
  4. Replies: 4
    Last Post: February 24th 2008, 04:08 PM
  5. n consecutive integers
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: October 22nd 2007, 07:23 PM

Search Tags


/mathhelpforum @mathhelpforum