|
%I #59 Aug 19 2022 11:58:48
%S 1,1,2,6,21,79,309,1237,5026,20626,85242,354080,1476368,6173634,
%T 25873744,108628550,456710589,1922354351,8098984433,34147706833,
%U 144068881455,608151037123,2568318694867,10850577045131,45856273670841,193850277807569,819669810565949
%N Number of permutations avoiding the patterns {3241,3421,4321}; number of weak sorting class based on 3241.
%C Is this the same sequence as A026737? - _Andrew S. Plewe_, May 09 2007
%C Yes, see the Callan reference "A bijection...". - _Joerg Arndt_, Feb 29 2016
%C 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
%H Alois P. Heinz, <a href="/A111279/b111279.txt">Table of n, a(n) for n = 0..1000</a> (terms n=1..300 from Vincenzo Librandi)
%H M. Albert, R. Aldred, M. Atkinson, C. Handley, D. Holton, D. McCaughan and H. van Ditmarsch, <a href="https://doi.org/10.37236/1928">Sorting Classes</a>, Elec. J. of Comb. 12 (2005) R31.
%H David Callan, <a href="http://arxiv.org/abs/1602.08347">A bijection for two sequences in OEIS</a>, arXiv:1602.08347 [math.CO], 2016.
%H David Callan, and Toufik Mansour, <a href="http://arxiv.org/abs/1602.05182">Five subsets of permutations enumerated as weak sorting permutations</a>, arXiv:1602.05182 [math.CO], 2016.
%H Alice L. L. Gao and Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H Alice L. L. Gao, and Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%F O.g.f.: (3-13*x+2*x^2+(5*x-1)*sqrt(1-4*x))/(2*(1-4*x-x^2)).
%F From _Gary W. Adamson_, Nov 14 2011: (Start)
%F 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:
%F 1, 1, 0, 0, 0, ...
%F 2, 1, 1, 0, 0, ...
%F 4, 1, 1, 1, 0, ...
%F 8, 1, 1, 1, 1, ...
%F ... (End)
%F 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
%F 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
%F 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
%F a(n) ~ (5/2-11/10*sqrt(5))*(sqrt(5)+2)^n. - _Vaclav Kotesovec_, Oct 18 2012
%e a(4) = 21 since the top row terms of M^3 = (11, 6, 3, 1, 0, 0, 0, ...)
%t 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 *)
%K nonn
%O 0,3
%A _Len Smiley_, Nov 01 2005
%E More terms from _Robert G. Wilson v_, Nov 04 2005
%E a(0)=1 prepended by _Alois P. Heinz_, Dec 11 2020
|
