A111285 Number of permutations avoiding the patterns {2431, 3421, 4231, 4321, 24513, 42513, 34512, 43512}; number of strong sorting class based on 2431.

1, 1, 2, 6, 20, 66, 216, 706, 2308, 7546, 24672, 80666, 263740, 862306, 2819336, 9217906, 30138228, 98537866, 322172592, 1053353226, 3443970860, 11260168946, 36815469656, 120369313506, 393551182948, 1286727730586, 4206996000512

Offset

0,3

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

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,-3,2).

Formula

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

G.f.: 1+x*(1-x)^2/(1-4*x+3*x^2-2*x^3).

a(n) = A175005(n)+A175005(n-2)-2*A175005(n-1). - R. J. Mathar, Aug 19 2022~

Mathematica

a[1] = 1; a[2] = 2; a[3] = 6; a[n_] := a[n] = 4a[n - 1] - 3a[n - 2] + 2a[n - 3]; Table[a[n], {n, 26}] (* Robert G. Wilson v *)
CoefficientList[Series[(1-2*x+x^2)/(1-4*x+3*x^2-2*x^3), {x, 0, 40}], x] (* or *) LinearRecurrence[{4, -3, 2}, {1, 2, 6}, 40] (* Vincenzo Librandi, Jun 27 2012 *)

Prog

(Magma) I:=[1, 2, 6]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2)+2*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jun 27 2012

Crossrefs

Sequence in context: A083323 A174846 A369431 * A052991 A246019 A226510

Adjacent sequences: A111282 A111283 A111284 * A111286 A111287 A111288

Keyword

nonn,easy

Author

Len Smiley, Nov 01 2005

Extensions

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

Status

approved