login
A111279
Number of permutations avoiding the patterns {3241,3421,4321}; number of weak sorting class based on 3241.
3
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,3
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
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.
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
EXAMPLE
a(4) = 21 since the top row terms of M^3 = (11, 6, 3, 1, 0, 0, 0, ...)
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 *)
CROSSREFS
Sequence in context: A366082 A148491 A026737 * A150197 A150198 A257562
KEYWORD
nonn
AUTHOR
Len Smiley, Nov 01 2005
EXTENSIONS
More terms from Robert G. Wilson v, Nov 04 2005
a(0)=1 prepended by Alois P. Heinz, Dec 11 2020
STATUS
approved