|
%I #21 Jul 27 2017 08:13:36
%S 1,2,4,15,72,425,3038
%N Number of permutations in S_n that are factorials of permutations in lexicographic order.
%C Let sigma(i), 1 <= i <= n!, be the i-th permutation in S_n in lexicographic order. a(n) = |{sigma(1)sigma(2)...sigma(i)| 1 <= i <= n!}|.
%C This is an S_n analog of the problem studied in the references section.
%D B. Rokowska and A. Schinzel. Sur un problème de M. Erdős. Elem. Math., 15:84-85, 1960.
%H W. D. Banks, F. Luca, I. E. Shparlinski, H. Stichtenoth, <a href="http://journals.tubitak.gov.tr/math/abstract.htm?id=7510">On the Value Set of n! Modulo a Prime</a>, Turk. J. Math., 29, (2005), 169-174.
%H T. Trudgian, <a href="http://www.emis.de/journals/INTEGERS/papers/o63/o63.Abstract.html">There are no socialist primes less than 10^9</a>, INTEGERS, 14 (2014), A63.
%o (PARI)
%o for(n=1,7,q=vector(n!);count=0;m2=matid(n);q[1]=m2;v=vector(n);for(i=1,n,v[i]=i);v3=vector(n);for(i=1,n,v3[i]=n-i+1);
%o while(v3!=v,for(i=1,n-1,if(v[i]<v[i+1],a=i);for(i=a+1,n,if(v[i]> v[a],b=i)));temp=v[a];v[a]=v[b];v[b]=temp;
%o v2=vector(n-(a+1)+1);for(i=1,n-(a+1)+1,v2[i]=v[n-i+1]);for(i=a+1,n,v[i]=v2[i-a]);
%o m=matrix(n,n);for(i=1,n,m[v[i],i]=1);q[count+2]=m;count++);
%o q2=vector(n!);for(i=1,n!,m2=prod(j=1,i,q[j]);for(i=1,n!,if(q[i]==m2,a2=i));q2[a2]++ );
%o a3=0;for(i=1,n!,if(q2[i]>0,a3++));print(a3))
%K nonn,more
%O 1,2
%A _Timothy Foo_, Jul 26 2017
|
