A111280 Number of permutations avoiding the patterns {4231, 4321, 35142, 45312, 42513, 45132, 35412, 45213, 43512, 456123, 351624, 451623, 356124}; number of strong sorting class based on 4231.

1, 1, 2, 6, 22, 113, 431, 1584, 5920, 22214, 83239, 311777, 1167902, 4375090, 16389450, 61395989, 229993639, 861572476, 3227511492, 12090486122, 45291815419, 169666341761, 635582108218, 2380935499534, 8919152662622, 33411776268873

Offset

0,3

Links

Table of n, a(n) for n=0..25.

M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb., Vol. 12 (2005), R31.

Index entries for linear recurrences with constant coefficients, signature (4,-2,4,0,-1).

Formula

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

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

Mathematica

a[1] = 1; a[2] = 2; a[3] = 6; a[4] = 22; a[5] = 113; a[n_] := a[n] = 4a[n - 1] - 2a[n - 2] + 4a[n - 3] - a[n - 5]; Table[ a[n], {n, 25}] (* Robert G. Wilson v, Nov 04 2005 *)
LinearRecurrence[{4, -2, 4, 0, -1}, {1, 2, 6, 22, 113}, 30] (* Harvey P. Dale, Jun 03 2019 *)

Crossrefs

Sequence in context: A174074 A290279 A014371 * A095817 A370525 A352413

Adjacent sequences: A111277 A111278 A111279 * A111281 A111282 A111283

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, Mar 12 2024

Status

approved