← Complete problem index

PROJECT EULER · #0631

Constrained Permutations

Statement only · UnsolvedOriginal problem ↗

Let (p1p2…pk) denote the permutation of the set 1,...,k that maps pi↦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=(p1p2⋯pk) in a permutation P=(P1P2⋯Pn) to be a sequence 1≤t1<t2<⋯<tk≤n such that pi<pj if and only if Pti<Ptj for all i,j∈{1,…,k}.

For example, (1243) occurs twice in the permutation (314625): once as the 1st, 3rd, 4th and 6th elements (3465), and once as the 2nd, 3rd, 4th and 6th elements (1465).

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)=294400.

Find f(1018,40) modulo 1000000007.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.