A positional number system for enumerating fixed-size subsets?

Solution 1:

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.

If you want to learn all about such stuff, and lots more, read volume 4A of Knuth's Art of Computer programming (and do all the exercises).