A180187 -id:A180187 - 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

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

A180186 Triangle read by rows: T(n,k) is the number of permutations of [n] starting with 1, having no 3-sequences and having k successions (0 <= k <= floor(n/2)); a succession of a permutation p is a position i such that p(i +1) - p(i) = 1.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 2, 3, 0, 9, 8, 3, 44, 45, 12, 1, 265, 264, 90, 8, 1854, 1855, 660, 90, 2, 14833, 14832, 5565, 880, 45, 133496, 133497, 51912, 9275, 660, 9, 1334961, 1334960, 533988, 103824, 9275, 264, 14684570, 14684571, 6007320, 1245972, 129780, 5565

Offset: 0

Emeric Deutsch, Sep 06 2010

Row n has 1+floor(n/2) entries.
Sum of entries in row n is A165961(n).
T(n,0) = d(n-1).
Sum_{k>=0} k*T(n,k) = A180187(n).
From Emeric Deutsch, Sep 07 2010: (Start)
T(n,k) is also the number of permutations of [n-1] with k fixed points, no two of them adjacent. Example: T(5,2)=3 because we have 1432, 1324, and 3214.
(End)

			T(5,2)=3 because we have 12453, 12534, and 14523.
Triangle starts:
    1;
    1;
    0,   1;
    1,   0;
    2,   3,   0;
    9,   8,   3;
   44,  45,  12,  1;
  265, 264,  90,  8;

Cf. A000166, A165961, A180187.

d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n, k) if n = 0 and k = 0 then 1 elif k <= (1/2)*n then binomial(n-k, k)*d[n-1-k] else 0 end if end proc: for n from 0 to 12 do seq(a(n, k), k = 0 .. (1/2)*n) end do; # yields sequence in triangular form

T(n,k) = binomial(n-k,k)*d(n-k-1), where d(j) = A000166(j) are the derangement numbers.

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

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

A180186 Triangle read by rows: T(n,k) is the number of permutations of [n] starting with 1, having no 3-sequences and having k successions (0 <= k <= floor(n/2)); a succession of a permutation p is a position i such that p(i +1) - p(i) = 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula