# Count circular sequences with different adjacent elements

We have given $n$ and $k$ we want to count all sequences of length $n$, each element in the range $[1, k]$ such that no two adjacent elements are equal, plus the first and the last elements should be different, in other words the sequence is circle.

For example $n=4, k=2$, there are two possible orderings: $\{1,2,1,2\}$, $\{2,1,2,1\}$.

My try: Let's say $f(x)$ is the number of such sequences of length $x$ with fixed $k$.

We can see that $f(x) = k \cdot (k-1)^{x-1}$, but on this way there might be cases where the first and the last elements are equal, so we should subtract those cases from $f(x)$, now I cannot come up with formula how many such sequences exist.

• If the first and last elements must be equal, there will be only $1$ choice, as opposed to $n-1$ choices (mistyped as $x-1$ in your formula), for the last element. – Steve Kass May 17 '18 at 12:00
• See the "smords" exercise in my UMN Fall 2017 Math 4990 Homework set 3. – darij grinberg May 17 '18 at 13:43

Let $l$ be the first element of a sequence. Let's denote by $a_n$ the number of such sequences that also end with $l$, while $b_n$ shall be the number of such sequences that do not end in $l$. (I'm only ever talking about sequences that fullfill the 'no adjacent elements are equal' rule). We get

$$f(n) = k \times b_n$$

as there are $k$ possible values for $l$ and the sequences counted by $a_n$ are exactly those that have the same first and last element, which we don't want. Also, it is easily seen that $a_1=1$ and $b_1=0$.

Further, we have for $n \ge 1$ $$a_{n+1}=b_n,$$ as there is a 1-1 correspondence between a sequence ending in $l$ of length $n+1$ and a sequence not ending in $l$ of length $n$: Just remove the last element of the former.

If we remove the last element of a sequence of length $n+1$ not ending in $l$, there are two possibilites: The (new) last element can be $l$ or something else.

Any given sequence of length $n$ ending in $l$ will be obtained this way in exactly $k-1$ ways (any of the $k-1$ non-$l$ values could have been removed).

Any given sequence of length $n$ not ending in $l$ will be obtained this way in exactly $k-2$ ways (the last element of the $n+1$-length sequence could have been anything except $l$ and the last element of the $n$-length series).

$$b_{n+1} = (k-1)a_n + (k-2)b_n$$

Using the above, we get $$b_1=0, b_2=k-1,$$ $$b_{n+2} = (k-2)b_{n+1} + (k-1)b_n$$.

This is a recurrence relation with constant coefficients, the usual methods lead to the following formula:

$$b_n = \frac{k-1}k\left((k-1)^{n-1} - (-1)^{n-1}\right)$$

(if you don't know about those methods, you can just prove the formula using mathematical induction).

To get the final answer, we multiplay with $k$ and get

$$f(n) = (k-1)\left((k-1)^{n-1} - (-1)^{n-1}\right) = (k-1)^n +(k-1)(-1)^n$$