A111280 Number of permutations avoiding the patterns {4231, 4321, 35142, 45312, 42513, 45132, 35412, 45213, 43512, 456123, 351624, 451623, 356124}; number of strong sorting class based on 4231.
1, 1, 2, 6, 22, 113, 431, 1584, 5920, 22214, 83239, 311777, 1167902, 4375090, 16389450, 61395989, 229993639, 861572476, 3227511492, 12090486122, 45291815419, 169666341761, 635582108218, 2380935499534, 8919152662622, 33411776268873
Offset: 0
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 (4,-2,4,0,-1).
Programs
-
Mathematica
a[1] = 1; a[2] = 2; a[3] = 6; a[4] = 22; a[5] = 113; a[n_] := a[n] = 4a[n - 1] - 2a[n - 2] + 4a[n - 3] - a[n - 5]; Table[ a[n], {n, 25}] (* Robert G. Wilson v, Nov 04 2005 *) LinearRecurrence[{4,-2,4,0,-1},{1,2,6,22,113},30] (* Harvey P. Dale, Jun 03 2019 *)
Formula
a(n) = 4*a(n-1)-2*a(n-2)+4*a(n-3)-a(n-5).
G.f.: 1+x*(1-2*x-2*x^3+29*x^4)/(1-4*x+2*x^2-4*x^3+x^5). - Colin Barker, Jan 16 2012
Extensions
More terms from Robert G. Wilson v, Nov 04 2005
a(0)=1 prepended by Alois P. Heinz, Mar 12 2024