Monday 13 April 2020

Permutations of sequences

Imagine an infinite sequence of 3 objects, $A$, $B$, $C$, that has the following property:
For each permutation in the 3 objects $A$, $B$, $C$, if this permutation is applied to the sequence, the resulting sequence is a tail of the original sequence.
For example, if we have the sequence, $AABACBA...$, the permutations would be $BBABCAB...$, $CCBCABC...$, $BBCBACB...$, $AACABCA...$ and $CCACBAC...$ Each one of these must appear as a tail.
If you try this for a moment, you will soon discover that this is impossible. This is also quite easy to prove.
First off, the sequence must evidently contain all 3 objects, if not, the permutation that turns an object that is contained in an object that is not will not be displayed as any tail.
One can assume without loss of generality that the first element of the series is A. Now one can look at the permutations ABC->BCA and the permutations ABC->BAC. For each of these, a tail must exist, we can call the tails indices x and y. Because these elements are each the first element of there tail, they both have to be B (as both permutations project A to B). But if we look at element x+y, this element is both the x-th element of the "y" tail, as the y-th element of the "x" tail. So this element would have to be C, as well as A, which leads to a contradiction. Therefore such a sequence cannot exist.
If one considers a subset of permutations that are allowed, and generalise this to sequences with more possible elements, one can easily prove that a valid sequence exists if and only if the subset of permutations forms a cyclic group. The proof of this is left as an exercise to the reader.