A228231 Number of equivalence classes in S_n under the {123, 321} {132, 231}-equivalence.

4, 8, 18, 36, 88, 176, 470, 940, 2784, 5568, 18564, 37128, 140496, 280992, 1205406, 2410812, 11625040, 23250080, 124582172, 249164344, 1467151632, 2934303264, 18808816988, 37617633976, 260504960128, 521009920256, 3874087578120, 7748175156240, 61547948858400, 123095897716800

Offset

3,1

Links

Alois P. Heinz, Table of n, a(n) for n = 3..400

William Kuszmaul, Counting Permutations Modulo Pattern-Replacement Equivalences for Three-Letter Patterns, arXiv:1304.5667 [math.CO], 2013.

Formula

a(n) = sum(k=1..l, k!*binomial(n-k-1,h-1)) + sum(k=1..h, k!*binomial(n-k-1,l-1)) where l = floor(n/2) and h = ceiling(n/2).

a(n) ~ sqrt(Pi) * n^(n/2+1/2) / (2^(n/2-1) * exp(n/2-1)) if n is even and a(n) ~ sqrt(Pi) * n^(n/2+1) / (2^(n/2+1/2) * exp(n/2-1)) if n is odd. - Vaclav Kotesovec, Aug 23 2014

Maple

a:= proc(n) option remember;
      `if`(n<9, [0, 1, 2, 4, 8, 18, 36, 88, 176][n+1],
       ((8*n-20)*a(n-1) +(n^3+21*n^2-181*n+319)*a(n-2)
       -(6*n^2+46*n-290)*a(n-3) -(12*n^3-8*n^2-800*n+2680)*a(n-4)
       +(48*n^2-240*n-240)*a(n-5) +(48*n^3-560*n^2+1312*n+2112)*a(n-6)
       -32*(n-6)*(3*n-19)*a(n-7) -64*(n-6)*(n-7)^2*a(n-8))/
      (2*(n-1)*(n-3)))
    end:
seq(a(n), n=3..50);  # Alois P. Heinz, Aug 26 2013

Mathematica

a[n_] := Sum[k!*Binomial[n - k - 1, Ceiling[n/2] - 1], {k, 1, Floor[n/2]}] + Sum[s!*Binomial[n - s - 1, Floor[n/2] - 1], {s, 1, Ceiling[n/2]}]; Table[a[n], {n, 3, 50}] (* G. C. Greubel, Apr 03 2017 *)

Prog

(PARI)
a(n)={ my(l=floor(n/2), h=ceil(n/2));
sum(k=1, l, k!*binomial(n-k-1, h-1))+sum(k=1, h, k!*binomial(n-k-1, l-1)); }
\\ Joerg Arndt, Aug 16 2013

Crossrefs

Sequence in context: A007784 A008204 A190062 * A175657 A080287 A280155

Adjacent sequences: A228228 A228229 A228230 * A228232 A228233 A228234

Keyword

nonn

Author

William Kuszmaul, Aug 16 2013

Status

approved