Counting the number of permutations b of an array a such that: $$$S = \sum_{j=2}^{n} (\max(a[b_j], a[b_{j-1}]) - 1)$$$ equals a given value X.
Know :
$$$n \le 50$$$
$$$a_i \le n$$$
Example: Computing S for a given permutation
Let
and define
Example 1
Take the permutation
[ b = [2, 4, 1, 3, 5] ]
Then
| j | $$$Pair(a[b_{j-1}], a[b_j])$$$ | max | max−1 | Cumulative (S) |
|---|---|---|---|---|
| 2 | (5, 2) | 5 | 4 | 4 |
| 3 | (2, 3) | 3 | 2 | 6 |
| 4 | (3, 6) | 6 | 5 | 11 |
| 5 | (6, 10) | 10 | 9 | 20 |
Result:
