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?


1 Answer 1


The bijection you are looking for is known as a combinatorial number system. A great further resource is Knuth's TAOCP.

  • $\begingroup$ Thank's a lot, that is exactly what I was looking for. $\endgroup$
    – Maximal
    Nov 30, 2018 at 14:49
  • $\begingroup$ @Maximal You're welcome, and welcome to the site! $\endgroup$
    – Juho
    Nov 30, 2018 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.