1
$\begingroup$

Earlier I posted this question: Is there some standard name for this particular order of terms in an elementary symmetric polynomial?

This present question will further refine the definition of what I'm after.

  • $(A)$ Permutations of three members of $\{x_1,x_2,x_3,x_4\}$ in colexicographic order, i.e. like lexicographic order except by the last symbol rather than the first.
  • $(B)$ Permutations of three members of $\{x_1,x_2,x_3,x_4\}$ in a similar order that refuses to allow $x_4$ to appear until after all permutations not including $x_4$ are listed.
  • $(C)$ Combinations of three members of $\{x_1,x_2,x_3,x_4,x_5\}$ in colexicographic order. In this order, $x_4$ cannot appear until after all combinations of $\{x_1,x_2,x_3\}$ are listed; $x_5$ cannot appear until all combinations of $\{x_1,x_2,x_3,x_4\}$ are listed, and so on.

\begin{align} & (A) & & (B) & & (C)\\ \hline & x_3 x_2 x_1 & & x_3 x_2 x_1 & & x_1 x_2 x_3 \\ {} + {} & x_4 x_2 x_1 & {}+{} & x_2 x_3 x_1 & {}+{} & x_1 x_2 x_4 \\ {} + {} & x_2 x_3 x_1 & {}+{} & x_3 x_1 x_2 & {}+{} & x_1 x_3 x_4 \\ {} + {} & x_4 x_3 x_1 & {}+{} & x_1 x_3 x_2 & {}+{} & x_2 x_3 x_4 \\ {} + {} & x_2 x_4 x_1 & {}+{} & x_2 x_1 x_3 & {}+{} & x_1 x_2 x_5 \\ {} + {} & x_3 x_4 x_1 & {}+{} & x_1 x_2 x_3 & {}+{} & x_1 x_3 x_5 \\ {} + {} & x_3 x_1 x_2 & {}+{} & x_2 x_1 x_4 & {}+{} & x_1 x_4 x_5 \\ {} + {} & \cdots \cdots & {}+{} & \cdots\cdots & {}+{} & x_2 x_3 x_5 \\ \vdots\,\,\, & & \vdots\,\,\, & & \vdots\,\,\, \\ \vdots\,\,\, & & \vdots\,\,\, \end{align} In $(A)$, if we were to extend the set of objects being permuted by the addition of one element $x_5,$ to $\{x_1,x_2,x_3,x_4,x_5\},$ then $x_5 x_2 x_1$ would appear before $x_3 x_1 x_2,$ so we would not merely add more elements at the end of the list.

By contrast, in $(B)$ and $(C),$ adding another variable would only add new members that come after those already listed.

Thus colexicographic order does not satisfy that desideratum with permutations, although it does with combinations.

So my present question is: Is there a conventional name for orders that satisfy that desideratum, and in particular for the one in $(C)\text{?}$

I include plus signs because ultimately I will want to allow the variables to have numerical values and I will consider rearrangements of infinite series. With the order $(A),$ if we went on to infinitely many variables, then these would be densely ordered in colexicographic order, whereas I want each term to have just finitely many predecessors, as would happen in $(C)$. Or in $(B)$ for that matter, but for now I am not considering non-commutative multiplications.

$\endgroup$
1
+50
$\begingroup$

If I understand the question correctly, you might find useful the ordering of $k$-subsets of an $n$-set called "revolving door order" in the book Combinatorial Algorithms (pdf link) by Nijenhuis & Wilf. I don't think it's exactly the same as what you're looking for, but it does have the property that all the combinations containing $j$ as the largest element are listed before any combinations containing $j+1$.

They demonstrate an algorithm for generating such subsets (NXKRSD) and provide this sample output for generating subsets of size 4 from the set $\{1,2,\ldots, 7\}$ (pg. 36 in the pdf link, any transcription errors are mine):

1 2 3 4
1 2 4 5
2 3 4 5
1 3 4 5
1 2 3 5
1 2 5 6
2 3 5 6
1 3 5 6
3 4 5 6
2 4 5 6
1 4 5 6
1 2 4 6
2 3 4 6
1 3 4 6
1 2 3 6
1 2 6 7
2 3 6 7
1 3 6 7
3 4 6 7
2 4 6 7
1 4 6 7
4 5 6 7
3 5 6 7
2 5 6 7
1 5 6 7
1 2 5 7
2 3 5 7
1 3 5 7
3 4 5 7
2 4 5 7
1 4 5 7
1 2 4 7
2 3 4 7
1 3 4 7
1 2 3 7

I believe the name "revolving door" comes from the fact that each combination is produced from the previous one by removing one element and adding one other.

$\endgroup$
6
  • $\begingroup$ "it does have the property that all the combinations containing $j$ as the largest element are listed before any combinations containing $j+1.$" However, it puts $1,2,6,7$ before $2,3,6,7$, so that doesn't apply to second-largest digits. That's not crucial as for my purpose, but it better than not having that property. $\endgroup$ Jul 5 '17 at 17:31
  • $\begingroup$ @MichaelHardy Yes, that's true. Also, that property appears to be a coincidental side-effect of the generation algorithm and not intrinsic to being "revolving door" (which is more about the kinds of allowed deltas between successive subsets), so it's not really an ideal descriptor for your case. $\endgroup$
    – mhum
    Jul 5 '17 at 17:49
  • $\begingroup$ @MichaelHardy Hang on. How does your ordering in column C) differ from the colexicographic ordering (e.g.: as described here)? $\endgroup$
    – mhum
    Jul 5 '17 at 21:21
  • $\begingroup$ As I said, "colexicographic order does not satisfy that desideratum with permutations, although it does with combinations." Thus an order of the sort I want coincides with colexicographic order when combinations of the same size are listed, but not when permutations are listed. $\endgroup$ Jul 5 '17 at 21:48
  • $\begingroup$ @MichaelHardy Oh! I see. I think I misunderstood the question. It seems that you're looking for a term that's more generically applicable to a bunch of different orders. $\endgroup$
    – mhum
    Jul 5 '17 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.