|
%I #51 Feb 21 2024 06:16:51
%S 1,1,2,5,20,102,626,4458,36144,328794,3316944,36755520,443828184,
%T 5800823880,81591320880,1228888215960,19733475278880,336551479543440,
%U 6075437671458000,115733952138747600,2320138519554562560,48827468196234035280,1076310620915575933440
%N Number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> acb where a<b<c.
%C 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.
%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.
%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
%H Alois P. Heinz, <a href="/A212580/b212580.txt">Table of n, a(n) for n = 0..450</a>
%H Anders Claesson, <a href="https://akc.is/papers/036-From-Hertzsprungs-problem-to-pattern-rewriting-systems.pdf">From Hertzsprung's problem to pattern-rewriting systems</a>, University of Iceland (2020).
%H S. Linton, J. Propp, T. Roby, and J. West, <a href="http://arxiv.org/abs/1111.3920">Equivalence classes of permutations under various relations generated by constrained transpositions, 2011</a> arXiv:1111.3920 [math.CO], <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Roby/roby4.html">J. Int. Seq. 15 (2012) #12.9.1</a>
%F From _Seiichi Manyama_, Feb 20 2024: (Start)
%F G.f.: Sum_{k>=0} k! * ( x * (1-x^2) )^k.
%F a(n) = Sum_{k=0..floor(n/3)} (-1)^k * (n-2*k)! * binomial(n-2*k,k). (End)
%e From _Alois P. Heinz_, May 22 2012: (Start)
%e a(3) = 5: {123, 132}, {213}, {231}, {312}, {321}.
%e 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)
%p b:= proc(s, x, y) option remember; `if`(s={}, 1, add(
%p `if`(x=0 or x-y<>1 or j-x<>1, b(s minus {j}, y, j), 0), j=s))
%p end:
%p a:= n-> b({$1..n}, 0$2):
%p seq(a(n), n=0..14); # _Alois P. Heinz_, Apr 14 2021
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n<5, [1$2, 2, 5, 20][n+1],
%p n*a(n-1)+3*a(n-2)-(2*n-2)*a(n-3)+(n-2)*a(n-5))
%p end:
%p seq(a(n), n=0..22); # _Alois P. Heinz_, Apr 14 2021
%t a[n_] := a[n] = If[n < 5, {1, 1, 2, 5, 20}[[n+1]],
%t n*a[n-1] + 3*a[n-2] - (2n - 2)*a[n-3] + (n-2)*a[n-5]];
%t Table[a[n], {n, 0, 22}] (* _Jean-François Alcover_, Apr 20 2022, after _Alois P. Heinz_ *)
%o (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
%Y Cf. A174072, A210667, A210668, A210669, A210671, A212417, A212581.
%Y Column k=0 of A343535.
%K nonn
%O 0,3
%A _Tom Roby_, May 21 2012
%E a(9)-a(22) from _Alois P. Heinz_, Apr 14 2021
|
