Given the index of two permutations, Is there a direct way to compute the index of their composition? [closed]

Question

Suppose you are given two indexed permutations, (7 followed by 4, for instance)

1. What is the best way to go about finding their composition, given the indices themselves? I'd imagine that the answer would involve converting the indices to some cycle form, performing the necessary computation then finding the index of the resulting permutation. Does there exist a more concise method to compose two arbitrary permutations, or does the index not inherently contain enough information?
2. Can this information be used to study permutation groups (like $S_{4}$ or $M_{24}$ etc.), or is the index missing important details? Like the permutation's conjugacy class?
3. Can this operation be extended to apply to any two whole numbers? i.e. Can there exist an infinite group of permutations, applicable as a noncommutative binary operation over $\mathbb N_{0}$?

Answer 1

As noted in the comments, there are problems with adding leading zeros to an index (indices $10$, $010$, $0010$ correspond to different permutations $21$, $132$, $1243$) or conversely, adding fixed points to the end of a permutation (permutations $21$, $213$, $2134$–which would all be described by the same cycle, $(1,2)$–have indices $10$, $100$, $1000$).

Let's define a "stable index" (basically using reverse-lexicographic order instead of lexicographic order). Given a permutation $\pi=(p_0,\dotsc,p_{n-1})$, for each $k=0,\dotsc,n-1$ define $a_k$ to be the number of $\{p_0,\dotsc,p_{k-1}\}$ that are strictly greater than $p_k$. Note that each $0 \leq a_k \leq k$. So the list $(a_0,\dotsc,a_{n-1})$, or rather its reversal $(a_{n-1},\dotsc,a_0)$, is a valid factoradic expansion. Finally the stable index is $s(\pi) = (a_{n-1},\dotsc,a_0)_! = \sum a_k k!$.

Here are some examples (permutations written in compressed one-line notation first, then in cycle notation at the end):

\begin{array}{lll} \pi & (a_0,\dotsc,a_n) & s(\pi) & \pi \\ \hline 21 & (0,1) & 1 & (12) \\ 213 & (0,1,0) & 1 & (12) \\ 213\dotsc n & (0,1,0,\dotsc,0) & 1 & (12) \\ 132 & (0,0,1) & 2 & (23) \\ 1324\dotsc n & (0,0,1,0,\dotsc,0) & 2 & (23) \\ 312 & (0,1,1) & 3 & (132) \\ 231 & (0,0,2) & 4 & (123) \\ 2143 & (0,1,0,1) & 7 & (12)(34) \\ \operatorname{id} & (0,\dotsc,0) & 0 & (1) \\ \end{array}

Let's find $7$ followed by $4$. This is the permutation $(123) \circ (12)(34) = (134)$ or $3241$ in one-line notation. We find $(a_0,a_1,a_2,a_3) = (0,1,0,3)$, so the stable index is $3010_! = 19$.

I think this answers the last question by assigning a "stable index" to every permutation of the positive integers that only moves finitely many integers; let's call these "finite permutations". Then composition and inversion of finite permutations correspond to operations on non-negative integers.

To answer the second question, it could be used to study finite permutation groups. The stable index isn't missing any information, except perhaps which finite permutation group the permutation is supposed to be in, i.e., the number of fixed points of the permutation. It certainly captures the cycle type, in fact the (non-trivial) cycles. But on the other hand, I don't know what advantages it has over other notations for permutations (one-line, cycles, permutation matrices, etc).

For the first question, there's the approach you described (convert stable indices to one-line notation, compose, get the stable index of the result). It's not the case that the stable index doesn't contain enough information. I would guess that it can be done more directly but I would have to think about how.

There are many questions, of course most of them probably wildly unnatural:

1. Which finite permutations correspond to stable indices that are primes, perfect squares, etc?
2. Which stable indices correspond to finite permutations that are transpositions, $k$-cycles, even, etc?
3. What operations on integers correspond to the permutation operations of composition and inversion (your question), reversal, conjugation, etc.?
4. What operations on finite permutations correspond to the integer operations of incrementation, addition, multiplication, etc.? What about divisibility?
5. How do permutation statistics such as sign, inversions, descents, etc., relate to the index? (For example, the number of inversions is equal to the sum of the factoradic digits, $\sum a_k$.)
6. What if we use falling factorials instead of factorials, or $q$-factorials, to get polynomial indices? (Evaluating at $q=1$ gives the above-defined index, evaluating at $q=0$ gives the number of inversions. What about at $q=-1$?)

This might all be well-known. I guess the stable index is basically just a bijection for the way that $q$-factorials count the permutations with a given inversion number. So perhaps it's an exercise in a combinatorics textbook or something.