2006 iTest Problems/Problem 33

Six students sit in a group and chat during a complicated mathematical lecture. The professor, annoyed by the chatter, splits the group into two or more smaller groups. However, the smaller groups with at least two members continue to produce chatter, so the professor again chooses one noisy group and splits it into smaller groups. This process continues until the professor achieves the silence he needs to teach Algebraic Combinatorics. Suppose the procedure can be carried out in ways, where the order of group breaking matters (if A and B are disjoint groups, then breaking up group A and then B is considered different form breaking up group B and then A even if the resulting partitions are identical) and where a group of students is treated as an unordered set of people. Compute the remainder obtained when is divided by .

Solution

Let be a partition of 6, and let be the number of ways that a group of 6 students broken up according to the partition can be split until all are silent. We know that trivially. Then we calculate as follows:

(because the group of two can be split in only one way). (because the two groups of two can be split in two ways). (because the group of three can be split in three ways). (because the three groups of two can be split in three ways). (because we can either split the group of three or the group of two). (because we can either split the group of four into one and three or two and two). (because there are two ways to pick the group to split and three ways to split that group). (because we can split the group of four into three and one, or the group of four into two and two, or the group of two). (because we can either split the group of five into four and one or three and two). (because we can either split the group of six into five and one, or four and two, or three and three).

Thusly, our answer is modulo , which is .