The combinations $\sigma$ of $K$ elements of a set of size $N$ can be ordered lexicographically $\,(<_{\text{lex}})\,$ such that we have
$$\forall\left(i,j\in\left[1,i_{\text{max}}\right]\right)\,.\,\left((i<_{\mathbb{N}}j)\;\Leftrightarrow\;(\sigma_i<_{\text{lex}}\sigma_j)\right)$$
Instead of taking the $K$ elements that are removed, we could also take the $N-K$ elements that stay and then swap both sets:
$$\left\{\left(\sigma_{N\text{ choose }K}\right)_i\,|\,i\in[1,i_{\text{max}}]\right\} = \left\{\complement\left(\left(\sigma_{N\text{ choose }N-K}\right)_i\right)\,|\,i\in[1,i_{\text{max}}]\right\}$$
where swapping means taking the set-complement $\complement$ w.r.t. $\{1...N\}$.
E.g., for $N=5$ and $K=2$ we have $i_{\text{max}}={N\choose K}={5\choose 2}=10$ combinations
$$\begin{array}{|c|c|c|c|c|c|} \hline i & (σ_{N\text{ choose }K})_i & \text{bits} & j & (σ_{N\text{ choose }N-K})_j & \text{bits}\\ \hline 1 & (1, 2) & 00011 & 10 & (3, 4, 5) & 11100 \\ 2 & (1, 3) & 00101 & 9 & (2, 4, 5) & 11010 \\ 3 & (1, 4) & 01001 & 8 & (2, 3, 5) & 10110 \\ 4 & (1, 5) & 10001 & 7 & (2, 3, 4) & 01110 \\ 5 & (2, 3) & 00110 & 6 & (1, 4, 5) & 11001 \\ 6 & (2, 4) & 01010 & 5 & (1, 3, 5) & 10101 \\ 7 & (2, 5) & 10010 & 4 & (1, 3, 4) & 01101 \\ 8 & (3, 4) & 01100 & 3 & (1, 2, 5) & 10011 \\ 9 & (3, 5) & 10100 & 2 & (1, 2, 4) & 01011 \\ 10 & (4, 5) & 11000 & 1 & (1, 2, 3) & 00111 \\ \hline \end{array}$$
Now, one can observe that this seems to establish a direct one-to-one correspondence in the following way:
$$(\text{Thesis})\quad\forall(i\in[1,i_{\text{max}}])\,.\,\left(\sigma_{{N\text{ choose }K},\,(<_{\text{lex}})}\right)_i=\complement\left(\left(\sigma_{{N\text{ choose }N-K},\,(>_{\text{lex}})}\right)_i\right)$$
where $(>_{\text{lex}})$ is the reverse-lexicographic order. I.e.,
- the lexicographically-$i$-th combination of choosing $K$ elements out of $N$
is the same as
- the set-complement $\complement$ of the reverse-lexicographically-$i$-th combination of choosing $N-K$ elements out of $N$
My question: Is that thesis true and how would one proof this for all $N$ and $K$?
The combinations $\sigma_i$ can be generated by decomposing $i$ according to a combinatorial number system (Buckles' so-called "Algorithm 515"), and I've tested this for all $1\leq N \leq 20$ and $0 \leq K \leq N$. I would start dissecting the algorithm to proof that both computations lead to the same result; but there might be a more direct proof for this property. (therefore the question)
Update
My proof attempt so far:
For two combinations $\sigma$ and $\tau$ of $K$ elements of a set of size $N$, one might demonstrate for the lexicographic order $(<_{\text{lex}})$ that
$$(\sigma <_{\text{lex}} \tau)\;\Leftrightarrow\; \exists i\,.\,\left(\sigma[j]=\tau[j]\text{ for }j<i\right)\text{ and }\left(\sigma[i]<_{\mathbb{N}}\tau[i]\right)$$
I.e., $\sigma$ is lexicographically smaller than $\tau$, iff $\sigma$ and $\tau$ share a same prefix after that they differ.
Then, one might argue that for this particular $\sigma[i] =: s$
$$(\sigma <_{\text{lex}} \tau)\;\Leftrightarrow \;\exists(s\in\sigma)\,\forall(t\in\tau)\,.\,\text{either }(t\in\sigma)\text{ or }(s<_{\mathbb{N}}t)$$
I.e., $(\sigma <_{\text{lex}} \tau)$, iff each element of $\tau$ is either in $\sigma$ or it is greater than $\sigma[i]$.
Or, formulated differently: $(\sigma <_{\text{lex}} \tau$), iff $\sigma$ contains the smallest element $\sigma[i]$ that is not shared by both of them:
$$(\sigma <_{\text{lex}} \tau)\;\Leftrightarrow\;\min(\sigma \text{ "xor" } \tau)\in\sigma$$
In particular $\sigma[i]\notin\tau$ in that case. We also have $$(\sigma[i]\notin\tau)\;\Leftrightarrow\;(\sigma[i]\in\complement(\tau))$$
because the complement $\complement(\tau)$ of $\tau$ contains all elements that are not contained in $\tau$ w.r.t. $\{1..N\}$.
That means, that the situation is "reversed" for $\complement(\sigma)$ and $\complement(\tau)$. With the help of
$$(\sigma\text{ "xor" }\tau)=(\complement(\sigma)\text{ "xor" }\complement(\tau))$$
we shoud arrive at
$$(\sigma <_{\text{lex}} \tau)\;\Leftrightarrow\;\min(\sigma \text{ "xor" } \tau)\in\sigma\;\Leftrightarrow\;\min(\complement(\sigma) \text{ "xor" } \complement(\tau))\in\complement(\tau)\;\Leftrightarrow\;(\complement(\sigma) >_{\text{lex}} \complement(\tau))$$
And this should conclude, that the $i$-th element in a set of $\sigma$s, ordered by $(<_{\text{lex}})$ corresponds to the $i$-th element in a set of $\complement(\sigma)$s, ordered by $(>_{\text{lex}})$.
Are there any flaws or too-great holes in this proof attempt?