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?


  • 1
    $\begingroup$ Try combinadic $\endgroup$ – Henry Jan 10 '12 at 8:27
  • $\begingroup$ @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. $\endgroup$ – 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.

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).

  • $\begingroup$ I'm not sure I see why you can't have a positional system. Factoradic is a positional system and it can have repeated digits in it. $\endgroup$ – templatetypedef Jan 10 '12 at 18:05
  • $\begingroup$ @templatetypedef: You want the "further processing" necessary to get from digits to your combination to be minimal, otherwise the numeral system has little to do with combinations. Even for factorial numbers to permutations the processing is non-negligible, but acceptable. For combinations, at the least the product of the bases used for the individual digits should give the binomial coefficient counting the combinations; however there is no obvious way to write a general binomial coefficient as a pure product, without division (contrary to factorials). $\endgroup$ – Marc van Leeuwen Jan 15 '12 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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