Order of a combination when mapping them to whole numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T15:58:38Z http://mathoverflow.net/feeds/question/29942 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29942/order-of-a-combination-when-mapping-them-to-whole-numbers Order of a combination when mapping them to whole numbers Claudiu 2010-06-29T17:36:44Z 2010-06-30T17:03:34Z <p>You can map whole numbers to combinations when taking them in order. For example, 13 choose 3 would look like:</p> <pre><code>0 --&gt; (0, 1, 2) 1 --&gt; (0, 1, 3) 2 --&gt; (0, 1, 4) etc... </code></pre> <p>Given a particular combination, such as <code>(0, 3, 9)</code>, is there a way to determine which whole number maps to it (26, in this case), short of writing out all the combinations in order until I hit upon the proper one? Furthermore, is there a way of doing this when counting combinations with repetitions?</p> <p>If anyone is wondering, this isn't homework, but for a personal programming project.</p> http://mathoverflow.net/questions/29942/order-of-a-combination-when-mapping-them-to-whole-numbers/29947#29947 Answer by Charles Matthews for Order of a combination when mapping them to whole numbers Charles Matthews 2010-06-29T18:01:34Z 2010-06-29T18:01:34Z <p>Well, yes, in the sense that dividing 26 by 12 choose 2 immediately tells you that 0 is the first digit. Dividing 26 by 11 choose 1 indicates that the second digit is 3. Subtracting 12 + 11 from 26 indicates that you should take the third of the (0, 3, ?) numbers, which is (0, 3, 6). This all looks quite algorithmic: you need to divide and take remainders by certain binomial coefficients or their sums.</p> http://mathoverflow.net/questions/29942/order-of-a-combination-when-mapping-them-to-whole-numbers/30077#30077 Answer by Max Alekseyev for Order of a combination when mapping them to whole numbers Max Alekseyev 2010-06-30T17:03:34Z 2010-06-30T17:03:34Z <p>Let $N(n;a_1,\dots,a_k)$ where $0\leq a_1 &lt; a_2 &lt; \dots &lt; a_k &lt; n$ be the order number of $(a_1,\dots,a_k)$ as a combination from ($n$ choose $k$).</p> <p>Since there are exactly $\binom{n-1}{k-1}$ combinations with $a_1 = 0$, we have a recurrence:</p> <p>if $a_1 = 0$, then $$N(n;a_1,\dots,a_k) = N(n-1;a_2-1,\dots,a_k-1)$$</p> <p>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).$$</p> <p>with initial condition $N(n;)=0$ (i.e., when $k=0$) for any $n$.</p> <p>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.</p>