Dividing 12 people into any number of groups, such that person A and B are not in the same group?

Question

In how many ways can you divide 12 people into any number of groups, such that person A and B are not in the same group?

I am trying to solve this question and so far I am thinking of this in terms of Stirling numbers of the second kind.

The way I am thinking of this problem is as follows: Calculate the ways to partition 12 in to any number of blocks (greater than 2 since we can't have 1 group as that group must contain A & B together) $$ \sum_{i = 2}^{12} S(12, i) = 4,213,596$$

and then subtract that from the possible ways of partitioning 11 people in to any number of blocks (here I am making A & B the same person AB so that they are always in the same group) giving the following:

$$\sum_{i = 1}^{11} S(11,i) = 678,570$$

subtracting from each other I get: $$3,535,026$$

Which seems quite high in my opinion. Is this the correct approach or am I missing something?

Answer 1

You're almost right. First off, it's far more natural to think in terms of Bell numbers than Stirling numbers of the second kind.

You shouldn't have undercounted $B_{12}$ by one. You are correct that a single unit with all twelve members is not a successful configuration, but it gets subtracted by the single unit in $B_{11}$. Thus, the correct answer is $3\ 535\ 027$.

This sequence is A005493 in OEIS. Indeed, it notes:

Number of set partitions of (n+2) elements where two specific elements are clustered separately. Example: a(1)=3 because 1/2/3, 1/23, 13/2 are the 3 set partitions with 1, 2 clustered separately. - Andrey Goder (andy.goder(AT)gmail.com), Dec 17 2007