### YouKn0wWho's blog

By YouKn0wWho, 7 weeks ago,

I was experimenting on the following problem for quite a long time:

You are given two integers $n$ and $k(1 \le k\le n \le 10^5)$. You have to find the number of permutations with length $n$ that can be obtained as a suffix array of at least one integer sequence $a_1, a_2, \ldots, a_n$ s.t. $1\le a_i \le k$. Output it modulo $998, 244, 353$.

Definition of Suffix Array for an integer sequence

I didn't have any clue when I came up with the problem. It's really hard to find any specific properties of a permutation which will ensure that there exists a sequence which will generate the permutation as its suffix array.

So then I wrote a brute force over smaller numbers. And it turned out that there exists an OEIS sequence for this problem! And the solution to our problem is $F(n, k) = \sum_{i = 0}^{k}{(-1)^i(k-i)^n {n \choose i}}$

But there is a breathtaking twist! Before I describe it, let's look at the Eulerian numbers. What are they? The Eulerian number $A(n, k)$ is the number of permutations of the numbers from $1$ to $n$ in which exactly $k$ elements are greater than the previous element (permutations with $k$ "ascents").

It turns out that $F(n, k) = \sum_{i = 0}^{k - 1}{A(n, i)}$. That means the solution to our problem is exactly equal to the number of permutations with $<k$ ascents!

The twist here is that when I printed out the permutations in my problem, they are not the permutations with $<k$ ascents! That means there is a bijection between the permutations with $<k$ ascents and the permutations that can be obtained as a suffix array of at least one integer sequence $a_1, a_2, \ldots, a_n$ s.t. $1\le a_i \le k$.

So my two questions are:

• How does the bijection exist?
• Is there any specific property of a permutation which will ensure that there exists a sequence $a_1, a_2, \ldots, a_n$ s.t. $1\le a_i \le k$ which will generate the permutation as its suffix array?

• +132

 » 7 weeks ago, # | ← Rev. 2 →   +63 I read this long time ago, due to the same problem idea. If I remember correctly, you need to look for descents on $p^{-1}(p+1)$, where the addition is taken modulo $n$. Note that the above is a bijection on $S_n$.
 » 7 weeks ago, # |   +275 I couldn't resist checking the blog post after seeing such a catchy title.
•  » » 6 weeks ago, # ^ |   -7 Damn clickbait on CF!
 » 6 weeks ago, # | ← Rev. 2 →   +17 I remember a problem named "Suffix Array" from CTSC 2016. The problem is: given $n$, $m$ and $c_1,c_2 \cdots c_m$, count the number of different suffix arrays which can be generated by strings satisfying that the $i$-th character appears no more than $c_i$ times. $n, c_i \leq 500$It is a very hard problem and I have no idea how to solve it, but the solution claims that the suffix array of string $s$ is $p$ iff the condition below is satisfied:Let $p_{0} = n+1$,if $p_i + 1$ appears after $p_{i+1} + 1$ then $s_{p_i} < s_{p_{i+1}}$if $p_i + 1$ appears before $p_{i+1}+1$ then $s_{p_i} \leq s_{p_{i+1}}$With this claim it is easy to get your conclusionSorry for my poor English, written in a hurry as I have to leave now.