Results 1 to 3 of 3

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

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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)}
    $
    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: Sep 9th 2011, 04:30 AM
  2. Consecutive integers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Apr 22nd 2010, 03:41 AM
  3. Consecutive integers help. Anyone?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Mar 26th 2009, 08:46 PM
  4. Replies: 4
    Last Post: Feb 24th 2008, 03:08 PM
  5. n consecutive integers
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: Oct 22nd 2007, 06:23 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum