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

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?