I have a list of combinations resulting from n choose r where order doesn't matter and without repeats, and the list is ordered based on the first choice. To make this concrete, in my specific case, it's 6 choose 2, so the list is as follows:
(1,2)
(1,3)
...
(1,6)
(2,3)
(2,4)
(2,5)
(2,6)
(3,4)
...
(5,6)
for a total of 15 combinations. If I give you both choices, what is the closed form solution for it's position in this list? For example, the outputs from the closed form solution for some sample inputs would be as follows:
i.e. (1,6) -> 5, (2,3) -> 6, (3,5) -> 11
I feel like there must be a closed form solution to this involving factorials, but I can't seem to figure it out, and it's actually relevant for my work. Wasn't sure what exact search terms to use for this, so let me know if there's an answer out there already.
You want a formula for the index of $\{x_1,\dots,x_r\}$ in the list of all subsets of $\{1,\dots,n\}$ of size $r$. Assuming the items are written in increasing order, as $x_1<x_2<\dots<x_r$, the index is $$ \binom{n}r-\left[\binom{n-x_r}{1}+\binom{n-x_{r-1}}2+\dots+\binom{n-x_1}{r}\right] $$ In your case, where $n=6$ and $r=2$, the index of $\{a,b\}$ works out to be $$ \binom{6}2-\left[\binom{n-b}{1}+\binom{n-a}2\right]=15-(6-b)-\frac{(6-a)(5-a)}{2} $$ For example, the rank of $\{1,2\}$ would be $15-\binom{4}1-\binom{5}2=1$. So far, so good.
The rank of $\{1,6\}$ is $15-\binom01-\binom52=5.$
The rank of $\{2,3\}$ is $15-\binom{3}1-\binom{4}2=6$.
The rank of $\{3,5\}$ is $15-\binom{1}1-\binom{3}2=11$.
In case you are wondering where the formula comes from, I adapted the formula from combinadics. In combinadics, the index of $\{x_1,x_2,\dots,x_r\}$ in the list of all subsets of $\{0,1,\dots,n-1\}$ is $$ \binom{x_1}1+\binom{x_2}2+\dots+\binom{x_r}{r} $$ However, this produces a different ordering than the one you specified. Your ordering is lexicographic, while the combinadic ordering is reverse co-lexicographic.