A111053 Number of permutations which avoid the patterns 1324 and (2143 with Bruhat restriction {2<->3}). Also the number of permutations whose graphs are acyclic.

1, 2, 6, 22, 89, 379, 1661, 7405, 33367, 151398, 690147, 3156112, 14465746, 66409493, 305232025, 1404129530, 6463476538, 29767212095, 137142651679, 632021380433, 2913316615372, 13431328632593, 61931182541194, 285592218851606, 1317104663887309, 6074682489939359, 28018852961838675, 129239701278757210

Offset: 1

Author

Steve Butler, Oct 06 2005

Keywords

• nonn

Examples

			x + 2*x^2 + 6*x^3 + 22*x^4 + 89*x^5 + 379*x^6 + 1661*x^7 + 7405*x^8 + ...
		

References

• S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. See p. 399, Table A.7.

Links

• H. Abe and S. Billey, Consequences of the Lakshmibai-Sandhya theorem: the ubiquity of permutation patterns in Schubert calculus and related geometry, 2014.
• M. Bousquet-Mélou and S. Butler, Forest-like permutations, arXiv:math/0603617 [math.CO], 2006.
• S. Butler, On permutations which are 1324 and {overline 2143} avoiding, 2005.
• S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).
• Haruhisa Enomoto, Bruhat inversions in Weyl groups and torsion-free classes over preprojective algebras, arXiv:2002.09205 [math.RT], 2020.

Crossrefs

Cf. A204200.

Programs

Mathematica

a = DifferenceRoot[Function[{a, n}, {(4n^2 + 46n + 60)a[n] + (-9n^2 - 105n - 156)a[n+1] + (22n^2 + 256n + 372)a[n+2] + (-9n^2 - 111n - 240)a[n+3] + (n+4)(n+9)a[n+4] == 0, a[1] == 1, a[2] == 2, a[3] == 6, a[4] == 22}]];
Array[a, 28] (* Jean-François Alcover, Dec 17 2018 *)

PARI

x='x+O('x^66);
gf=((1-x)*(1-4*x-2*x^2)-(1-5*x)*sqrt(1-4*x))/(2*(1-5*x+2*x^2-x^3));
Vec(gf) /* Joerg Arndt, Jun 25 2011 */

PARI

{a(n) = if( n<0, 0, polcoeff( 2 * x * (1 - 4*x - x^2) / ((1 - x) * (1 - 4*x - 2*x^2) + (1 - 5*x) * sqrt(1 - 4*x + x * O(x^n))), n))} /* Michael Somos, Jan 12 2012 */

Formula

G.f.: ((1-x)*(1-4*x-2*x^2)-(1-5*x)*sqrt(1-4*x))/(2*(1-5*x+2*x^2-x^3)). - Ralf Stephan, May 09 2007

G.f.: 2 * x * (1 - 4*x - x^2) / ((1 - x) * (1 - 4*x - 2*x^2) + (1 - 5*x) * sqrt(1 - 4*x)). - Michael Somos, Jan 12 2012

G.f. is the power series composition of g.f. A204200 and g.f. A000108 (Catalan) with offset 1. - Michael Somos, Jan 12 2012

Conjecture: n*(n+5)*a(n) +3*(20-13*n-3*n^2)*a(n-1) +2*(11*n^2+40*n-150)*a(n-2) +3*(40-11*n-3*n^2)*a(n-3) +2*(n+6)*(2*n-5)*a(n-4)=0. - R. J. Mathar, Aug 14 2012

Extensions

More terms from Joerg Arndt, Jun 25 2011