# A positional number system for enumerating fixed-size subsets?

Many combinatorial objects have some associated positional number system. For example, the subsets of a (finite) set S can be listed off by observing the bits of all $|S|$-bit numbers, treating the 1s and 0s as indicators for whether to pick a particular element or not. Permutations of a finite set S can be found by examining the factoradic representations of the first $|S|!$ natural numbers.

Is there an analogous positional number system for encoding k-element subsets of an n-element set?

Thanks!

• Try combinadic – Henry Jan 10 '12 at 8:27
• @Henry- This looks great, but it looks like it's not a positional system in the sense that binary or factoradic numbers are. You should definitely promote this to an answer, though. – templatetypedef Jan 10 '12 at 8:31

The combinatorial number system that Henry already linked to is the best you can ask for. Asking for it to be a positional number system is contradictory to your requirement that only fixed size subsets are encoded. In a positional number system any string of legal digits can occur (corresponds to a different number), including those with repeated digits that you don't want to consider. You could of course take your $n$-bit numbers and consider only those with exactly $k$ bits equal to $1$, but that would have the same problem that lots of digit-sequences do no correspond to an appropriate subset.
An indirect encoding in which the digit string has to undergo further processing in order to be turned into a $k$-combination can be defined, but is not satisfactory. As an extreme case you could take ordinary decimal notation, and use the numeric value to look up a combination in a (lexicographic) list of all $k$-combinations; that does not seem to be what you are asking for. Note that even the factorial number system does not directly encode permutations, but just their Lehmer code; converting from these to permutations is quite straightforward, but not even computationally easy (i.e., doable in $O(n)$ time for permutations of $n$) using any simple data structure.