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

Author

Len Smiley, Nov 01 2005

Keywords

• nonn
• easy

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

Programs

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

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

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~

Extensions

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