0
$\begingroup$

I have a problem that goes like this, we have $n$ slots that can contain a value $r=[0,n]$ where $n \in \mathbb N$. In addition, the slots must add up to $n$, that is $n=\sum\limits_{i=1}^{n}r_i$. What are the total number of combinations that can be used to satisfy these requirements.

My specific case is where $n=6$. My first reaction was to see what the upper-bound of combinations where the value was allowed to repeat. This would be $$n^n \Rightarrow 6^6 = 46656$$ That would ideally allow me to check and make sure my solution wasn't off base. The next angle I took was to apply the fundamental principal of counting to determine the total number of acts that could be taken in each slot and to multiply them together. I came up with: $$\text{Total # of combinations} = 6(6-r_1)(6-\sum\limits_{i=1}^{2}r_i)...(6-\sum\limits_{i=1}^{n}r_i)\text{ ,where n=5}$$

My logic was that the number of choices of what I can put in the $i^{th}$ slot depends on what I put in the $i-1$ slot. Thinking through the equation I came up with a bit more, I realized that it fell flat on its face. If $r_1=6$ then the total combinations would equal 0 which is clearly not true. I tried looking at the $n=2$ and $n=3$ cases but did not have much luck.

Any tips or general advice would be greatly appreciated!

Note: It has been a while since I have worked on a math problem so please do correct/improve my question.

$\endgroup$
1
$\begingroup$

The answer is the number of solutions to: $$ r_1+r_2+\cdots + r_n = n \text{ where } 0 \leq r_i \leq n $$ To solve it, there is a great method called stars-and-bars. See if you can get the reasoning of that method and try to solve it. The final answer is: ${2n-1 \choose n-1}$.

$\endgroup$

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.