Loading [MathJax]/jax/output/HTML-CSS/jax.js
PartitionCount
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{n1k}+{n1k1}
  • 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.
25
 
1
public class PartitionCount {
2
   public static long bundleWays(int n, int k) {
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   }
17
   
18
   public static void main(String[] args) {
19
      for (int n=0; n<=5; n++) {
20
         for (int k=0; k<=n; k++)
21
            StdOut.printf("{%d %d} = %-3d  ", n, k, bundleWays(n, k));
22
         StdOut.println();
23
      }
24
   }
25
}