Partitioning a set of items is a problem I run across rather often. Determining the number of ways you can partition a set of n items into k groups is a surprisingly difficult problem. Suppose you have a set of n = 4 items and want to partition those items into k = 2 groups. How many ways can you do this? There are 7 possible partitions of 4 items into 2 groups:

 

(a)   (b,c,d)
(b)   (a,c,d)
(c)   (a,b,d)
(d)   (a,b,c)
(a,b)   (c,d)
(a,c)   (b,d)
(a,d)   (b,c)

 

It turns out that the number of possible partitions is given by an equation called Stirling numbers of the second kind, S(n,k). It is an interesting function which increases very rapidly. S(4,2) = 7 and S(6,4) = 65. I was working on a problem recently with n = 435 (the number of members in the U.S. House of Representatives) and k = 2. The number of ways you can partition 435 items into 2 groups is 4.4 * 10 to the 130th power. This is an unimaginably huge number. Wikipedia has a good article on Stirling numbers of the second kind if you want to know more.