Skip to main content
added 879 characters in body
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

Let $N(n;a_1,\dots,a_k)$ where $0\leq a_1 < a_2 < \dots < a_k < n$ be the order number of $(a_1,\dots,a_k)$ as a combination from ($n$ choose $k$).

Since there are exactly $\binom{n-1}{k-1}$ combinations with $a_1 = 0$, we have a recurrence:

if $a_1 = 0$, then $$ N(n;a_1,\dots,a_k) = N(n-1;a_2-1,\dots,a_k-1)$$

if $a_1 > 0$, then $$N(n;a_1,\dots,a_k) = \binom{n-1}{k-1} + N(n-1;a_1-1,a_2-1,\dots,a_k-1).$$

with initial condition $N(n;)=0$ (i.e., when $k=0$) for any $n$.

For example, $$N(13;0,1,4) = N(12;0,3) = N(11;2) = \binom{10}{0} + N(10;1)$$ $$= \binom{10}{0} + N(10;1) = \binom{10}{0} + \binom{9}{0} + N(9;0)$$ $$=\binom{10}{0} + \binom{9}{0} + N(8;) = 1 + 1 + 0 = 2$$ as required.

UPDATE. In fact, there is a simpler way to enumerate combinations, using combinatorial number system of degree $k$. A $k$-combination $0\leq a_1 < a_2 < \dots < a_k < n$ here gets the order number: $$\binom{a_1}{1} + \binom{a_2}{2} + \dots + \binom{a_k}{k}.$$

The properties of combinatorial number system ensure that this representation is a bijective mapping between $k$-combinations of $n$ and the integers in the interval $[0,\tbinom{n}{k}-1]$. In particular, given an integer $m$ in this interval, its representation in the combinatorial number system of degree $k$: $$m = \binom{a_1}{1} + \binom{a_2}{2} + \dots + \binom{a_k}{k}$$ uniquely defines numbers $0\leq a_1 < a_2 < \dots < a_k < n$ (the last inequality follows from $m<\tbinom{n}{k}$), i.e., a $k$-combination of $n$.

Let $N(n;a_1,\dots,a_k)$ where $0\leq a_1 < a_2 < \dots < a_k < n$ be the order number of $(a_1,\dots,a_k)$ as a combination from ($n$ choose $k$).

Since there are exactly $\binom{n-1}{k-1}$ combinations with $a_1 = 0$, we have a recurrence:

if $a_1 = 0$, then $$ N(n;a_1,\dots,a_k) = N(n-1;a_2-1,\dots,a_k-1)$$

if $a_1 > 0$, then $$N(n;a_1,\dots,a_k) = \binom{n-1}{k-1} + N(n-1;a_1-1,a_2-1,\dots,a_k-1).$$

with initial condition $N(n;)=0$ (i.e., when $k=0$) for any $n$.

For example, $$N(13;0,1,4) = N(12;0,3) = N(11;2) = \binom{10}{0} + N(10;1)$$ $$= \binom{10}{0} + N(10;1) = \binom{10}{0} + \binom{9}{0} + N(9;0)$$ $$=\binom{10}{0} + \binom{9}{0} + N(8;) = 1 + 1 + 0 = 2$$ as required.

Let $N(n;a_1,\dots,a_k)$ where $0\leq a_1 < a_2 < \dots < a_k < n$ be the order number of $(a_1,\dots,a_k)$ as a combination from ($n$ choose $k$).

Since there are exactly $\binom{n-1}{k-1}$ combinations with $a_1 = 0$, we have a recurrence:

if $a_1 = 0$, then $$ N(n;a_1,\dots,a_k) = N(n-1;a_2-1,\dots,a_k-1)$$

if $a_1 > 0$, then $$N(n;a_1,\dots,a_k) = \binom{n-1}{k-1} + N(n-1;a_1-1,a_2-1,\dots,a_k-1).$$

with initial condition $N(n;)=0$ (i.e., when $k=0$) for any $n$.

For example, $$N(13;0,1,4) = N(12;0,3) = N(11;2) = \binom{10}{0} + N(10;1)$$ $$= \binom{10}{0} + N(10;1) = \binom{10}{0} + \binom{9}{0} + N(9;0)$$ $$=\binom{10}{0} + \binom{9}{0} + N(8;) = 1 + 1 + 0 = 2$$ as required.

UPDATE. In fact, there is a simpler way to enumerate combinations, using combinatorial number system of degree $k$. A $k$-combination $0\leq a_1 < a_2 < \dots < a_k < n$ here gets the order number: $$\binom{a_1}{1} + \binom{a_2}{2} + \dots + \binom{a_k}{k}.$$

The properties of combinatorial number system ensure that this representation is a bijective mapping between $k$-combinations of $n$ and the integers in the interval $[0,\tbinom{n}{k}-1]$. In particular, given an integer $m$ in this interval, its representation in the combinatorial number system of degree $k$: $$m = \binom{a_1}{1} + \binom{a_2}{2} + \dots + \binom{a_k}{k}$$ uniquely defines numbers $0\leq a_1 < a_2 < \dots < a_k < n$ (the last inequality follows from $m<\tbinom{n}{k}$), i.e., a $k$-combination of $n$.

Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

Let $N(n;a_1,\dots,a_k)$ where $0\leq a_1 < a_2 < \dots < a_k < n$ be the order number of $(a_1,\dots,a_k)$ as a combination from ($n$ choose $k$).

Since there are exactly $\binom{n-1}{k-1}$ combinations with $a_1 = 0$, we have a recurrence:

if $a_1 = 0$, then $$ N(n;a_1,\dots,a_k) = N(n-1;a_2-1,\dots,a_k-1)$$

if $a_1 > 0$, then $$N(n;a_1,\dots,a_k) = \binom{n-1}{k-1} + N(n-1;a_1-1,a_2-1,\dots,a_k-1).$$

with initial condition $N(n;)=0$ (i.e., when $k=0$) for any $n$.

For example, $$N(13;0,1,4) = N(12;0,3) = N(11;2) = \binom{10}{0} + N(10;1)$$ $$= \binom{10}{0} + N(10;1) = \binom{10}{0} + \binom{9}{0} + N(9;0)$$ $$=\binom{10}{0} + \binom{9}{0} + N(8;) = 1 + 1 + 0 = 2$$ as required.