How many ways can you distribute
n different objects into
k
nonempty bundles? Traditionally this number is denoted by
{nk}, for example
{42}=7 because 4
objects — call them A, B, C, D — can be distributed
into two bundles
in the seven ways
A-BCD B-ACD C-ABD D-ABC AB-CD AC-BD AD-BC
To determine the value of these numbers, we will use the recurrence relation
- for n,k>0,{nk}=k{n−1k}+{n−1k−1}
- with the base cases {00}=1 and
for n>0,{n0}=0 and for
k>0,{0k}=0
Write a static method
bundleWays(n, k)
that uses
dynamic programming to compute
{nk}.
Using a recursive method will be too slow.