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

%I #42 Apr 12 2023 11:14:03

%S 1,2,6,22,89,379,1661,7405,33367,151398,690147,3156112,14465746,

%T 66409493,305232025,1404129530,6463476538,29767212095,137142651679,

%U 632021380433,2913316615372,13431328632593,61931182541194,285592218851606,1317104663887309,6074682489939359,28018852961838675,129239701278757210

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

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

%H H. Abe and S. Billey, <a href="http://www.math.washington.edu/~billey/papers/abe.billey.pdf">Consequences of the Lakshmibai-Sandhya theorem: the ubiquity of permutation patterns in Schubert calculus and related geometry</a>, 2014.

%H M. Bousquet-Mélou and S. Butler, <a href="https://arxiv.org/abs/math/0603617">Forest-like permutations</a>, arXiv:math/0603617 [math.CO], 2006.

%H S. Butler, <a href="https://www.semanticscholar.org/paper/On-permutations-which-are-1324-and-2143-avoiding-Butler/47ff2e8d8461087e56de6840058a5dffd1290196">On permutations which are 1324 and {overline 2143} avoiding</a>, 2005.

%H S. B. Ekhad and M. Yang, <a href="http://sites.math.rutgers.edu/~zeilberg/tokhniot/oMathar1maple12.txt">Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences</a>, (2017).

%H Haruhisa Enomoto, <a href="https://arxiv.org/abs/2002.09205">Bruhat inversions in Weyl groups and torsion-free classes over preprojective algebras</a>, arXiv:2002.09205 [math.RT], 2020.

%F 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

%F 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

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

%F 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

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

%t 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}]];

%t Array[a, 28] (* _Jean-François Alcover_, Dec 17 2018 *)

%o (PARI) x='x+O('x^66);

%o 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));

%o Vec(gf) /* _Joerg Arndt_, Jun 25 2011 */

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

%Y Cf. A204200.

%K nonn

%O 1,2

%A _Steve Butler_, Oct 06 2005

%E More terms from _Joerg Arndt_, Jun 25 2011