Constrained Permutations

Let $(p_1 p_2 \ldots p_k)$ denote the permutation of the set ${1, …, k}$ that maps $p_i\mapsto i$. Define the length of the permutation to be $k$; note that the empty permutation $()$ has length zero.
Define an occurrence of a permutation $p=(p_1 p_2 \cdots p_k)$ in a permutation $P=(P_1 P_2 \cdots P_n)$ to be a sequence $1\leq t_1 \lt t_2 \lt \cdots \lt t_k \leq n$ such that $p_i \lt p_j$ if and only if $P_{t_i} \lt P_{t_j}$ for all $i,j \in \{1, \dots, k\}$.
For example, $(1243)$ occurs twice in the permutation $(314625)$: once as the 1st, 3rd, 4th and 6th elements $(3\,\,46\,\,5)$, and once as the 2nd, 3rd, 4th and 6th elements $(\,\,146\,\,5)$.
Let $f(n, m)$ be the number of permutations $P$ of length at most $n$ such that there is no occurrence of the permutation $1243$ in $P$ and there are at most $m$ occurrences of the permutation $21$ in $P$.
For example, $f(2,0) = 3$, with the permutations $()$, $(1)$, $(1,2)$ but not $(2,1)$.
You are also given that $f(4, 5) = 32$ and $f(10, 25) = 294\,400$.
Find $f(10^{18}, 40)$ modulo $1\,000\,000\,007$.

This is a problem in enumerative combinatorics that can be solved with the use of dynamic programming.

This problem is set up perfectly for dynamic programming. We construct an $n \times m \times p$, $3$D dp-table `dp[][][]` where an entry `dp[i][j][k]` represents the number of permutations for an array of length `i` such that no occurrence of permutation `1243` and not more than `j` occurrences of permutation `21` and with maximum element being `k`.

For the base case `dp[i][j][0]` is always $1$ for all `i` and `j`, because there is only the empty permutation.

For the non-base cases, we sum up the number of ways based on where the maximum appears in the list:
1. For each `l` from `k` to `i-1`, we increase the number of occurrences of `21` by `1`, decrement the length of array from `i` to `i-1` and maximum remains `k` which results in:
> `dp[i][j][k] = (dp[i][j][k] + dp[i – 1][j – (l < k ? 1 : 0)][k - 1]) mod MODULO` 2. For `l == i`: > `dp[i][j][k] = (dp[i][j][k] + dp[i – 1][j][k – 1]) mod MODULO`

Maintain a cumulative sum for each `i`, `j` to calculate the result of dp-table.

Finally, the answer for `f(n, m)` is the summation `dp[n][m][i]` for all possible `i`.

For the case, `f(10^18, 40)` modulo $1,000,000,007$, it is not feasible to directly compute due to the astronomical size of the inputs. You would need to take into account the computational constraints and come up with a more optimized solution or algorithm, possibly involving number-theoretic concepts such as modular arithmetic or combinatorial identities to compute smaller, more manageable quantities.

Lastly, for some competitive programming problems such as this one, there might not be a straight forward way to solve it, only an efficient algorithm and technique that would get you closer to the result under given constraints.

More Answers: