A111281 Number of permutations avoiding the patterns {2413,2431,4213,3412,3421,4231,4321,4312}; number of strong sorting class based on 2413.

1, 1, 2, 6, 16, 40, 100, 252, 636, 1604, 4044, 10196, 25708, 64820, 163436, 412084, 1039020, 2619764, 6605420, 16654772, 41993004, 105880308, 266964460, 673118772, 1697188012, 4279255412, 10789627756, 27204748468, 68593500716, 172950260724, 436073277676

Offset: 0

Author

Len Smiley, Nov 01 2005

Keywords

• nonn
• easy

Comments

a(n) = term (1,1) in M^n, M = the 4x4 matrix [1,1,1,1; 0,1,0,1; 0,0,1,1; 1,0,0,1]. - Gary W. Adamson, Apr 29 2009

Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>2, 1>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second and fourth elements. - Sergey Kitaev, Dec 09 2020

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..2490
• 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.
• Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
• Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
• Kai Ting Keshia Yap, David Wehlau, and Imed Zaguia, Permutations Avoiding Certain Partially-ordered Patterns, arXiv:2101.12061 [math.CO], 2021.
• Index entries for linear recurrences with constant coefficients, signature (3,-2,2).

Programs

Mathematica

a[1] = 1; a[2] = 2; a[3] = 6; a[n_] := a[n] = 3a[n - 1] - 2a[n - 2] + 2a[n - 3]; Table[a[n], {n, 28}] (* Robert G. Wilson v *)

Formula

a(n) = 3*a(n-1)-2*a(n-2)+2*a(n-3).

G.f.: 1+x*(1-x+2*x^2)/(1-3*x+2*x^2-2*x^3). - Colin Barker, Jan 16 2012

Extensions

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

a(0)=1 prepended by Alois P. Heinz, May 07 2021