A111283 Number of permutations avoiding the patterns {4321, 45132, 45231, 35412, 53412, 45213, 43512, 45312, 456123, 451623, 356124}; number of strong sorting class based on 4321.

1, 1, 2, 6, 23, 96, 409, 1751, 7505, 32176, 137956, 591501, 2536132, 10873981, 46623553, 199904321, 857114814, 3674987126, 15756967635, 67559972476, 289671844661, 1242004318751, 5325249092137, 22832672531956, 97897943538708

Offset

0,3

Links

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

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 (5,-3,0,-1).

Formula

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

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

Mathematica

a[1] = 1; a[2] = 2; a[3] = 6; a[n_] := a[n] = 4a[n - 1] + a[n - 2] + a[n - 3] - 4; Table[a[n], {n, 24}] (* Robert G. Wilson v, Nov 04 2005 *)
LinearRecurrence[{5, -3, 0, -1}, {1, 2, 6, 23}, 30] (* Harvey P. Dale, Jan 01 2017 *)

Crossrefs

Sequence in context: A150295 A150296 A134064 * A150297 A374165 A150298

Adjacent sequences: A111280 A111281 A111282 * A111284 A111285 A111286

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

Status

approved