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
Keywords
Examples
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.
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.
Programs
-
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 *)
Formula
a(n) = A165962(n) for odd n.
Comments