0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Steve Kass May 17 '18 at 12:00
  • $\begingroup$ See the "smords" exercise in my UMN Fall 2017 Math 4990 Homework set 3. $\endgroup$ – darij grinberg May 17 '18 at 13:43
1
$\begingroup$

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).

This leads to

$$ 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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.