|
| |
|
|
A140257
|
|
Number of permutations p of order n such that the system of congruences x == i (mod p(i)), i=1..n, is solvable.
|
|
1
| |
|
|
1, 2, 6, 8, 48, 24, 216, 120, 240, 128, 2544, 336, 11520, 3168, 1536, 480, 23616, 2592
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| 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).
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))!.
|
|
|
PROG
| (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))! }
|
|
|
CROSSREFS
| Sequence in context: A050552 A105607 A098239 * A204546 A192534 A053938
Adjacent sequences: A140254 A140255 A140256 * A140258 A140259 A140260
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Max Alekseyev (maxale(AT)gmail.com), May 16 2008, May 17 2008
|
| |
|
|
