Reverse Lexicographic Order

Question

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?

Answer 1

It seems to depend on the author quite heavily what reverse lexicographic order actually means. In Peter Cameron's Combinatorics, reverse lexicographic is simply lexicographic order, but with the word written backwards (reversed internal order). However, oeis says that reverse lexicographic order is the lexicographic list written backwards (reversed external order). What the question means by reverse lexicographic order will decide how to actually answer the question.

Answer 2

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.