Homework 12

Stirling Numbers of the Second Kind, represented as S(n, k), count (among

other things) the number of ways to divide n objects into exactly k nonempty

piles. For example, there are 7 ways to divide four objects into two piles:

{1, 2, 3} {4}

{1, 2, 4} {3}

{1, 3, 4} {2}

{2, 3, 4} {1}

{1, 2} {3, 4}

{1, 3} {2, 4}

{1, 4} {2, 3}

Stirling Numbers of the Second Kind can be calculated using the following

recurrence relation:

S(n, k) = (

1, if k = 1 or k = n

kS(n − 1, k) + S(n − 1, k − 1), otherwise

Use this recurrence to answer the questions below. If you are interested why

this recurrence is true, you may see the footnote1 below; however, you do not

need to understand why this works in order to solve the problem.

1. Describe a na¨ıve recursive algorithm that computes S(n, k) using this recurrence.

2. What map implementation would you use for a memoized dynamic programming solution to this problem and why?

3. Describe a memoized dynamic programming solution to this problem.

1When adding one element to go from n − 1 to n, the new element can either go in a pile

by itself or be added to an existing pile. There are S(n − 1, k − 1) ways to put these n − 1

elements into k − 1 piles, and we can create the k

th pile by putting the new element by itself.

On the other hand, there are S(n − 1, k) ways to put the n − 1 elements into k piles, and we

can add the new element to any of the k piles. There’s only one way to put everything into

one pile, and the only way to put n elements into n piles is to put everything in its own pile.

1

## Reviews

There are no reviews yet.