Page 292 Exercise 15

This problem is a nice application of Sterling numbers.  Sterling numbers are discussed quite thoroughly in Concrete Mathematics by Ronald Graham, Donald Knuth, and Oren Patashnik.  Sterling numbers are divided into two varieties, and it is the first kind that is of interest to us.  Sterling numbers of the first kind are used to indicate the number of partitions that can be produced from n objects taken k at a time.  For example, if we
take three objects and split them into two groups, we will obtain 3 distinct groupings: {1} U {23}, {2} U {13}, and {3} U {12}.

 
Actually the case of k = 2 is somewhat trickier than k = anything else, and I refer you to Graham, et al.  The answer for k = 2, however, is always 2ⁿ - 1.