Problem 631

Problem 631

Constrained Permutations

Let $(p_1p_2\ldots p_k)$ denote the permutation of the set ${1,\ldots,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_1p_2\ldots p_k)$ in a permutation $P=(P_1P_2\ldots P_n)$ to be a sequence $1\le t_1<t_2<\cdots <t_k\le n$ such that $p_i<p_j$ if and only if $P_{t_i}<P_{t_j}$ for all $i,j\in{1,\ldots,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$.


用$(p_1p_2\ldots p_k)$表示将集合 ${1,\ldots,k}$ 按照$p_i\mapsto i$映射的排列。记这样的排列的长度为$k$;注意空排列$()$的长度视为0。

考虑排列$P=(P_1P_2\ldots P_n)$和较短的排列$p=(p_1p_2\ldots p_k)$,如果存在序列$1\le t_1<t_2<\cdots <t_k\le n$ ,使得对任意$i,j\in{1,\ldots,k}$,$p_i<p_j$ 当且仅当$P_{t_i}<P_{t_j}$,则称$p$在$P$中出现了一次。

例如,排列$(1243)$在排列$(314625)$中出现了两次:第一次由第1、3、4、6个元素组成,即 $(3\ 46\ 5)$;第二次由第2、3、4、6个元素组成,即$(\ 146\ 5)$。



已知$f(4,5)=32$,以及$f(10,25)=294\ 400$。

求$f(10^{18},40)$并对$1\ 000\ 000\ 007$取余。