Thread: 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!

Originally Posted by Bman900

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

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?

Originally Posted by Bman900

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.