Permutations avoiding 1234, 2341, 4132

Proof tree for permutations avoiding 1234, 2341, 4132

Legend

A = Av(0123, 1230, 3021)

B = Av(012, 3021)

╲ = Av(01)

Equations:
${ F_{0}}={ F_{1}}+{ F_{3}}$
${ F_{1}}=1$
${ F_{3}}={ F_{4}}{ F_{5}}$
${ F_{5}}={ F_{6}}+{ F_{8}}$
${ F_{6}}={ F_{1}}+{ F_{11}}$
${ F_{11}}={ F_{12}}{ F_{4}}$
${ F_{12}}={ F_{14}}+{ F_{15}}$
${ F_{14}}={ F_{1}}+{ F_{34}}$
${ F_{34}}={ F_{14}}{ F_{4}}$
${ F_{4}}=x$
${ F_{15}}={ F_{11}}+{ F_{17}}$
${ F_{17}}={ F_{35}}+{ F_{36}}$
${ F_{35}}={ F_{37}}{ F_{4}}$
${ F_{37}}={ F_{104}}+{ F_{13}}$
${ F_{104}}={ F_{100}}+{ F_{108}}$
${ F_{100}}={ F_{34}}{ F_{4}}$
${ F_{108}}={ F_{102}}+{ F_{103}}$
${ F_{102}}={ F_{104}}{ F_{4}}$
${ F_{103}}={ F_{4}}{ F_{80}}$
${ F_{13}}={ F_{17}}+{ F_{34}}$
${ F_{36}}={ F_{38}}{ F_{4}}$
${ F_{38}}={ F_{11}}+{ F_{80}}$
${ F_{8}}={ F_{10}}+{ F_{11}}$
${ F_{10}}={ F_{18}}+{ F_{19}}$
${ F_{18}}={ F_{20}}{ F_{4}}$
${ F_{20}}={ F_{23}}+{ F_{24}}$
${ F_{23}}={ F_{11}}+{ F_{29}}$
${ F_{29}}={ F_{45}}+{ F_{46}}$
${ F_{46}}={ F_{4}}{ F_{48}}$
${ F_{48}}={ F_{50}}+{ F_{51}}$
${ F_{50}}={ F_{115}}+{ F_{34}}$
${ F_{115}}={ F_{116}}{ F_{4}}$
${ F_{116}}={ F_{115}}+{ F_{34}}$
${ F_{51}}={ F_{55}}+{ F_{95}}$
${ F_{55}}={ F_{117}}+{ F_{118}}$
${ F_{118}}={ F_{115}}{ F_{4}}$
${ F_{117}}={ F_{119}}{ F_{4}}$
${ F_{119}}={ F_{100}}+{ F_{121}}$
${ F_{121}}={ F_{117}}+{ F_{147}}$
${ F_{147}}={ F_{115}}{ F_{4}}$
${ F_{45}}={ F_{4}}{ F_{47}}$
${ F_{47}}={ F_{34}}+{ F_{95}}$
${ F_{95}}={ F_{112}}+{ F_{45}}$
${ F_{112}}={ F_{113}}{ F_{4}}$
${ F_{113}}={ F_{115}}+{ F_{34}}$
${ F_{24}}={ F_{10}}+{ F_{30}}$
${ F_{30}}={ F_{56}}+{ F_{57}}+{ F_{58}}$
${ F_{58}}={ F_{4}}{ F_{68}}$
${ F_{68}}={ F_{67}}+{ F_{80}}$
${ F_{67}}={ F_{123}}+{ F_{89}}$
${ F_{123}}={ F_{4}}{ F_{80}}$
${ F_{56}}={ F_{4}}{ F_{59}}$
${ F_{59}}={ F_{132}}+{ F_{22}}$
${ F_{22}}={ F_{29}}+{ F_{30}}$
${ F_{132}}={ F_{126}}+{ F_{136}}$
${ F_{136}}={ F_{129}}+{ F_{130}}$
${ F_{129}}={ F_{132}}{ F_{4}}$
${ F_{130}}={ F_{4}}{ F_{67}}$
${ F_{126}}={ F_{4}}{ F_{95}}$
${ F_{57}}={ F_{4}}{ F_{60}}$
${ F_{60}}={ F_{32}}+{ F_{67}}$
${ F_{19}}={ F_{21}}{ F_{4}}$
${ F_{21}}={ F_{27}}+{ F_{28}}$
${ F_{27}}={ F_{11}}+{ F_{32}}$
${ F_{32}}={ F_{36}}+{ F_{70}}$
${ F_{70}}={ F_{4}}{ F_{73}}$
${ F_{73}}={ F_{76}}+{ F_{77}}$
${ F_{77}}={ F_{79}}+{ F_{95}}$
${ F_{79}}={ F_{123}}+{ F_{140}}+{ F_{57}}$
${ F_{140}}={ F_{141}}{ F_{4}}$
${ F_{141}}={ F_{153}}+{ F_{77}}$
${ F_{153}}={ F_{126}}+{ F_{156}}$
${ F_{156}}={ F_{130}}+{ F_{151}}$
${ F_{151}}={ F_{153}}{ F_{4}}$
${ F_{76}}={ F_{32}}+{ F_{34}}$
${ F_{28}}={ F_{33}}+{ F_{80}}$
${ F_{33}}={ F_{89}}+{ F_{90}}$
${ F_{90}}={ F_{4}}{ F_{80}}$
${ F_{89}}={ F_{4}}{ F_{93}}$
${ F_{93}}={ F_{67}}+{ F_{95}}$
${ F_{80}}={ F_{4}}{ F_{83}}$
${ F_{83}}={ F_{34}}+{ F_{80}}$

Coefficients:
$1, 1, 2, 6, 21, 72, 221, 605, 1517, 3574,\ldots$

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

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

Recurrence relation:
$24a \left( n \right) -24a \left( n+1 \right) +6a \left( n+2 \right) +7{n}^{3}-45{n}^{2}+26n+66$
$a \left( 0 \right) =1$
$a \left( 1 \right) =1$
$a \left( 2 \right) =2$
$a \left( 3 \right) =6$
$a \left( 4 \right) =21$
$a \left( 5 \right) =72$
$a \left( 6 \right) =221$
$a \left( 7 \right) =605$
$a \left( 8 \right) =1517$

Closed form:
$\cases{1&$n=0$\cr 1&$n=1$\cr 2&$n=2$\cr -11+3/8{2}^{n}n+{\frac {21{2}^{n}}{4}}+1/2{n}^{2}-7/3n-7/6{n}^{3}&otherwise\cr}$