Skip to main content
MathOverflow

Return to Answer

A little bit less verbose
Source Link
Zach Teitler
Zach Teitler
  • 6.2k
  • 3
  • 33
  • 63

In the comments it'sAs noted that the indices, as defined, don't give a good (stable) correspondence between non-negative integers and permutations. Specifically, left-padding with zeros in the factoradic expansion of an integer changes the corresponding permutation.

To be more verbose than comments allowed, there are really two steps in this process. First, going from a (non-negative) integer to a factoradic expansion is ambiguous because there might or might not beproblems with adding leading zeros: to an index $1$ can be(indices $10_!$$10$, $010_!$$010$, $0010_!$, etc. Second, going from a factoradic string$0010$ correspond to a permutation is fine, except that the leading zeros make a difference:different permutations $10 \to 21$$21$, $010 \to 132$$132$, $0010 \to 1243$, etc. The usual embeddings of symmetric groups$1243$) or conversely, putting $S_n$ into $S_{n+1}$ asadding fixed points to the permutationsend of a permutation $1,\dotsc,n$, leaving(permutations $n+1$ fixed$21$, don't identify these permutations. Instead$213$, $21 \in S_2$$2134$–which would all be identified with $213 \in S_3$ and with $2134 \in S_4$. In a sensedescribed by the correspondence from non-negative integers to permutations is not "stable" in that adding leading zeros doesn't correspond to these embeddings. Converselysame cycle, the permutation $21$ has index$(1,2)$–have indices $10_! = 1$$10$, the permutation $213$ has index $100_! = 2$$100$, $2134$ has index $1000_! = 6$, etc$1000$).

On further reflection it's not that bad ofLet's define a problem. We just have to change the correspondences to go the other way."stable index" (Get it? Further reflection? Pun intended.)

Far be it from me to change other peoples's definition of index! So I here propose a definitionbasically using reverse-lexicographic order instead of "stable index"lexicographic order). Given a permutation $\pi=(p_0,\dotsc,p_{n-1})$, define a list $(a_0,\dotsc,a_{n-1})$ by settingfor 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$: $$ a_k = \#\{j : 0 \leq j \leq k-1, p_j > p_k \}. $$ So $a_k = 0$ if $p_k$ is the greatest element in $\{p_0,\dotsc,p_k\}$, or $a_k=k$ if $p_k$ is the smallest. Note that each $0 \leq a_k \leq k$. So the stringlist $(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!$.

\begin{array}{lll} \pi & (a_0,\dotsc,a_n) & s(\pi) & \pi \\ \hline 21 & (0,1) & 1 & (12) \\ 213 & (0,1,0) & 1 & (12) \\ 2134 & (0,1,0,0) & 1 & (12) \\ 2134\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}\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}

I think this gives an answer toanswers the last question. This assigns by assigning a "stable index" to every permutation of the positive integers that only moves finitely many integers. The group of these permutations is called the infinite permutation group. I hope some expert will step in;integers; let's call these "finite permutations" to suggest that their support (set of elements that move) is finite. Then composition and inversion of finite permutations correspond to operations on non-negative integers. What operations are they? I don't know but I would love to find out.

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). Presumably it must have some advantage. Knowing more about the composition and inversion operators might clarify when this system is advantageous.

For the first question, there's the naive approach, like you saydescribed (convert stable indices to one-line notation, compose using known methods, get the stable index of the result). It's not the case that the stable index doesn't contain enough information. But canI would guess that it can be done more quickly and directly? Surely the answer is yes! What a fun project but I would have to find outthink about how.

  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$?)

Even if some of these are of dubious importanceThis might all be well-known. I guess the stable index is basically just a bijection for the way that (square$q$-indexedfactorials count the permutations?), I think they would still be fun to figure out with a given inversion number. So perhaps it's an exercise in a combinatorics textbook or something.

In the comments it's noted that the indices, as defined, don't give a good (stable) correspondence between non-negative integers and permutations. Specifically, left-padding with zeros in the factoradic expansion of an integer changes the corresponding permutation.

To be more verbose than comments allowed, there are really two steps in this process. First, going from a (non-negative) integer to a factoradic expansion is ambiguous because there might or might not be leading zeros: $1$ can be $10_!$, $010_!$, $0010_!$, etc. Second, going from a factoradic string to a permutation is fine, except that the leading zeros make a difference: $10 \to 21$, $010 \to 132$, $0010 \to 1243$, etc. The usual embeddings of symmetric groups, putting $S_n$ into $S_{n+1}$ as the permutations of $1,\dotsc,n$, leaving $n+1$ fixed, don't identify these permutations. Instead, $21 \in S_2$ would be identified with $213 \in S_3$ and with $2134 \in S_4$. In a sense the correspondence from non-negative integers to permutations is not "stable" in that adding leading zeros doesn't correspond to these embeddings. Conversely, the permutation $21$ has index $10_! = 1$, the permutation $213$ has index $100_! = 2$, $2134$ has index $1000_! = 6$, etc.

On further reflection it's not that bad of a problem. We just have to change the correspondences to go the other way. (Get it? Further reflection? Pun intended.)

Far be it from me to change other peoples's definition of index! So I here propose a definition of "stable index". Given a permutation $\pi=(p_0,\dotsc,p_{n-1})$, define a list $(a_0,\dotsc,a_{n-1})$ by setting each $a_k$ to be the number of $\{p_0,\dotsc,p_{k-1}\}$ that are strictly greater than $p_k$: $$ a_k = \#\{j : 0 \leq j \leq k-1, p_j > p_k \}. $$ So $a_k = 0$ if $p_k$ is the greatest element in $\{p_0,\dotsc,p_k\}$, or $a_k=k$ if $p_k$ is the smallest. Note that each $0 \leq a_k \leq k$. So the string $(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!$.

\begin{array}{lll} \pi & (a_0,\dotsc,a_n) & s(\pi) & \pi \\ \hline 21 & (0,1) & 1 & (12) \\ 213 & (0,1,0) & 1 & (12) \\ 2134 & (0,1,0,0) & 1 & (12) \\ 2134\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}

I think this gives an answer to the last question. This assigns a "stable index" to every permutation of the positive integers that only moves finitely many integers. The group of these permutations is called the infinite permutation group. I hope some expert will step in; let's call these "finite permutations" to suggest that their support (set of elements that move) is finite. Then composition and inversion of finite permutations correspond to operations on non-negative integers. What operations are they? I don't know but I would love to find out.

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). Presumably it must have some advantage. Knowing more about the composition and inversion operators might clarify when this system is advantageous.

For the first question, there's the naive approach, like you say (convert stable indices to one-line notation, compose using known methods, get the stable index of the result). It's not the case that the stable index doesn't contain enough information. But can it be done more quickly and directly? Surely the answer is yes! What a fun project to find out.

  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?

Even if some of these are of dubious importance (square-indexed permutations?), I think they would still be fun to figure out.

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

\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}

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.

  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.

Source Link
Zach Teitler
Zach Teitler
  • 6.2k
  • 3
  • 33
  • 63

In the comments it's noted that the indices, as defined, don't give a good (stable) correspondence between non-negative integers and permutations. Specifically, left-padding with zeros in the factoradic expansion of an integer changes the corresponding permutation.

To be more verbose than comments allowed, there are really two steps in this process. First, going from a (non-negative) integer to a factoradic expansion is ambiguous because there might or might not be leading zeros: $1$ can be $10_!$, $010_!$, $0010_!$, etc. Second, going from a factoradic string to a permutation is fine, except that the leading zeros make a difference: $10 \to 21$, $010 \to 132$, $0010 \to 1243$, etc. The usual embeddings of symmetric groups, putting $S_n$ into $S_{n+1}$ as the permutations of $1,\dotsc,n$, leaving $n+1$ fixed, don't identify these permutations. Instead, $21 \in S_2$ would be identified with $213 \in S_3$ and with $2134 \in S_4$. In a sense the correspondence from non-negative integers to permutations is not "stable" in that adding leading zeros doesn't correspond to these embeddings. Conversely, the permutation $21$ has index $10_! = 1$, the permutation $213$ has index $100_! = 2$, $2134$ has index $1000_! = 6$, etc.

On further reflection it's not that bad of a problem. We just have to change the correspondences to go the other way. (Get it? Further reflection? Pun intended.)

Far be it from me to change other peoples's definition of index! So I here propose a definition of "stable index". Given a permutation $\pi=(p_0,\dotsc,p_{n-1})$, define a list $(a_0,\dotsc,a_{n-1})$ by setting each $a_k$ to be the number of $\{p_0,\dotsc,p_{k-1}\}$ that are strictly greater than $p_k$: $$ a_k = \#\{j : 0 \leq j \leq k-1, p_j > p_k \}. $$ So $a_k = 0$ if $p_k$ is the greatest element in $\{p_0,\dotsc,p_k\}$, or $a_k=k$ if $p_k$ is the smallest. Note that each $0 \leq a_k \leq k$. So the string $(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) \\ 2134 & (0,1,0,0) & 1 & (12) \\ 2134\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 gives an answer to the last question. This assigns a "stable index" to every permutation of the positive integers that only moves finitely many integers. The group of these permutations is called the infinite permutation group. I hope some expert will step in; let's call these "finite permutations" to suggest that their support (set of elements that move) is finite. Then composition and inversion of finite permutations correspond to operations on non-negative integers. What operations are they? I don't know but I would love to find out.

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). Presumably it must have some advantage. Knowing more about the composition and inversion operators might clarify when this system is advantageous.

For the first question, there's the naive approach, like you say (convert stable indices to one-line notation, compose using known methods, get the stable index of the result). It's not the case that the stable index doesn't contain enough information. But can it be done more quickly and directly? Surely the answer is yes! What a fun project to find out.

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?

Even if some of these are of dubious importance (square-indexed permutations?), I think they would still be fun to figure out.