A290024 Number of permutations in S_n that are factorials of permutations in lexicographic order.

1, 1, 2, 4, 15, 72, 425, 3038, 24538, 221220, 2221701

Offset

0,3

Comments

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!}|.

This is an S_n analog of the problem studied in the references section.

References

B. Rokowska and A. Schinzel, Sur un problème de M. Erdős, Elem. Math., 15:84-85, 1960.

Links

Table of n, a(n) for n=0..10.

W. D. Banks, F. Luca, I. E. Shparlinski, and H. Stichtenoth, On the Value Set of n! Modulo a Prime, Turk. J. Math., 29, (2005), 169-174.

T. Trudgian, There are no socialist primes less than 10^9, INTEGERS, 14 (2014), A63.

Prog

(PARI)
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);
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;
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]);
m=matrix(n, n); for(i=1, n, m[v[i], i]=1); q[count+2]=m; count++);
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]++ );
a3=0; for(i=1, n!, if(q2[i]>0, a3++)); print(a3))

Crossrefs

Sequence in context: A316661 A014517 A020110 * A292757 A182449 A140836

Adjacent sequences: A290021 A290022 A290023 * A290025 A290026 A290027

Keyword

nonn,more

Author

Timothy Foo, Jul 26 2017

Extensions

a(0) and a(8)-a(10) from Pontus von Brömssen, Apr 29 2025

Status

approved