How many ways can 4 things of type A, 4 things of type B, and 4 things of type C be arranged so no two things of the same type are seated together?

Question

I have a question similar to the one posed here.

How many ways can 4 things of type A, 4 things of type B, and 4 things of type C be arranged so no two things of the same type are seated together?

This is similar to the question "If you have n boys and m girl, how many ways can you seat them so that no one is sitting next to the same gender?" but with three types of objects instead of two?

My best idea is 6 * 4!4!4! because there are six possible unique combinations of types A, B, and C. ABC ACB BAC BCA CAB CBA and there are 4 of each type. I haven't been able to find an example of this problem that deals with more than 2 types of things and it seems to fit the formula of m! * n₁!n₂!...n_m! where m is the number of sets and n is the number of things in those sets.

Is my thinking correct or does that formula not describe this situation? If not, what formula would?

Answer 1

A general solution for $n$ types of indistinguishable objects having $m$ each is

$$f(n,m) = n!.((n-1).(n-1)!)^{m-1}$$

To obtain this, you have to arrange the objects in such a way that there are $m$ continuous groups of each of the $n$ objects placed one after the other. The only constraint is that the last element of one group should be different from the first element of the next group.

Number of ways of arranging the first group = $n!$

Now, for a fixed first group, the number of choices for the first element is $(n-1)$, to prevent repetition at the boundary of two groups. Then you are free to permute the rest of the $(n-1)$ objects. This process will repeat for $(m-1)$ times

Answer 2

I don't see a simple way to do this, but the example is just small enough to do a case analysis by hand.

For now assume the four As are indistinguishable, and same for Bs and Cs. We will simply multiply by $(4!)^3$ at the end.

We will first place As and Bs, and by symmetry we can simply consider cases where the first letter is A -- we will multiply by $2$ to account for the placements starting with B.

The tricky part is that an intermediate step such as BABAABAB is allowed -- this has one "violation" (defined as a pair of adjacent same letters) which must be fixed by inserting a C there in the final step.

The case analysis is by no. of violations after placing As and Bs.

$0$ violation: There is $1$ such string, ABABABAB. The four Cs can go in any of the $9$ gaps. Total count $= 1 \times {9 \choose 4}$

Whenever there is a violation, we can conceptually group the adjacent equal letters together, e.g. consider BABAABAB as BABABAB. We will call the former the "expanded" string and the latter the "contracted" string. Note that:

• Multiple different expanded strings map to the same contracted string.

• The contracted string must have alternating letters, by definition.

• Contracted string length + no. of violations = expanded string length = $8$.

$1$ violation: If A is the first letter, the violation can only be B. The only possible contracted string is ABABABA, which expands into $3$ cases: ABBABABA, ABABBABA, ABABABBA. In each case, one C is constrained to undo the violation, and the other three Cs can go into any of the $8$ gaps of the contracted string. (Alternate view: the contracted B actually expands into, not just BB, but in fact BCB.) Total count is $3 \times {8 \choose 3}$.

$2$ violations: The only contracted string is ABABAB, with one A-violation and one B-violation. This expands into $9$ expanded strings: $3$ choices for the A-violation and $3$ choices for the B-violation. Expanding also uses up two Cs. The remaining two Cs can go into any of the $7$ gaps of the contracted string. Total count $= 9 \times {7 \choose 2}$.

$3$ violations: The only contracted string is ABABA, with one A-violation and two B-violations. This also expands into $9$ expanded strings: $3$ choices for the A-violation and $3$ choices for the B-violations: ABBABBA, ABBBABA, ABABBBA. Expanding uses up three Cs and the remaining C can go into any of the $6$ gaps of the contracted string. Total count $=9 \times {6 \choose 1}$.

$4$ violations: The only contracted string is ABAB, with two violations of each letter. This also expands into $9$ expanded strings: AABAAB, AAABAB, ABAAAB, and similarly for B. Expanding uses up all four Cs. Total count $= 9 \times 1$.

$5$ or more violations: These are possible (e.g. AAAABBBB has $6$ violations), but since they cannot be fixed by four Cs, we will ignore them.

So the total of the $0$ to $4$ violation cases $= {9 \choose 4} + 3 \times {8 \choose 3} + 9 \times [{7 \choose 2} + {6 \choose 1} + 1] = 546$. This only accounts for strings where A appears before B, so the final answer is $546 \times 2 = 1092$ (for indistinguishable As, etc).

And if you want to consider the four As as distinct, etc, then the final final answer is $1092 \times (4!)^3$.

Answer 3

The following is a generating function approach:

We have to produce certain $abc$-strings of length $12$. These strings are beginning with $a$ and contain exactly four $a$s. Such strings are called admissible if they look as follows: $$a\ \square\ a\ \square\ a\ \square a\ \square'\ ,\tag{1}$$ were each $\square$ is a nonempty word of the form $bcbc\ldots$ or $cbc\ldots$, and the $\square'$ may be empty as well. The formal sum of all admissible words in a $\square$ is $$ \square=b+bc+bcb+bcbc+\ldots+c+cb+cbc+cbcb+\ldots ={b+c+2bc\over1-bc}\ ,$$ and the formal sum of all admissible words in $\square'$ is $$\square'=1+{b+c+2bc\over1-bc}={1+b+c+bc\over1-bc}\ .$$ When we replace the squares in $(1)$ by their formal sums and multiply out distributively we obtain many terms, one term with coefficient $1$ for each admissible choice of the four words. The result is $$\left({b+c+2bc\over1-bc}\right)^3{1+b+c+bc\over 1-bc}=(b+c+2bc)^3(1+b+c+bc)\sum_{k\geq0}{k+3\choose 3}(b c)^k\ .\tag{2} $$ We now have to determine the coefficient of $b^4c^4$ on the RHS. From $$(b+c+2bc)^3(1+b+c+bc)$$ we have to collect the terms of the form $(bc)^r$ $\>(0\leq r\leq4)$ and to combine these with corresponding terms of the sum on the RHS of $(2)$. Mathematica has done this for me, and has obtained $364$.

This means that the number you are after is $3\cdot364=1092$, since we have assumed that the first letter is $a$ in our argument.