cp's OEIS Frontend

A140257 Number of permutations p of order n such that the system of congruences x == i (mod p(i)), i=1..n, is solvable.

%I A140257 #3 Mar 30 2012 17:27:01
%S A140257 1,2,6,8,48,24,216,120,240,128,2544,336,11520,3168,1536,480,23616,2592
%N A140257 Number of permutations p of order n such that the system of congruences x == i (mod p(i)), i=1..n, is solvable.
%C A140257 The system of congruences x == i (mod p(i)), i=1..n, is solvable if and only if for every pair of indices i,j=1..n, gcd(p(i),p(j)) divides (i-j).
%C A140257 Note that if the system is solvable for a permutation p=(p(1),p(2),...,p(n)), then it is solvable for reversed permutation (p(n),p(n-1),...,p(1)). Also, any two primes q1, q2 greater than n/2 in p can be exchanged without affecting the system solvability. Therefore for n>1, a(n) is divisible by 2*(A000720(n)-A000720(n/2))!.
%o A140257 (PARI) { allper(n,i) = local(b); if(i>n,r++;return); p[i]=0; while(p[i]<n, p[i]++; if(P[p[i]],next); if(q[p[i]]>m,next); b=0; for(j=1,i-1, if((i-j)%gcd(p[i],p[j]),b=1;break)); if(b,next); P[p[i]]=1; if(q[p[i]]==m,m++;allper(n,i+1);m--,allper(n,i+1)); P[p[i]]=0) } { a(n) = P=p=q=vector(n); for(i=1,n,if(isprime(i),q[i]=primepi(i))); m=primepi(n\2)+1; r=0; allper(n,1); r*(primepi(n)-primepi(n\2))! }
%K A140257 nonn
%O A140257 1,2
%A A140257 _Max Alekseyev_, May 16 2008, May 17 2008