Counting Number of Distributions (Constraint: No adjacent objects are identical)

combinatoricspermutations

The question from the book is

Five persons A,B,C,D,E are seated in a circular arrangement. If each of them is given a hat of one of the three colors- red, blue, and green; then the number of ways of distributing hats such that the persons seated in adjacent seats get different colored hats is ___.

So, I tried using the multiplication theorem to get to an answer,

Assuming ABCDE are seated along a line in the given order,

A can get any of the three colors,
following which B gets one of the two remaining colors, following C gets one of the two colors other than the one that B gets, and so on.

So, the number of distributions would be

$$ \text{No. of distributions for a line} = 3 \times 2 \times 2 \times 2 \times 2 = 48 $$

Now this includes distributions in which A and E have the same colored hats,

If A and E have the same colors, then there are 6 possible distributions which satisfy the conditions, 2 for each color that A gets.

Using the inclusion-exclusion principle,
$$ \text{No. of distributions for a circle} = 48 – 6 = 42 $$

But the answer is supposed to be 30.

I'm not sure where I am wrong, so if someone could figure it out and help me solve this question, I'd be really grateful.

This is my first time on this forum so excuse me if my question is not very clear. Thanks!

Best Answer

The easiest is to notice that if five people sit in a circle, you cannot ensure adjacent persons not wearing hats of the same color with hats of two colors (and of course one). So you need hats of all three colors with no color having $3$ hats or more.

But coming back to your work and mistake in your counting -

Yes if they were standing in a line, there would be $48$ ways to distribute hats of three colors with adjacent persons not wearing hats of the same color.

Now as they are in a circle, we subtract those distributions where the first and the first persons are wearing hats of the same color. Take an example with both of them wearing red hats - R 2 3 4 R

The possible distributions for positions $2, 3, 4$ are -
B G B, B R B, G B G, G R G, B R G, G R B

That is $6$ distributions where first and fifth persons are wearing $R$ colored hats. So considering they could be wearing $B$ or $G$ too, the number of distributions that we need to subtract from $48$ is $3 \cdot 6 = 18$. That leads to $30$ distributions.

Related Question