Permutations avoiding 1234, 1432, 2341, 4132

Proof tree for permutations avoiding 1234, 1432, 2341, 4132

Legend

A = Av(0123, 0321, 1230, 3021)

B = Av(012, 0321, 3021)

C = Av(021, 0123, 1230)

D = Av(012, 021)

E = Av(10, 012)

F = Av(01, 10)

╲ = Av(01)

Equations:
${ F_{0}}={ F_{1}}+{ F_{2}}$
${ F_{1}}=1$
${ F_{2}}={ F_{4}}$
${ F_{4}}={ F_{8}}{ F_{9}}$
${ F_{8}}=x$
${ F_{9}}={ F_{12}}+{ F_{23}}$
${ F_{12}}={\frac {-3{x}^{2}+3x-1}{2{x}^{3}-5{x}^{2}+4x-1}}$
${ F_{23}}={ F_{102}}+{ F_{97}}$
${ F_{97}}={\frac {x \left( x-1 \right) ^{2}}{ \left( 2x-1 \right) ^{2}}}$
${ F_{102}}={ F_{104}}$
${ F_{104}}={ F_{231}}{ F_{8}}$
${ F_{231}}={ F_{1874}}+{ F_{445}}$
${ F_{445}}={ F_{161}}+{ F_{2718}}$
${ F_{161}}={ F_{163}}$
${ F_{163}}={ F_{716}}{ F_{722}}{ F_{8}}$
${ F_{716}}=- \left( x-1 \right) ^{-1}$
${ F_{722}}={ F_{10123}}+{ F_{5969}}$
${ F_{5969}}={ F_{23787}}+{ F_{23788}}$
${ F_{23787}}=1/4{\frac {{x}^{4}+2{x}^{3}-2{x}^{2}-x+1}{ \left( x-1/2 \right) ^{2}}}$
${ F_{23788}}={ F_{23790}}$
${ F_{23790}}=-{\frac { \left( {x}^{5}-{x}^{4}-3{x}^{3}+5{x}^{2}-1 \right) x}{ \left( 2x-1 \right) ^{2} \left( x-1 \right) ^{2}}}$
${ F_{10123}}={ F_{10125}}$
${ F_{10125}}=-{\frac { \left( 5{x}^{3}-8{x}^{2}+x+1 \right) x}{ \left( 2x-1 \right) ^{2} \left( x-1 \right) }}$
${ F_{2718}}={ F_{2692}}+{ F_{7507}}$
${ F_{2692}}=-{\frac {{x}^{2} \left( 2x+1 \right) }{x-1}}$
${ F_{7507}}={ F_{7517}}$
${ F_{7517}}={\frac {{x}^{3} \left( 4{x}^{2}-x-2 \right) }{ \left( x-1 \right) ^{2} \left( 2x-1 \right) }}$
${ F_{1874}}={ F_{1875}}$
${ F_{1875}}={ F_{3672}}{ F_{8}}$
${ F_{3672}}={ F_{217}}+{ F_{3721}}$
${ F_{217}}={ F_{1663}}+{ F_{714}}$
${ F_{714}}={\frac {x-1}{2x-1}}$
${ F_{1663}}={ F_{4800}}+{ F_{6799}}$
${ F_{4800}}={ F_{4804}}$
${ F_{4804}}={\frac {{x}^{2} \left( x-2 \right) }{ \left( x-1 \right) ^{2} \left( 2x-1 \right) }}$
${ F_{6799}}=-{\frac {x}{x-1}}$
${ F_{3721}}=-{\frac {x}{x-1}}$

Coefficients:
$1, 1, 2, 6, 20, 59, 150, 354, 801, 1767,\ldots$

Minimal polynomial:
$ \left( 2x-1 \right) ^{2} \left( x-1 \right) ^{3}F \left( x \right) -6{x}^{8}+13{x}^{7}-5{x}^{6}-5{x}^{5}+7{x}^{4}-14{x}^{3}+14{x}^{2}-6x+1$

Generating function:
${\frac {6{x}^{8}-13{x}^{7}+5{x}^{6}+5{x}^{5}-7{x}^{4}+14{x}^{3}-14{x}^{2}+6x-1}{ \left( 2x-1 \right) ^{2} \left( x-1 \right) ^{3}}}$

Recurrence relation:
$-8a \left( n \right) +8a \left( n+1 \right) -2a \left( n+2 \right) -{n}^{2}+n$
$a \left( 0 \right) =1$
$a \left( 1 \right) =1$
$a \left( 2 \right) =2$
$a \left( 3 \right) =6$
$a \left( 4 \right) =20$
$a \left( 5 \right) =59$
$a \left( 6 \right) =150$
$a \left( 7 \right) =354$
$a \left( 8 \right) =801$

Closed form:
$\cases{1&$n=0$\cr 1&$n=1$\cr 2&$n=2$\cr 6&$n=3$\cr 1/16 \left( 4n+21 \right) {2}^{n}-1/2{n}^{2}-3/2n-3&otherwise\cr}$