|
|
A212580
|
|
Number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> acb where a<b<c.
|
|
8
|
|
|
1, 1, 2, 5, 20, 102, 626, 4458, 36144, 328794, 3316944, 36755520, 443828184, 5800823880, 81591320880, 1228888215960, 19733475278880, 336551479543440, 6075437671458000, 115733952138747600, 2320138519554562560, 48827468196234035280, 1076310620915575933440
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Also the number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> bac where a<b<c.
Also the number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> cba where a<b<c.
Also the number of permutations of [n] avoiding consecutive triples j, j+1, j-1. a(4) = 20 = 4! - 4 counts all permutations of [4] except 1342, 2314, 3421, 4231. - Alois P. Heinz, Apr 14 2021
|
|
LINKS
|
|
|
FORMULA
|
G.f.: Sum_{k>=0} k! * ( x * (1-x^2) )^k.
a(n) = Sum_{k=0..floor(n/3)} (-1)^k * (n-2*k)! * binomial(n-2*k,k). (End)
|
|
EXAMPLE
|
a(3) = 5: {123, 132}, {213}, {231}, {312}, {321}.
a(4) = 20: {1234, 1243, 1324}, {1342}, {1423}, {1432}, {2134}, {2143}, {2314}, {2341, 2431}, {2413}, {3124}, {3142}, {3214}, {3241}, {3412}, {3421}, {4123, 4132}, {4213}, {4231}, {4312}, {4321}. (End)
|
|
MAPLE
|
b:= proc(s, x, y) option remember; `if`(s={}, 1, add(
`if`(x=0 or x-y<>1 or j-x<>1, b(s minus {j}, y, j), 0), j=s))
end:
a:= n-> b({$1..n}, 0$2):
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [1$2, 2, 5, 20][n+1],
n*a(n-1)+3*a(n-2)-(2*n-2)*a(n-3)+(n-2)*a(n-5))
end:
|
|
MATHEMATICA
|
a[n_] := a[n] = If[n < 5, {1, 1, 2, 5, 20}[[n+1]],
n*a[n-1] + 3*a[n-2] - (2n - 2)*a[n-3] + (n-2)*a[n-5]];
|
|
PROG
|
(PARI) my(N=30, x='x+O('x^N)); Vec(sum(k=0, N, k!*(x*(1-x^2))^k)) \\ Seiichi Manyama, Feb 20 2024
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|