Results 1 to 4 of 4

Math Help - Help with partitions

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    17

    Help with partitions

    I was given the following formula to figure this problem out as I was suppose to complete a table of Stirling Numbers of the Second Kind.

    S(n,k) = S(n-1, k-1) + k*S(n-1, k)

    So lets say we have S(5,3) so n=5 and k=3 and then I get this far:

    S(5,3) = S(5-1, 3-1) +3*S(5-1, 3)

    S(5,3) = S(4, 2) +3*S(4, 3)

    What do I do with the S and the number within the parenthesis?

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Bman900 View Post
    I was given the following formula to figure this problem out as I was suppose to complete a table of Stirling Numbers of the Second Kind.

    S(n,k) = S(n-1, k-1) + k*S(n-1, k)

    So lets say we have S(5,3) so n=5 and k=3 and then I get this far:

    S(5,3) = S(5-1, 3-1) +3*S(5-1, 3)

    S(5,3) = S(4, 2) +3*S(4, 3)

    What do I do with the S and the number within the parenthesis?

    Thanks in advance!
    For a recursion, you have one or more base cases, and then rules that reduce all other cases to base case(s). Here, you have omitted the base cases, thus the recursion will never end. The base cases should be in your notes, else google "stirling second kind" and get them online.

    Well I'll save you some trouble, they are here

    Stirling numbers of the second kind - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2010
    Posts
    17
    Well I was suppose to fill out that exact table. I just didn't want to copy it without undertstanding it. Now I kinda graps the concept.

    But we also did something like this: P(8,4) = 5 Is there a way we can figure this out without listing all the possible options?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Bman900 View Post
    Well I was suppose to fill out that exact table. I just didn't want to copy it without undertstanding it. Now I kinda graps the concept.

    But we also did something like this: P(8,4) = 5 Is there a way we can figure this out without listing all the possible options?
    Where did the P come from? You have not defined P(n,k).

    If you are only given a recurrence relation and asked to fill out a table/find a value, then you will need to either

    (1) start at the base cases and work towards the values you need to find

    (2) start at the values you need to find and work towards the base cases

    (3) type it into a programming language/CAS and have the computer do that for you

    (4) solve the recurrence to obtain a closed form expression, then use your expression to evaluate

    (5) find another clever method that doesn't directly use the recurrence relation but some other property you've proven from it

    It's the same as if I give you that the Fibonacci numbers are defined by f(0)=0, f(1)=1, and f(n)=f(n-1)+f(n-2) for n>1. What is f(20)?

    Using JUST the recurrence relation, the way you do it is to find ALL the values from f(2) through f(20), although of course there are better methods such as using the closed-form expression involving the golden ratio, or matrix exponentiation, or various identities that can be proven.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Partitions
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: October 4th 2010, 02:40 AM
  2. more partitions
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 15th 2010, 04:28 PM
  3. partitions
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: March 15th 2010, 04:22 PM
  4. partitions
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 11th 2010, 03:53 PM
  5. Partitions of n
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2009, 01:50 PM

Search Tags


/mathhelpforum @mathhelpforum