1
$\begingroup$

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\} \}$.

$\endgroup$
  • $\begingroup$ (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? $\endgroup$ – Asaf Karagila Jul 20 '14 at 19:02
  • $\begingroup$ I edited my question clarifying that two points. Thanks for your time. $\endgroup$ – gd1 Jul 20 '14 at 19:05
  • $\begingroup$ I suppose that by $[0,C_{k,M} - 1]$ you don't mean a closed interval? $\endgroup$ – wabu wabu rabu Jul 20 '14 at 19:07
  • $\begingroup$ I do mean a closed interval. $\endgroup$ – gd1 Jul 20 '14 at 19:08
  • 1
    $\begingroup$ Well, you mean the closed interval of integers. @gd1 Presumably, I'm not allowed to map something to $\pi$.... $\endgroup$ – Thomas Andrews Jul 20 '14 at 19:12
2
$\begingroup$

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$.]

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 Thanks. I need some time and efforts to digest this, though. $\endgroup$ – gd1 Jul 20 '14 at 19:16
  • $\begingroup$ I just added a brief comment on the reverse operation. @gd1 $\endgroup$ – Thomas Andrews Jul 20 '14 at 19:18
  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews Jul 20 '14 at 19:25
  • $\begingroup$ But the StackOverflow question gives other algorithms for mappings of $m$-subsets... $\endgroup$ – Thomas Andrews Jul 20 '14 at 19:35
  • $\begingroup$ 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. $\endgroup$ – gd1 Aug 1 '14 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.