A111279 Number of permutations avoiding the patterns {3241,3421,4321}; number of weak sorting class based on 3241.

1, 1, 2, 6, 21, 79, 309, 1237, 5026, 20626, 85242, 354080, 1476368, 6173634, 25873744, 108628550, 456710589, 1922354351, 8098984433, 34147706833, 144068881455, 608151037123, 2568318694867, 10850577045131, 45856273670841, 193850277807569, 819669810565949

Offset: 0

Author

Len Smiley, Nov 01 2005

Keywords

• nonn

Comments

Is this the same sequence as A026737? - Andrew S. Plewe, May 09 2007

Yes, see the Callan reference "A bijection...". - Joerg Arndt, Feb 29 2016

a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>3, 1>4, 3>2} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the first element is the largest and the third element is larger than the second element. - Sergey Kitaev, Dec 10 2020

Examples

			a(4) = 21 since the top row terms of M^3 = (11, 6, 3, 1, 0, 0, 0, ...)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n=1..300 from Vincenzo Librandi)
• M. Albert, R. Aldred, M. Atkinson, C. Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb. 12 (2005) R31.
• David Callan, A bijection for two sequences in OEIS, arXiv:1602.08347 [math.CO], 2016.
• David Callan, and Toufik Mansour, Five subsets of permutations enumerated as weak sorting permutations, arXiv:1602.05182 [math.CO], 2016.
• Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
• Alice L. L. Gao, and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

Programs

Mathematica

Rest[ CoefficientList[ Series[(3 - 13x + 2x^2 + (5x - 1)*Sqrt[1 - 4x])/(2*(1 - 4x - x^2)), {x, 0, 24}], x]] (* Robert G. Wilson v, Nov 04 2005 *)

Formula

O.g.f.: (3-13*x+2*x^2+(5*x-1)*sqrt(1-4*x))/(2*(1-4*x-x^2)).

From Gary W. Adamson, Nov 14 2011: (Start)

a(n) is the sum of top row terms of M^(n-1), M is an infinite square production matrix with powers of 2 as the left border as follows:

1, 1, 0, 0, 0, ...

2, 1, 1, 0, 0, ...

4, 1, 1, 1, 0, ...

8, 1, 1, 1, 1, ...

... (End)

The top rows of these matrix powers, 1; 1,1; 3,2,1; 11,6,3,1; 43,21,10,4,1; appear also as columns in A026736. - R. J. Mathar, Nov 15 2011

D-finite with recurrence n*a(n) + (16-13*n)*a(n-1)+(55*n-134)*a(n-2) + (264-71*n)*a(n-3) + 10*(7-2*n)*a(n-4) = 0. - R. J. Mathar, Nov 15 2011

Shorter recurrence: n*(n+5)*a(n) = 2*(4*n^2 + 17*n - 30)*a(n-1) - 3*(5*n^2 + 17*n - 80)*a(n-2) - 2*(n+6)*(2*n-5)*a(n-3). - Vaclav Kotesovec, Oct 18 2012

a(n) ~ (5/2-11/10*sqrt(5))*(sqrt(5)+2)^n. - Vaclav Kotesovec, Oct 18 2012

Extensions

More terms from Robert G. Wilson v, Nov 04 2005

a(0)=1 prepended by Alois P. Heinz, Dec 11 2020