Description
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