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

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

Offset

3,2

Comments

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

Links

Max Alekseyev, Table of n, a(n) for n = 3..100

Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, 2012.

Formula

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

Example

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.

Mathematica

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 *)

Crossrefs

Column 1 of A216726.

Cf. A165962, A174072, A174073, A174074.

Sequence in context: A194995 A104970 A216727 * A151470 A280096 A009573

Adjacent sequences: A174072 A174073 A174074 * A174076 A174077 A174078

Keyword

nonn

Author

Isaac Lambert, Mar 06 2010

Status

approved