Cumulative Permutation Sequences

Let  p1, p2, ...,pk  (where k = n!) denote the permutations of n 
elements, and let "*" denote composition.  (For example, pi*pj 
signifies the permutation given by first applying pj, and then 
applying pi.)  Of course, the n! permutations can be ordered in 
(n!)! different ways.  For any given "p-ordering", my question 
concerns the permutations

                      s1 = p1
                      s2 = p2*p1
                      s3 = p3*p2*p1
                      s4 = p4*p3*p2*p1


In general I think the list of permutations s1 through sk may 
contain duplicates, so it doesn't contain all n! permutations.  
For example, with n=5 and an arbitrarily chosen ordering g, the 
number of distinct permutations in the list of s1 through sk 
seems to be in the range from about 62 to 87 (out of 120 total).  
For any given ordering g, let v(g) denote the number of distinct 
permutations in the list s1 to sk.  

QUESTION:  What is the distribution of v(g) over all (n!)! orderings?
           In particular, what are the min and max values of v(g)?

If the sequence of compositions is continued by wrapping around the 
indicies of the permutations, i.e., identifying p[k+1] with p1, and 
p[k+2] with p2, and so on, then the s-list may or may not eventually 
include all n! permutations.  Taking n=5 again, I have found orderings 
such that the 120th distinct permutation finally appears at s[533].  
I've also found orderings where it appears as early as s[408].

Moreover, there are p-orderings which (evidently) never yield all 120
permutations.  For example, I have found p-orderings such that the 
infinite list s1, s2, ... seems to contain only 106 of the 120 
possible permutations.  Others give 111, or 117, etc.

QUESTIONS: -What fraction of all p-orderings give an s-list that 
            eventually includes all n! permutations?
           -What are the maximum and minimum possible periods for 
            an s-list?
           -What p-ordering gives the smallest set of distinct
            permutations on its infinite s-list? 

Return to MathPages Main Menu