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.

References

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

Links

Table of n, a(n) for n=3..23.

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