In how many ways can we split 8 animals into four groups with these requirements...

Question

So we have $2$ cats, $2$ dogs, $2$ lions, $2$ tigers, and we want to split them into $4$ groups such that each group has $2$ none similar animals.
In how many ways we can do that?

I'm trying to use the inclusion exclusion principle, since I tried to approach it normally and got stuck, and here's what I reached:
numbers of ways with $1$ group with $2$ similar animals : $8 \choose 2$$\frac {6!}{2!2!2!}$ .
number of ways with $2$ groups with $2$ similar animals: $8 \choose 4$$\frac{4!}{2!2!}$.
number of ways with $3$ groups with $2$ similar animals: $8 \choose 6$.
number of ways with $4$ groups with $2$ similar animals: $8 \choose 8$.
So my answer will be $\frac {8!}{2!^4}$ - $4 \choose 1$$8 \choose 2$$\frac {6!}{2!2!2!}$ + $4 \choose 2$$8 \choose 4$$\frac{4!}{2!2!}$ - $4 \choose 3$$8 \choose 6$ +$1$.
$=5040 - 10080 + 2520 - ...= (-)$.
So basically I got it all wrong since I got a minus in the end, would be happy to see where are my mistakes and how to solve this. Thanks in advance.

Answer 1

There are essentially two different patterns: either you have two species in two groups (forcing the choice for the other two groups) or you do not (in which case each group is distinct and with four groups you must have a cycle):

(a) AB AB CD CD

(b) AB BC CD DA

But the next issue is what counts as a different split.

If the species are distinguishable, but the groups and individual animals are not then (a) has $3$ possibilities (the cats can be with one other species) and (b) has $3$ possibilities (the cats can not be with one other species), making $6$ in total

If the species and individual animals are distinguishable, but the groups are not then (a) has $3\times 2^2$ possibilities (since you can only split a pair of species two ways, but have two sets of pairs) and (b) has $3\times 2^4$ possibilities (since going round the cycle you get two choices for each species), making $60$ in total

Answer 2

For applying P.I.E, the correct way should have been

$\displaystyle 4! - {4 \choose 1} 3! + {4 \choose 2} 2! - {4 \choose 3} 1! + {4 \choose 4} 0! = 9$

which is nothing but the derangement of $4$ i.e. $!4$.

But here is the problem. It is not a straightforward application of derangement either. That is because you are pairing animals that are of same kind (cat, dog, lion and tiger with cat, dog, lion and tiger).

Consider for example, a group $\{C \ D, D \ L, L \ T, T \ C\}$ is no different than $ \{C \ T, D \ C, L \ D, T \ L \}$. The derangement will count them as two different. The number of such repetitions should be ${3 \choose 2} = 3$ which is choosing two animals out of remaining $3$ to pair with a given animal. Once we fix two pairs, other two are automatically fixed. Here are the other two that repeat -

$\{C \ D, D \ T, L \ C, T \ L\}$ and $ \{C \ L, D \ C, L \ T, T \ D \}$

$\{C \ L, D \ T, L \ D, T \ C\}$ and $ \{C \ T, D \ L, L \ C, T \ D \}$

So the right answer is $ = !4 - 3 = 6$.

By the way, writing all permissible arrangements is a very viable option here.

Answer 3

First, read WW1's comment on the question. I agree that his interpretation of the question is most likely what is intended.

Now, since no two animals of the same type in are to be in the same group, by the pigeon hole principle, there must be a group with a cat, a second group, with a dog, yet a third group with a tiger, and a fourth group with a lion. This is what I meant by my first sentence.

We concentrate on the remaining $4$ animals. We can arrange them in $4!=24$ ways, put the first animal in the first group, the second animal in the second groups, and so on. Not all these permutations are admissible. Any of the $3!=6$ permutations in which the cat comes first is invalid, because we will end up with two cats in the first group. Similarly, we must subtract the $6$ permutations where the dog comes second, and so on. Since we have to do this for each of the animals, we are left with $24-\cdot6=0$ permutations.

Wait, though; we've done some double counting. If the cat comes first and the dog second in the permutation, then we subtracted it twice. We have to add these back in. There are $\binom42=6$ ways to choose the two animals, and $2$ ways to permute the other $2$ animals, so we have to add $12$.

We're not done yet. Suppose $3$ of the animals match the animal already in the group. Then of course, so does the fourth, and there's only one such permutation. How many times have we counted it? We counted it once to begin with, subtracted it $4$ times (once for each animal), and added it back $6$ times (once for each pair of animals). In all, we counted it $1-4+6=3$ times. And of course, we don't want to count it all all, so we subtract $3$, giving a final answer of $9$.

This is equal to the number of derangements of $4$ objects, where a derangement is a a permutation that leaves no element fixed. That is $\sigma(x)\neq x$ for every $x$ in the set. I hope the relation of derangements to this problem is clearer now.