This problem was inspired from https://codeforces.com/contest/1861/problem/E.
Given two integers $2 \le k \le n$, we call the sequence $(a_1, a_2,\dots, a_n) ~ k-$good if it satisfies the following conditions:
- $a_i \in \lbrace 1, 2,\dots,k \rbrace$ for all $1 \le i \le n$.
- $(a_1,a_2,\dots,a_k)$ is a permutation of $(1,2,\dots,k)$.
- For any $2 \le m \le n-k+1$, $(a_m, a_{m+1},\dots,a_{m+k-1})$ is NOT a permutation of $(1,2,\dots,k)$.
For example when $k=4,n=6$, the sequence $(3,1,2,4,4,3)$ is a $4-$good sequence, whereas $(3,1,2,4,3,2)$ isn't.
Let $f(k,n)$ be the number of $k-$good sequences with $n$ elements. Is there either a closed-form expression or a recurrence relation for $f(k,n)$? If not, then are there any efficient ways to calculate $f(k,n)$?
We can begin to attack the problem as follows.
Given a $k$-good sequence $(a_1,a_2,\dots,a_n)$ with $n$ elements, for at most one value of $a_{n+1}$, we have that $(a_1,a_2,\dots,a_{n+1})$ is not a good sequence. It follows $$(k-1)f(k,n)\le f(k,n+1)\le kf(k,n).$$ Moreover, if $k=2$ then there is exactly one choice of such $a_{n+1}$, so $f(k,n+1)=f(k,n)$. Thus $f(2,n)=2$ for each natural $n\ge 2$.
Let $k=3$. Let $f_1(3,n)$ be the number of $3$-good sequences $(a_1,a_2,\dots,a_n)$ with $a_{n-1}=a_n$ and $f_2(3,n)$ be the number of $3$-good sequences $(a_1,a_2,\dots,a_n)$ with $a_{n-1}\ne a_n$. It is easy to see that $f(k,n)=f_1(k,n)+f_2(k,n)$, $f_1(k,k)=0$, $f_2(k,k)=1$, $f_1(3,n+1)=f_1(3,n)+f_2(3,n)$, and $f_2(3,n+1)=2f_1(3,n)+f_2(3,n)$. Thus $$\begin{pmatrix} f_1(3,n) \\ f_2(3,n) \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 2 & 1 \end{pmatrix}^{n-k} \begin{pmatrix} 0 \\ 1\end{pmatrix}.$$
It seems that this approach can be generalized for any $k$ as follows. Let $\mathcal P_k$ be the family of all partitions of $\{1,2,\dots,k-1\}$ into nonempty subsets. For any partition $P\in\mathcal P_k$ let $f_P(k,n)$ be the number of $k$-good sequences $(a_1,a_2,\dots,a_n)$ such that for each $i,j\in \{1,2,\dots,k\}$ we have $a_{n+1-i}=a_{n+1-j}$ iff $i$ and $j$ belong to the same member of the partition $P$ and then providing the recurrence $$(f_P(k,n+1))^t_{P\in\mathcal P_k}=A(f_P(k,n))^t_{P\in\mathcal P_k}$$ for some matrix $A$.