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
etc
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