Counting Permutations Avoiding Increasing Subsequences Proportional to their length

Counting Permutations Avoiding Increasing Subsequences Proportional to their length
By Manuel Kauers and Doron Zeilberger
.pdf .tex [Yet to be written]

Written: Jan. 2026

The number of permutations of length n avoiding an increasing sequence of length 3 is famously the n-th Catalan number. It is well-known that for any fixed r, the number of permutations of length n avoiding an increasing subsequence of length r is D-finite, i.e. satisfies some linear recurrence equation with polynomial coefficients. But what if you forbid really long increasing subsequences, half, one-third, etc, of the permutation length? In other words if r is some fraction of n (and variations on the theme)?

Maple packages

AvoidP.txt, To generate data

Sample Input and Output for AvoidP.txt

If you want to see conjectured linear recurrences, the first 40 terms, and the 1000-th term for sequences enumerating permutations of length 2n+a1 containing an increasing sequence of length n+a2 for the following 13 cases of [a1,a2],
{ [-2, -1], [-2, 0], [-1, 0], [-1, 1], [-1, 2], [0, 1], [0, 2], [0, 3], [1, 0], [1, 1], [1, 2], [2, 1], [2, 2]}
the input file gives the output

If you want to see the first 40 terms of the sequences enumerating permutations of {1, ..., 2n} avoiding subsequences of length n+m for m from 0 to 4
the input file gives the output

If you want to see the first 80 terms of the Shaiy Pilpel OEIS sequence A6220 (the OEIS only has 13 terms, so far)
the input file gives the output

If you want to see the first 107 terms of the Shaiy Pilpel OEIS sequence A6220 (the OEIS only has 13 terms, so far), done by Manuel Kauers' computer see heret

If you want to see the first 70 terms of the sequences
Sum(YF(p)*YF(p+[i1,i2]), p in Par(n))
where Par(n) is the set of (integer) partitions of n, and YF(p) is the number of Standard Young Tableaux of shape p (using the Young-Frobenius Formula)
For [i1,i2]={[0,0],[1,0],[2,0],[2,1],[2,2]}
(note that the case [i1,i2]=0 gives n! thanks to Robinson-Schenstead)
the input file gives the output
[For a nice version where the sequence corresponding to [i1,i2] is called Li1i2, see: here

Manuel Kauers' Home Page
Doron Zeilberger's Home Page