A111283 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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