A permutation of length $n$ is consisted of only numbers $\in \{1,2,3 \cdots n\}$ and some $k$, $k \leq n$ initial values of that permutation are given. Found out the number of ways such that the inversion count of the permutation of length $n$ has value equal to $\sum_{i = 1}^{n} max(0, i - perm[i])$, perm[i] meaning the element at index $i$. Example : $n = 5, k = 2 $
initial value of permutation $2 \>1$
Now six permutations are possible for above sequence
$2 \>1 \>3 \> 4 \>5$
Inversion count = $1$ ,
Sum = $max(0, 1 - 2) + max(0, 2 - 1) + max(0, 3 - 3) + max(0, 4 - 4) + max(0, 5 - 5) = 0 + 1 + 0 + 0 + 0 = 1$
So here Inversion count is equal to sum.
$2 \>1 \>4 \> 3 \>5$ Inversion count = $2$ ,
Sum = $max(0, 1 - 2) + max(0, 2 - 1) + max(0, 3 - 4) + max(0, 4 - 3) + max(0, 5 - 5) = 0 + 1 + 0 + 1 + 0 = 2$
So here Inversion count is equal to sum.
$2 \>1 \>4 \> 5 \>3$ Inversion count = $3$ ,
Sum = $max(0, 1 - 2) + max(0, 2 - 1) + max(0, 3 - 4) + max(0, 4 - 5) + max(0, 5 - 3) = 0 + 1 + 0 + 0 + 2 = 2$
So here Inversion count is not equal to sum.
$2 \>1 \>3 \> 5 \>4$ Inversion count = $2$ ,
Sum = $max(0, 1 - 2) + max(0, 2 - 1) + max(0, 3 - 3) + max(0, 4 - 5) + max(0, 5 - 4) = 0 + 1 + 0 + 1 + 0 = 2$
So here Inversion count is equal to sum.
$2 \>1 \>5 \> 3 \>4$ Inversion count = $3$ ,
Sum = $max(0, 1 - 2) + max(0, 2 - 1) + max(0, 3 - 5) + max(0, 4 - 3) + max(0, 5 - 4) = 0 + 1 + 0 + 1 + 1 = 3$
So here Inversion count is equal to sum.
$2 \>1 \>5 \> 4 \>3$ Inversion count = $4$ ,
Sum = $max(0, 1 - 2) + max(0, 2 - 1) + max(0, 3 - 5) + max(0, 4 - 4) + max(0, 5 - 3) = 0 + 1 + 0 + 0 + 2 = 3$
So here Inversion count is not to sum.
So there are three sequences of size $5$ with above given initial $2$ value which satisfy the above condition.
I know permutation can be count using modified merge sort but since $1 \leq n, k \leq 30$ So it will be very hard to generate all permutations.
Please help how to proceed
Knuth [1] defined the total displacement of a permutation $\sigma$ of $\{1,\ldots,n\}$ to be $\mathrm{td}(\sigma) = \sum_{j=1}^{n} |\sigma(j)-j|$. Subsequently, Diaconis and Graham [2] proved that total displacement and number of inversions are related by the following double inequality: $\mathrm{inv} \leqslant \mathrm{td}(\sigma) \leqslant 2\,\mathrm{inv}(\sigma)$ for any permutation $\sigma$.
The permutations for which we have the equality $\mathrm{td}(\sigma) = 2\,\mathrm{inv}(\sigma)$ are the $321$-avoiding permutations, that is, those not containing a decreasing subsequence of three terms.
You are interested in a subset of these, that also avoid the patterns $231$ and $312$. These are precisely the direct sums of $1$ and $21$ and are counted by the Fibonnaci numbers. (See [3] for a basic introduction to pattern avoidance in permutations.)
[1] Donald E. Knuth. The art of Computer Programming. Vol. 3: Sorting and Searching. Addison-Wesley, 1973.
[2] Persi Diaconis and R. L. Graham. Spearman’s footrule as a measure of disarray. J. Royal Statist. Soc. Ser. B, 39:262–268, 1977.
[3] https://arxiv.org/pdf/1506.06673