1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ What is the source of this problem? $\endgroup$
    – lulu
    Sep 1, 2023 at 13:42
  • $\begingroup$ @lulu I was "inspired" by yesterday's Codeforces contest. See codeforces.com/contest/1861/problem/E $\endgroup$
    – NVA
    Sep 1, 2023 at 13:45
  • 2
    $\begingroup$ It's against site policy to post live contest questions here, though I would agree that your problem is quite far removed from the contest problem (in particular, the contest blocks overlaps where you do not). I suggest editing your post to include the motivating problem though...on its face, the problem sure looks more like a programming challenge than a likely recursion candidate. $\endgroup$
    – lulu
    Sep 1, 2023 at 13:49
  • $\begingroup$ Also, what have you tried? It seems hard since, while $a_{k+1}$ is obviously forced to be a duplicate, it makes a big difference which duplicate it is. If $a_{k+1}=a_k$ then that blocks a whole lot of subsequences from being permutations, whereas if $a_{k+1}=a_1$, then it doesn't. $\endgroup$
    – lulu
    Sep 1, 2023 at 13:51
  • 1
    $\begingroup$ Oh, if the contest is over then there is no problem at all. As I mentioned, in this case I don't think your problem is close enough to the contest problem to cause an issue. The contest problem does sound recursive, since you can always start computing the cost after the first permutation is observed. Yours seems harder to me (with the usual proviso that I might be missing something). $\endgroup$
    – lulu
    Sep 1, 2023 at 14:12

1 Answer 1

1
+50
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .