[Math] Reverse Lexicographic Order

combinatorics

Find the 233rd subset of [12] with five elements in reverse lexicographic
order.

I am a little confused with the difference between normal and reverse lexicographic order. I think I understand that in lexicographic order. The first few subsets would look like this: {1,2,3,4,5},{1,2,3,4,6},…,{1,2,3,4,12},{1,2,3,5,6}, and so on.

In reverse lexicographic order, would the first few subsets simply be {5,4,3,2,1},{6,4,3,2,1},…,{12,4,3,2,1},{6,5,3,2,1}? i.e. the same only read from right to left.

(Aside) So then, since there are ${12 \choose 5}$=792 subsets of size 5, the 233rd subset in reverse lexicographic order would be equal to the 559th subset in normal lexicographic order?

Best Answer

What Frentos wrote in the comments is incorrect. The reverse lexicographical order on subsets of $[12]$ with five elements is found by pretending that $12<11<10<\ldots<3<2<1$ and using the resulting lexicographical order. Thus, the first two are indeed $\{12,11,10,9,8\}$ and $\{12,11,10,9,7\}$, but the next one after that is $\{12,11,10,8,7\}$, not $\{12,11,10,9,6\}$.

This means that your aside is not correct. It would be almost correct if you were talking about the reflected lexicographic order, which is simply the reversal of the usual lexicographic order: it would be off by one, since the $233$-rd element from the end of the lexicographical order is the $(79\color{red}3-233)$-rd, or $560$-th element, not the $559$-th element. Here’s a HINT for the correct approach: if $a<b<c<d<e$, compare the position of $\{a,b,c,d,e\}$ in the lexicographic order with the position of $\{13-a,13-b,13-c,13-d,13-e\}$ in the reverse lexicographic order.