The $\binom{5}{3}$ ($=10$) $\,\,3$-elements subsets of the set $\{1,2,3,4,5\}$ can be arranged in the following way, called lexicographic ordering:
$\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\},\{2,3,4\},\{2,3,5\},\{2,4,5\},\{3,4,5\}.$
The subset $\{1,3,5\}$ appears at the $5$th position of the ordering. There are $\binom{10}{4}$ $\,\,4$-element subsets of the set $\{1,2,\cdots,10\}$. What are the positions of the subsets $\{3,4,5,6\}$ and $\{3,5,7,9\}$ in the corresponding lexicographic ordering of the $4$-element subsets of $\{1,2,...,10\}$?
(Question 49 in Exercise 1, Principle and Techniques in Combinatorics by Chen Chuan-Chong, Koh Khee-Meng)
I attempted to solve this problem by listing the subsets according to the lexicographic order in the following way:
$\{1,2,3,4\}\longrightarrow\{1,2,3,10\} :7$
$\{1,2,4,5\}\longrightarrow\{1,2,4,10\} :6$
$\{1,2,5,6\}\longrightarrow\{1,2,5,10\} :5$
$\cdots\cdots$
Finally I got the answers $141$ and $161$.
My question: Is there any better way to solve this problem instead of listing?
Thanks!
Best regards, Michael
Observe that there are $\binom{9}{3}$ subsets with a $1$, since the remaining three numbers must be larger than $1.$ Similarly, there are $\binom{8}{3}$ subsets with a $2$ and no $1,$ since the remaining three numbers must be larger than $2.$ The least subset (wrt lexicographic ordering) with a $3$ but no $1$ or $2$ is $\{3,4,5,6\}$, so this must occupy position $\binom{9}{3}+\binom{8}{3}+1=141.$
The number of subsets with least digits $3$ and $4$ is $\binom{6}{2}$, so $\{3,5,6,7\}$ occupies place $140+\binom{6}{2}+1$; the number of subsets with least digits $3,5,6$ is $\binom{4}{1}$, so $\{3,5,7,8\}$ occupies place $140+\binom{6}{2}+\binom{4}{1}+1,$ which leaves $\{3,5,7,9\}$ in place $140+\binom{6}{2}+\binom{4}{1}+2=161.$
I'll readily admit that there's probably a better way to approach this, but this significantly cuts down the computation from your approach.