= Combinatorial number system
{title2=$m=\sum_{j=s}^r\binom{a_j}j$}
{wiki}
= Binomial representation
{synonym}
At a fixed positive <integer> level $r$, the <combinatorial number system> writes each positive <integer> $m$ uniquely as
$$
m=\binom{a_r}r+\binom{a_{r-1}}{r-1}+\cdots+\binom{a_s}s,
\qquad a_r>a_{r-1}>\cdots>a_s\geq s\geq1.
$$
Choose $a_r$ as large as possible with $\binom{a_r}r\leq m$, subtract that term and repeat at level $r-1$, stopping when the remainder is zero. For example, at level three,
$$
23=\binom63+\binom32=20+3.
$$
<Pascal's identity> gives $\binom{a+1}j-\binom aj=\binom a{j-1}$, so the remainder after choosing the level-$j$ term is smaller than $\binom a{j-1}$. The next top index is consequently strictly smaller. <Hockey-stick identity> also bounds the sum of all lower admissible terms by $\binom a{j-1}-1$. Thus those terms cannot replace a larger level-$j$ choice, proving uniqueness. The zero <integer> has the empty representation. This correspondence is useful for <ranking> and <unranking> fixed-size <subsets>.
Back to article page
