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

Author

Len Smiley, Nov 01 2005

Keywords

• nonn

Links

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

Programs

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

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

a(n) = 5*a(n-1) - 3*a(n-2) - a(n-4). - Wesley Ivan Hurt, Aug 04 2025

Extensions

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

a(0)=1 prepended by Alois P. Heinz, Mar 12 2024