The study of mathematical combinatorics really fascinates me. Last week while working on some code I needed a function to calculate the number of ways to evenly divide n different items into k equally-sized groups. This turns out to be a surprisingly difficult problem. For example, if n = 4 (and the items are A, B, C, D) and k = 2, then there are Choose(4,2) / 2 = 3 ways to evenly divide the 6 items:

(A,B) and (C,D)

(A,C) and (B,D)

(A,D) and (B,C)

Notice we have to divide Choose(4,2) by 2 to eliminate some duplicates. Now suppose we have n = 12 items and k = 4 groups and so the size of each group is 12/4 = 3. We can compute the number of ways to evenly divide the 12 items like this:

= [Choose(12,3) * Choose(9,3) * Choose(6,3) * Choose(3,3)] / 4!

= [220 * 84 * 20 * 1] / 24

= 15,680

First we choose any 3 items for the first group. Next we choose any 3 items from the remaining 12-3 = 9 items for the second group. Then choose any 3 items from the remaining 9-3 = 6 items, and finally choose 3 items from the remaining 3 items. We divide by 4! to eliminate duplicates like {(A,B,C), (D,E,F), (G,H,I), (J,K,L)} and {( J,K,L), (D,E,F), (G,H,I), (A,B,C)}.

Because these numbers can get really huge I coded up the solution in C# using the System.Numerics BigInteger type. I needed helper functions Choose() and Factorial() which are interesting sub-problems by themselves. Here is the Choose() function:

public static BigInteger Choose(int n, int k)

{

if (n < 0 || k < 0)

throw new Exception(“Invalid negative parameter in Choose()”);

if (n < k)

return 0; // special case

if (n == k)

return 1;

BigInteger delta, iMax;

if (k < n – k) // ex: Choose(100,3)

{

delta = n – k;

iMax = k;

}

else // ex: Choose(100,97)

{

delta = k;

iMax = n – k;

}

BigInteger ans = delta + 1;

for (BigInteger i = 2; i <= iMax; ++i)

{

checked { ans = (ans * (delta + i)) / i; }

}

return ans;

} // Choose()

An interesting problem.