Learn / Library / Combinatorics

Circular symbol fillings

CombinatoricsHard

A circular log has $10$ slots, where slot $10$ is next to slot $1$ . Each slot gets one of $3$ symbols so that adjacent slots always differ. Fillings that differ only by a rotation count as different. How many fillings are possible?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Compare circular fillings with straight rows whose ends may or may not match.

Solution

Let $c (n)$ be the number of valid circular fillings of $n$ slots; a straight row of $n$ slots with different neighbours can be filled in $3 \times 2^{n - 1}$ ways.
In such a row the last symbol either differs from the first, which is a circular filling counted by $c (n)$ , or equals the first; merging those equal ends gives a circular filling of $n - 1$ slots, counted by $c (n - 1)$ .
So $c (n) = 3 \times 2^{n - 1} - c (n - 1)$ with $c (2) = 6$ .
The values for $n = 3, \dots, 10$ are $6, 18, 30, 66, 126, 258, 510, 1026$ , so $c (10) = 1026$ .

Answer: $1026$

Next question Back to the library