A111286 Number of permutations avoiding the patterns {1342, 1432, 2341, 2431, 3142, 3241, 3412, 3421, 4132, 4231, 4312, 4321}; number of strong sorting class based on 1342.

1, 1, 2, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472

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

Crossrefs

Cf. A003945, A007283, A042950, A098011, A110164 - differs from each by one initial term.

Programs

Mathematica

Table[If[n == 1, 1, If[n == 2, 2, 3*2^(n - 2)]], {n, 32}] (* Robert G. Wilson v *)
LinearRecurrence[{2},{1,2,6},40] (* Harvey P. Dale, Jul 14 2019 *)

Formula

a(n) = 3*2^(n-2), n>=3.

a(n) = 2*a(n-1) for n=3. G.f.: (1-x+2*x^3)/(1-2*x). - Colin Barker, Nov 29 2012

Extensions

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