A174072 -id:A174072 - cp's OEIS frontend

1, 1, 2, 5, 20, 102, 626, 4458, 36144, 328794, 3316944, 36755520, 443828184, 5800823880, 81591320880, 1228888215960, 19733475278880, 336551479543440, 6075437671458000, 115733952138747600, 2320138519554562560, 48827468196234035280, 1076310620915575933440

Offset: 0

Tom Roby, May 21 2012

nonn

Also the number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> bac where a

Also the number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> cba where a

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

			From _Alois P. Heinz_, May 22 2012: (Start)
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)

Alois P. Heinz, Table of n, a(n) for n = 0..450
Anders Claesson, From Hertzsprung's problem to pattern-rewriting systems, University of Iceland (2020).
S. Linton, J. Propp, T. Roby, and J. West, Equivalence classes of permutations under various relations generated by constrained transpositions, 2011 arXiv:1111.3920 [math.CO], J. Int. Seq. 15 (2012) #12.9.1

Cf. A174072, A210667, A210668, A210669, A210671, A212417, A212581.

Column k=0 of A343535.

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):
seq(a(n), n=0..14);  # Alois P. Heinz, Apr 14 2021
# 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:
seq(a(n), n=0..22);  # Alois P. Heinz, Apr 14 2021

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]];
Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Apr 20 2022, after Alois P. Heinz *)

my(N=30, x='x+O('x^N)); Vec(sum(k=0, N, k!*(x*(1-x^2))^k)) \\ Seiichi Manyama, Feb 20 2024

From Seiichi Manyama, Feb 20 2024: (Start)
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)

a(9)-a(22) from Alois P. Heinz, Apr 14 2021

A216716 Triangle read by rows: number of permutations of [1..n] with k progressions of rise 2, distance 1 and length 3 (n >= 0, k >= 0).

Original entry on oeis.org

1, 1, 2, 6, 24, 114, 6, 674, 44, 2, 4714, 294, 30, 2, 37754, 2272, 276, 16, 2, 340404, 20006, 2236, 216, 16, 2, 3412176, 193896, 20354, 2200, 156, 16, 2, 37631268, 2056012, 206696, 20738, 1908, 160, 16, 2, 452745470, 23744752, 2273420, 215024, 21136, 1616, 164, 16, 2

Offset: 0

N. J. A. Sloane, Sep 15 2012

			Triangle begins:
         1
         1
         2
         6 [this is for n=3]
        24
       114       6
       674      44      2
      4714     294     30     2
     37754    2272    276    16    2
    340404   20006   2236   216   16   2
   3412176  193896  20354  2200  156  16  2
  37631268 2056012 206696 20738 1908 160 16 2
  ...

Alois P. Heinz, Rows n = 0..21, flattened
K. J. Parsons, Arithmetic progressions in permutations, Thesis, Washington and Lee University, 2011
Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, 2012. [broken link]

Row sums give A000142.

Column k=0 gives A174072.

b:= proc(s, x, y) option remember; expand(`if`(s={}, 1, add(
     `if`(x>0 and x-y=2 and y-j=2, z, 1)*b(s minus {j}, y, j), j=s)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b({$1..n}, 0$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Apr 13 2021

b[s_, x_, y_] := b[s, x, y] = Expand[If[s == {}, 1, Sum[
     If[x > 0 && x - y == 2 && y - j == 2, z, 1]*
     b[s ~Complement~ {j}, y, j], {j, s}]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0,
     Exponent[p, z]}]][b[Range[n], 0, 0]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Mar 02 2022, after Alois P. Heinz *)

More terms from Alois P. Heinz, Apr 13 2021

A174073 Number of permutations of length n without modular consecutive triples i,i+2,i+4.

Original entry on oeis.org

1, 1, 2, 3, 24, 100, 594, 4389, 35744, 325395, 3288600, 36489992, 441091944, 5770007009, 81213883898, 1223895060315, 19662509172096, 335472890422812, 6057979283966814, 115434096553014565, 2314691409661484600, 48723117262650147387, 1074208020519754180896, 24755214452825129257168

Offset: 0

Isaac Lambert, Mar 06 2010

nonn

			For example, a(5) does not count the permutation (0,4,1,3,2) since 4,1,3 is an arithmetic progression of 2 mod(5).

Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012.

Max Alekseyev, Table of n, a(n) for n = 0..100
Kyle Parsons, Arithmetic Progressions in Permutations, thesis, 2011. See Table 4 p. 12.

Column k=0 of A216724.

Cf. A165960, A174072, A174074, A174075.

a(11)-a(17) from Alois P. Heinz, Apr 13 2021

Terms a(18) onward from Max Alekseyev, Feb 04 2024

A174075 Number of circular permutations of length n without modular consecutive triples i,i+2,i+4.

Original entry on oeis.org

1, 6, 18, 93, 600, 4320, 35168, 321630, 3257109, 36199458, 438126986, 5736774869, 80808984725, 1218563192160, 19587031966352, 334329804180135, 6039535339644630, 115118210695441900, 2308967760171049528, 48613722701440862328, 1072008447320752890459

Offset: 3

Isaac Lambert, Mar 06 2010

nonn

Circular permutations are permutations whose indices are from the ring of integers modulo n.

			Since a(5)=18, there are (5-1)!-18=4 circular permutations with modular consecutive triples i,i+2,i+4 in all circular permutations of length 5. These are exactly (0,2,4,1,3), (0,2,4,3,1), (0,4,2,1,3), and (0,3,2,4,1). Note some have more than one modular progression.

Max Alekseyev, Table of n, a(n) for n = 3..100
Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, 2012.

Column 1 of A216726.

Cf. A165962, A174072, A174073, A174074.

f[i_,n_,k_]:=If[i==0 && k==0,1,If[i==n && n==k,1,Binomial[k-1,k-i]*Binomial[n-k-1,k-i-1] + 2*Binomial[k-1,k-i-1]*Binomial[n-k-1,k-i-1]+Binomial[k-1,k-i-1]*Binomial[n-k-1,k-i]]];
w1[i_,n_,k_]:=If[n-2k+i<0,0,If[n-2k+i==0,1,(n-2k+i-1)!]];
a[n_,k_]:=Sum[f[i,n,k]*w1[i,n,k],{i,0,k}];
A165962[n_]:=(n-1)!+Sum[(-1)^k*a[n,k],{k,1,n}];
b[n_,k_]:=Sum[Sum[Sum[f[j,n/2,p]*f[i-j,n/2,k-p]*w2[i,j,n,k,p],{p,0,k}],{j,0,i}],{i,0,k-1}];
w2[i_,j_,n_,k_,p_]:=If[n/2-2p+j<=0 || n/2-2(k-p)+(i-j)<=0,0,(n-2k+i-1)!];
A216727[n_?EvenQ]:=(n-1)!+Sum[(-1)^k*b[n,k],{k,1,n}];
A216727[n_?OddQ]:=A165962[n];
Table[A216727[n],{n,3,23}] (* David Scambler, Sep 18 2012 *)

a(n) = A165962(n) for odd n.

A216718 Triangle read by rows: number of circular permutations of [1..n] with k progressions of rise 1, distance 1 and length 3 (n >= 3, k >= 0).

Original entry on oeis.org

1, 1, 1, 5, 0, 1, 20, 3, 0, 1, 102, 14, 3, 0, 1, 627, 72, 17, 3, 0, 1, 4461, 468, 87, 20, 3, 0, 1, 36155, 3453, 582, 103, 23, 3, 0, 1, 328849, 28782, 4395, 704, 120, 26, 3, 0, 1, 3317272, 267831, 37257, 5435, 834, 138, 29, 3, 0, 1

Offset: 2

N. J. A. Sloane, Sep 15 2012

			Triangle begins:
        1;
        1,      1; [this is row n=3]
        5,      0,     1;
       20,      3,     0,    1;
      102,     14,     3,    0,   1;
      627,     72,    17,    3,   0,   1;
     4461,    468,    87,   20,   3,   0,  1;
    36155,   3453,   582,  103,  23,   3,  0, 1;
   328849,  28782,  4395,  704, 120,  26,  3, 0, 1;
  3317272, 267831, 37257, 5435, 834, 138, 29, 3, 0, 1;
  ...

Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012.

Cf. A216716, A174072, A165961, A180187.

a(2,0)=1 added by N. J. A. Sloane, Apr 16 2021

A174080 Number of permutations of length n with no consecutive triples i,i+d,i+2d for all d>0.

Original entry on oeis.org

1, 1, 2, 5, 21, 100, 597, 4113, 32842, 292379, 2925367, 31983248, 383514347, 4966286235, 69508102006, 1039315462467, 16627618496319, 282023014602100, 5075216962675445, 96263599713301975, 1925002914124917950

Offset: 0

Isaac Lambert, Mar 15 2010

			For n=4, there are 4!-a(4)=3 permutations with some consecutive triple i,i+d,i+2d. Note for n=4, only d=1 applies. Hence those three permutations are (0,1,2,3), (1,2,3,0), and (3,0,1,2). Since here only d=1, this is the same value of a(4) in A002628.

Cf. A002628, A174072, A174081, A174082, A174083, A295370.

b:= proc(s, x, y) option remember; `if`(s={}, 1, add(
      `if`(x=0 or xy-j,
         b(s minus {j}, y, j), 0), j=s))
    end:
a:= n-> b({$1..n}, 0$2):
seq(a(n), n=0..14);  # Alois P. Heinz, Apr 13 2021

b[s_, x_, y_] := b[s, x, y] = If[s == {}, 1, Sum[If[x == 0 || x < y || x-y != y-j, b[s~Complement~{j}, y, j], 0], {j, s}]];
a[n_] := b[Range[n], 0, 0];
Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Sep 27 2022, after Alois P. Heinz *)

a(0)-a(3) and a(10)-a(20) from Alois P. Heinz, Apr 13 2021

Showing 1-8 of 8 results.

cp's OEIS Frontend

A216717 Duplicate of A174072.

Views

Author

Keywords

Crossrefs

A174074 Number of circular permutations of length n without consecutive triples i,i+2,i+4.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A212580 Number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> acb where a

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A216716 Triangle read by rows: number of permutations of [1..n] with k progressions of rise 2, distance 1 and length 3 (n >= 0, k >= 0).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A174073 Number of permutations of length n without modular consecutive triples i,i+2,i+4.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A174075 Number of circular permutations of length n without modular consecutive triples i,i+2,i+4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A216718 Triangle read by rows: number of circular permutations of [1..n] with k progressions of rise 1, distance 1 and length 3 (n >= 3, k >= 0).

Views

Author

Keywords

Examples

References

Crossrefs

Extensions

A174080 Number of permutations of length n with no consecutive triples i,i+d,i+2d for all d>0.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions