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,2

References

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

Links

Table of n, a(n) for n=1..28.

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.

Formula

G.f.: ((1-X)*(1-4*X-2*X*X)-(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

Example

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

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 *)

Prog

(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 */

Crossrefs

Cf. A204200.

Sequence in context: A271388 A165540 A363809 * A165541 A165542 A165543

Adjacent sequences: A111050 A111051 A111052 * A111054 A111055 A111056

Keyword

nonn

Author

Steve Butler, Oct 06 2005

Extensions

More terms from Joerg Arndt, Jun 25 2011

Status

approved