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,3

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).

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

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 *)

Crossrefs

Sequence in context: A264551 A293004 A265278 * A018021 A215340 A074405

Adjacent sequences: A111278 A111279 A111280 * A111282 A111283 A111284

Keyword

nonn,easy

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, May 07 2021

Status

approved