login
A174075
Number of circular permutations of length n without modular consecutive triples i,i+2,i+4.
7
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
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.
Sequence in context: A194995 A104970 A216727 * A151470 A280096 A009573
KEYWORD
nonn
AUTHOR
Isaac Lambert, Mar 06 2010
STATUS
approved