Results 1 to 9 of 9

Math Help - Recurrence formula

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    308

    Recurrence formula

    1. Let denote the number of ways in which a set of elements can be partitioned into non-empty subsets. For example, , corresponding to:











    How do I do this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by usagi_killer View Post
    1. Let denote the number of ways in which a set of elements can be partitioned into non-empty subsets. For example, , corresponding to:











    How do I do this?
    Problem: given a set of n elements in ow many ways can one partition the set into non-empty subsets.

    Solution: Let us denote {n}\brace{k} as the number of ways we can parition \left\{1,\cdots,n\right\} into k blocks. Clearly, then the number of ways we can partition the set is \sum_{k=1}^{n}{{n}\brace{k}}.

    Let us first begin by finding a recurrence relation for {n}\brace{k}. To do this let S_k=\left\{P:P\text{ is a partition of }\left\{1,\cdots,n\right\}\text{ into }k\text{ blocks}\right\}. Partition S_k into two blocks, namely: those elements such that \{n\}\in P and those elements such that \{n\}\notin P. Since \left|S_k\right|={{n}\brace{k}} it follows that the sum of the cardinality of the two blocks must be equal to {n}\brace{k}.

    To calculate the number of elements in the first block, note that the deletion of \{n\} in each of the partitions would result in a set of partitions that is exactly describing the number of ways one can partition \left\{1,\cdots,n-1\right\} into k-1 blocks, or in other words {n-1}\brace{k-1}. Now note that the deletion of \{n\} did not, in any way, change the number of partitions in block one. It follows that the cardinality of the first block is {n-1}\brace{k-1}.

    To calculate the number of elements in the second block we employ a similar method. Instead of this time erasing \{n\} in each of the partitions, this time locate the block in each partition that contains n. From this block, erase n. Notice that this time we have not changed k but have reduced each block in the partition to a partition of n-1. But, there is multiplicity in these blocks. Exactly how many are there? A quick argument shows that each new partiton of n-1 will be repeated k times. Thus, since the deletion method we used did not change the cardinality of the second block we may conclude that the cardinality is k{{n-1}\brace{k}}.

    It immediately follows that {{n}\brace{k}}={{n-1}\brace{k-1}}+k{{n-1}\brace{k}}.

    To make f_k(n)={{n}\brace{k}} a valid sequence for a fixed positive k we must make the convention (which in no way affects the problem at hand) that {{n}\brace{k}}=0,\text{ }n<k, {{0}\brace{0}}=0, and {{{n}\brace{0}}},\text{ }n\ne0. Now our recurrence relation is legitimate over all n\in\mathbb{N}.

    An almost immediate consequence of of the way we defined {n}\brace{k} is that {{n}\brace{n}}={{n}\brace{1}}=1 since the only way to partition \left\{1,\cdots,n \right\} into n blocks is \{1\},\cdots,\{n\} and the only way to parition \left\{1,\cdots,n\right\} into 1 block is \{1,\cdots,n\}. So in your example we'd need to calculate \sum_{k=1}^{3}{{3}\brace{k}}, but since {{3}\brace{1}}={{3}\brace{3}}=1 we must only compute {3}\brace{2}. But, by our recurrence relation we see that {{3}\brace{2}}={{2}\brace{1}}+2{{2}\brace{2}}=1+2=  3. So then \sum_{k=1}^{3}{{3}\brace{k}}=1+3+1=5

    Remark: I could take this even further and find a generating function for this problem, but I believe that you should give it a try on your own.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by usagi_killer View Post
    1. Let denote the number of ways in which a set of elements can be partitioned into non-empty subsets. For example, , corresponding to:











    How do I do this?
    Hi - Here is an attempt

    Number of ways = \sum_{i=1}^{n}\theta(n,i)

    where,
    recursion equation is
    \theta(n,i) = \theta(n-1,i)i+\theta(n-1,i-1)
    \theta(n,1)=1

    Basically \theta(n,i) is number of ways to divide n elements in i groups.

    I might have complicated it. But this looks most straight fwd to me. Haven't been able to work out a closed from formula.
    Let me know if you need more inputs on how I came up with the recuursive definition.
    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    P.S. If you want me to show you how to do the generating function, just let me know.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    This problem can be solved by adding up a popular function called Stirling number. {n}\brace{k}<br />
in #2 is a notation for Stirling number of the second kind. You might find this article useful
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by Drexel28 View Post
    P.S. If you want me to show you how to do the generating function, just let me know.
    Maybe just a push so that we can try it out first - I really do not know much about generating functions.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    This is an interesting topic.

    The nth Bell number, b_{n}, is the number of ways to partition a set of n objects into subsets.

    You already have b_{3}=5 as an example.

    The sequence of Bell numbers is 1,1,2,5,15,52,.....

    The exponential generating function for the Bell number is

    e^{e^{x}-1}. This can be derived by using b_{n+1}=\sum_{k=0}^{\infty}\frac{k^{n-1}}{(k-1)!}

    The general formula is b_{n}=\frac{1}{e}\sum_{k=0}^{\infty}\frac{k^{n}}{k  !}

    Note the formula looks a whole lot like the MacLaurin series for e, huh?.

    With some effort, these can be derived.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Apr 2009
    Posts
    308
    Thank you guys, I really appreciate the help, I understand how to do this question now
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by galactus View Post
    This is an interesting topic.

    The nth Bell number, b_{n}, is the number of ways to partition a set of n objects into subsets.

    You already have b_{3}=5 as an example.

    The sequence of Bell numbers is 1,1,2,5,15,52,.....

    The exponential generating function for the Bell number is

    e^{e^{x}-1}. This can be derived by using b_{n+1}=\sum_{k=0}^{\infty}\frac{k^{n-1}}{(k-1)!}

    The general formula is b_{n}=\frac{1}{e}\sum_{k=0}^{\infty}\frac{k^{n}}{k  !}

    Note the formula looks a whole lot like the MacLaurin series for e, huh?.

    With some effort, these can be derived.
    Just a flourish of the hands and some prestidigitation and this generating function appeared, huh?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. finding a formula for a recurrence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 8th 2010, 03:04 PM
  2. Need help solving recurrence formula
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 7th 2009, 01:08 PM
  3. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 08:56 PM
  4. recurrence formula
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 4th 2008, 10:23 AM
  5. [SOLVED] Recurrence formula
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 28th 2008, 08:21 AM

Search Tags


/mathhelpforum @mathhelpforum