At a fixed positive integer level , the combinatorial number system writes each positive integer uniquely asChoose as large as possible with , subtract that term and repeat at level , stopping when the remainder is zero. For example, at level three,Pascal's identity gives , so the remainder after choosing the level- term is smaller than . The next top index is consequently strictly smaller. Hockey-stick identity also bounds the sum of all lower admissible terms by . Thus those terms cannot replace a larger level- choice, proving uniqueness. The zero integer has the empty representation. This correspondence is useful for ranking and unranking fixed-size subsets.
Ranking assigns each object in a finite ordered combinatorial family its zero-based position, giving a bijection with consecutive nonnegative integers. Its inverse is unranking. For an -element subset of , its rank in colexicographic order isThis is the combinatorial number system, with when . All ranks from to occur exactly once.
For two-element subsets, colexicographic order begins . Their ranks are . In particular, has rank . The binomial sum counts all preceding subsets by the largest element where they differ. Ranking turns structured objects into compact array indices and permits uniform sampling by drawing a uniform rank and applying unranking.
