A216718 -id:A216718 - cp's OEIS frontend

A165961 Number of circular permutations of length n without 3-sequences.

1, 5, 20, 102, 627, 4461, 36155, 328849, 3317272, 36757822, 443846693, 5800991345, 81593004021, 1228906816941, 19733699436636, 336554404751966, 6075478765948135, 115734570482611885, 2320148441078578447, 48827637296350480457, 1076313671861962141616

Offset: 3

Isaac Lambert, Oct 01 2009

nonn

Circular permutations are permutations whose indices are from the ring of integers modulo n. 3-sequences are of the form i,i+1,i+2. Sequence gives number of permutations of [n] starting with 1 and having no 3-sequences.

a(n) is also the number of permutations of length n-1 without consecutive fixed points (cf. A180187). - David Scambler, Mar 27 2011

			For n=4 the a(4)=5 solutions are (0,1,3,2), (0,2,1,3), (0,2,3,1), (0,3,1,2) and (0,3,2,1).

Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012. - From N. J. A. Sloane, Sep 15 2012 [broken link]

Michael De Vlieger, Table of n, a(n) for n = 3..450
Wayne M. Dymacek and Isaac Lambert, Permutations Avoiding Runs of i, i+1, i+2 or i, i-1, i-2, Journal of Integer Sequences, Vol. 14 (2011), Article 11.1.6.
Kyle Parsons, Arithmetic progressions in permutations, Thesis, 2011.

Cf. A002628, A165960, A165962.
Cf. A000166, A180186, - Emeric Deutsch, Sep 07 2010
A column of A216718. - N. J. A. Sloane, Sep 15 2012

d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: sum(binomial(n-k, k)*d[n-k-1], k = 0 .. floor((1/2)*n)) end proc: seq(a(n), n = 3 .. 23); # Emeric Deutsch, Sep 07 2010

a[n_] := Sum[Binomial[n-k, k] Subfactorial[n-k-1], {k, 0, n/2}];
a /@ Range[3, 21] (* Jean-François Alcover, Oct 29 2019 *)

Let b(n) be the sequence A002628. Then for n > 5, this sequence satisfies a(n) = b(n-1) - b(n-3) + a(n-3).

a(n) = Sum_{k=0..n/2} binomial(n-k,k)*d(n-k-1), where d(j)=A000166(j) are the derangement numbers. - Emeric Deutsch, Sep 07 2010

More terms from Emeric Deutsch, Sep 07 2010

Edited by N. J. A. Sloane, Apr 04 2011

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

Original entry on oeis.org

2, 6, 22, 2, 109, 10, 1, 657, 55, 7, 1, 4625, 356, 54, 4, 1, 37186, 2723, 362, 44, 4, 1, 336336, 23300, 2837, 368, 34, 4, 1, 3379058, 220997, 25408, 2967, 330, 35, 4, 1, 37328103, 2308564, 249736, 26964, 3100, 292, 36, 4, 1

Offset: 3

N. J. A. Sloane, Sep 15 2012

			Triangle begins:
         2
         6
        22       2
       109      10      1
       657      55      7     1
      4625     356     54     4    1
     37186    2723    362    44    4   1
    336336   23300   2837   368   34   4  1
   3379058  220997  25408  2967  330  35  4 1
  37328103 2308564 249736 26964 3100 292 36 4 1
  ...

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

Columns 1..2 are A174074, A216721.
Row sums are A000142(n-1).
Cf. A216716, A216718.

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

Original entry on oeis.org

1, 0, 0, 1, 5, 0, 0, 0, 1, 18, 5, 0, 0, 0, 1, 95, 18, 6, 0, 0, 0, 1, 600, 84, 28, 7, 0, 0, 0, 1, 4307, 568, 116, 40, 8, 0, 0, 0, 1, 35168, 4122, 810, 156, 54, 9, 0, 0, 0, 1, 321609, 33910, 5975, 1100, 205, 70, 10, 0, 0, 0, 1

Offset: 3

N. J. A. Sloane, Sep 15 2012

			Triangle begins:
       1,     0,    0,    1;
       5,     0,    0,    0,   1;
      18,     5,    0,    0,   0,  1;
      95,    18,    6,    0,   0,  0,  1;
     600,    84,   28,    7,   0,  0,  0, 1;
    4307,   568,  116,   40,   8,  0,  0, 0, 1;
   35168,  4122,  810,  156,  54,  9,  0, 0, 0, 1;
  321609, 33910, 5975, 1100, 205, 70, 10, 0, 0, 0, 1;
  ...

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

Columns 1..2 are A165962, A216723.
Row sums are A000142(n-1).
Cf. A216716, A216718, A216719, A165962.

A180187 Number of successions in all the permutations p of [n] such that p(1)=1 and having no 3-sequences. A succession of a permutation p is a position i such that p(i +1) - p(i) = 1.

Original entry on oeis.org

0, 1, 0, 3, 14, 72, 468, 3453, 28782, 267831, 2752828, 30984336, 379125192, 5011756625, 71190365580, 1081514329155, 17499480412746, 300473929597320, 5457031426340748, 104520033700333069, 2105651342251571562

Offset: 1

Emeric Deutsch, Sep 06 2010

nonn

From Emeric Deutsch, Sep 07 2010: (Start)
a(n) is also the number of fixed points in all those permutations of [n-1] that have no adjacent fixed points. Example: a(4)=3 because in 132, 213, 231, 312, 321 we have 1+1+0+0+1 fixed points.
a(n) is also the number of permutations of [n] having exactly 1 pair of adjacent fixed points. Example: a(4)=3 because we have 1243, 4231, and 2134.
(End)

			a(4)=3 because in 1*243, 1324, 13*42, 142*3, 1432 we have 3 successions (marked *).

Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012. - From N. J. A. Sloane, Sep 15 2012

Cf. A000166, A180186.

A column of A216718. - N. J. A. Sloane, Sep 15 2012

d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: seq(sum(k*binomial(n-k, k)*d[n-1-k], k = 0 .. floor((1/2)*n)), n = 1 .. 22);

a[0] = 1; a[n_] := a[n] = n*a[n - 1] + (-1)^n; f[n_] := Sum[k*Binomial[n - k, k]*a[n - k - 1], {k, 0, n/2}]; Array[f, 21] (* Robert G. Wilson v, Apr 01 2011 *)
a[n_] := Sum[k Binomial[n - k, k] Subfactorial[n - k - 1], {k, 0, n/2}];
a /@ Range[1, 21] (* Jean-François Alcover, Oct 29 2019 *)

a(n) = Sum_{k>=0} k*A180186(n,k).

a(n) = Sum_{k=0..floor(n/2)} k*binomial(n-k,k)*d(n-1-k), where d(j)=A000166(j) are the derangement numbers.

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

Original entry on oeis.org

1, 1, 2, 3, 3, 24, 0, 100, 15, 0, 5, 594, 108, 18, 0, 4389, 504, 119, 21, 0, 7, 35744, 3520, 960, 64, 32, 0, 325395, 31077, 5238, 927, 207, 27, 0, 9, 3288600, 288300, 42050, 8800, 900, 100, 50, 0, 36489992, 2946141, 409827, 59785, 9174, 1518, 319, 33, 0, 11

Offset: 0

N. J. A. Sloane, Sep 15 2012

			Triangle begins:
        1
        1
        2
        3      3
       24      0
      100     15     0    5
      594    108    18    0
     4389    504   119   21   0   7
    35744   3520   960   64  32   0
   325395  31077  5238  927 207  27  0 9
  3288600 288300 42050 8800 900 100 50 0
  ...

Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, Congressus Numerantium, Vol. 208 (2011), pp. 147-165.

Alois P. Heinz, Rows n = 0..18, flattened

Column 1 is A174073.
Row sums are A000142.
Cf. A216716, A216718, A216719, A216722.

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

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

More terms from Alois P. Heinz, Apr 13 2021

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

Original entry on oeis.org

11, 0, 0, 1, 6, 0, 0, 0, 0, 18, 5, 0, 0, 0, 1, 93, 18, 9, 0, 0, 0, 0, 600, 84, 28, 7, 0, 0, 0, 1, 4320, 512, 192, 0, 16, 0, 0, 0, 0, 35168, 4122, 810, 156, 54, 9, 0, 0, 0, 1, 321630, 34000, 5625, 1400, 200, 0, 25, 0, 0, 0, 0

Offset: 3

N. J. A. Sloane, Sep 15 2012

			Triangle begins:
1 0 0 1
6 0 0 0 0
18 5 0 0 0 1
93 18 9 0 0 0 0
600 84 28 7 0 0 0 1
4320 512 192 0 16 0 0 0 0
35168 4122 810 156 54 9 0 0 0 1
321630 34000 5625 1400 200 0 25 0 0 0 0
...

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

Cf. A216716, A216718, A216719, A216722, A216724, A174075.

cp's OEIS Frontend

A165961 Number of circular permutations of length n without 3-sequences.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Examples

References

Crossrefs

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

Views

Author

Keywords

Examples

References

Crossrefs

A180187 Number of successions in all the permutations p of [n] such that p(1)=1 and having no 3-sequences. A succession of a permutation p is a position i such that p(i +1) - p(i) = 1.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

Views

Author

Keywords

Examples

References

Crossrefs