Way where $K$ elements (numbered $1$ to $K$) can be aligned in $N$ places where only one element is allowed to repeat? I was asked this question while I was giving an interview for a software engineer role but simply couldn't find the correct answer. I am pretty sure this can be solved using permutation and combination but still always arrived at the wrong answer. Any help would be appreciated.

What are the number of ways in which, $K$ elements which are numbered from $1$ to $K$ like $1,2,....,K$ can be aligned in $N$ places such that no $2$ same number are adjacent except the one specified as variable $X$ ?


For the context of the question, please consider the following example:
$$N = 3 K = 2 X = 1$$
Explanation: Arrange $K = 2$ so $1,2$ in $3$ places such that $2$ cannot be placed next to each other but $1$ can like $1,1$ but not $2,2$.
Possible ways: $\{1,1,1\} , \{1,1,2\} , \{1,2,1\} , \{2,1,1\} , \{2,1,2\}$.
Another example can be:
$$N = 5 K = 4 X = 3$$ And there are $469$ possible ways in total.

So, how do I generate a common formula for greater numbers?
 A: To solve this question, we start by building two sequences, $a_n,b_n$ such that $a_n$ is the number of allowed sequences of length $n$ and $b_n$ is the number of allowed sequences of length $n$ assuming that you can't start with one of the regular numbers (i.e. can't start with some specific number that's not $X$).
We are therefore interested in a formula for $a_n$.
Then $a_n = a_{n-1} + (k-1)b_{n-1}$ as we can either choose $X$ as the first number (and then there are $a_{n-1}$ options to continue the sequence) or one of the other $k-1$ options (and then there are $b_{n-1}$ options to continue the sequence for each of the choices).
Quite similarly, we get $b_n = a_{n-1}+(k-2)b_{n-1}$ as we can either choose $X$ or any of the other $k-2$ elements to start the sequence.
We can therefore obtain a matrix equality given by
$$\left[ \array{1\ k-1\newline1\ k-2} \right]\cdot\left[ \array{a_{n-1}\newline b_{n-1}} \right]=\left[ \array{a_{n}\newline b_{n}} \right]$$
After finding $a_1=k,b_1=k-1$, we could calculate the $n$'th element of $a$ by diagonalising the matrix above (it has 2 eigenvalues for every real, positive value of $k$, thus is diagonalisable for such values), and, denoting by $P$ the change of basis matrix and $D$ the diagonal matrix, taking this form to the $n$'th power, then calculating $PD^{n-1}P^{-1}\left[ \array{a_{1}\newline b_{1}} \right]$, or if you rather, since $\left[ \array{1\ k-1\newline1\ k-2} \right]\left[ \array{1\newline 1} \right]=\left[ \array{a_{1}\newline b_{1}} \right]$, one could calculate $$PD^{n}P^{-1}\left[ \array{1\newline 1} \right]$$ and return the first coordinate.
There might be an easier way to do this, but unfortunately I couldn't find one :)
