Linear ordering of all subsets of size k I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into $\{1, \ldots, {n \choose k}\}$ that can be computed in $O(1)$ at best. 

The most trivial way for this would be to use a tree where each leaf node corresponds to such a subset but then I have to save the entire tree and each lookup will cost more than $O(1)$. We could also totally order those subsets such that $\{1, 2, 3\}$ would be the smallest subset for $k=3$ and $\{n, n-1, n-2\}$ the largest one and then use the number of smaller/equal subsets in this ordering as our index. I tried to come up with a closed form solution and it ended in some gnarly sums of binomial coefficients. 

So maybe there is a well known solution to this problem and somebody could give me a reference?
The bijection you are looking for is known as a combinatorial number system. A great further resource is Knuth's TAOCP.