# Looking for a bijection between this set and natural numbers

I am a computer programmer, and I am struggling with this mathematical problem without finding a consistent and efficient solution.

Let $A_{k, M}$ be the set of all the possible assignments for $n_1, n_2, ...,n_k$ non-negative integers such that $\sum_{i=1}^{k}{n_i} = M$. I need to compute $C_{k,M}=|A_{k, M}|$ for arbitrary $k, M$ and I need a bijection between $A_{k, M}$ and $[0, C_{k,M}-1]$. The bijection should be simple to compute "in both directions" and should not require exhaustive enumeration.

Example. $k = 3$, $M = 3$. The possible assignments are $\{3, 0, 0\}, \{0, 3, 0\}, \{0, 0, 3\}, \{0, 1, 2\}, \{0, 2, 1\}, \{1, 0, 2\}, \{2, 0, 1\}, \{1, 2, 0\}, \{2, 1, 0\}, \{1, 1, 1\}$, therefore $C_{k,M}=|A_{k, M}| = 10$.

I have done little research so far, I have looked at combinatorial/factorial number systems (you may assume I know what they are about) but the problem seems to be quite different. Can you give me some directions?

EDIT: I clarify a few points as requested. 1) I don't actually know there is a "simple to compute" bijection, but I do know that my inability to find it is no evidence of its nonexistence, therefore I am asking here for your advice. 2) The two sets are: $A_{k, M} = \{ (n_1, n_2, ...,n_k) : \sum_{i=1}^{k}{n_i} = M \}$ and $[0, |A_{k, M}|-1] \subset \{ \mathbb{N} \cup \{0\} \}$.

• (1) Why do you think there is a bijection which is "simple to compute"? (2) It's not quite clear which sets you are looking to find a bijection between, could you clarify this a bit please? – Asaf Karagila Jul 20 '14 at 19:02
• I edited my question clarifying that two points. Thanks for your time. – gd1 Jul 20 '14 at 19:05
• I suppose that by $[0,C_{k,M} - 1]$ you don't mean a closed interval? – wabu wabu rabu Jul 20 '14 at 19:07
• I do mean a closed interval. – gd1 Jul 20 '14 at 19:08
• Well, you mean the closed interval of integers. @gd1 Presumably, I'm not allowed to map something to $\pi$.... – Thomas Andrews Jul 20 '14 at 19:12

By the stars and bars method, there is a bijection between $A_{k,M}$ and the set of $k-1$-subsets of $\{1,2,\dots,M+k-1\}$.

Essentially, $n_1,n_2,\dots,n_k$ goes to $\{n_1+1,n_1+n_2+2,\dots,n_1+\dots+n_{k-1}+k-1\}$.

The set of $m$-subsets of $\{1,2,\dots,N\}$ can be given indices in $\{0,1,\dots,\binom{N}m-1\}$ via the squashed ordering, where $1\leq a_1<a_2<\dots<a_m\leq N$ is mapped to the integer:

$$\sum_{j=1}^m \binom{a_j-1}{j}$$

The reverse map, however, is not as easy.

To compute the reverse map, given an index $I$, find the largest $a_m$ so that $\binom{a_m-1}{m}\leq I$. Then, if you know $a_{k+1},\dots,a_m$, find the largest $a_k$ so that $$\binom{a_k-1}{k} \leq I-\sum_{j=k+1}^m \binom{a_j-1}{j}$$

[Note, in all the above, we are assuming that if $a<b$ then $\binom{a}{b}=0$.]

• +1 Thanks. I need some time and efforts to digest this, though. – gd1 Jul 20 '14 at 19:16
• I just added a brief comment on the reverse operation. @gd1 – Thomas Andrews Jul 20 '14 at 19:18
• Oddly, I seem to be the only person using the squashed order index - when I Google "squashed order," the first two results I get the description of its use in a bridge deal mapper, and in an answer from Stack Overflow. – Thomas Andrews Jul 20 '14 at 19:25
• But the StackOverflow question gives other algorithms for mappings of $m$-subsets... – Thomas Andrews Jul 20 '14 at 19:35
• I had some time to read this through, and it was very helpful. The bijection between $A_{k, M}$ and that subset is just impressive. At the moment, I am still unable to truly understand it but I'll think harder. However, I used another method for mapping the combination to an integer, the "combinatorial number system" as described by D. Knuth. For the time being, I am satisfied with this result. – gd1 Aug 1 '14 at 22:37