1
$\begingroup$

This question already has an answer here:

I am working on a problem where a single dice with 6 face is rolled multiple times to reach a sum of X. This is a combinatorics problem. For example if I just want to find out the number of way a sum of 5 has to be obtained (not including negative numbers) the answer would be (2^4) = 16. Basically it follows the formula 2^(X-1) where X is the sum.

But the above formula is valid when there are the restrictions on the numbers that can be used. In my specific case I have the restriction of a six faced dice (numbers from 1 to 6).

What should be my approach to solve this problem?

$\endgroup$

marked as duplicate by JMoravitz, Ross Millikan combinatorics Apr 11 '17 at 3:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ So one way to get a sum of 5 is to roll a 1 five times, 11111? Another way is a 2 and three 1's, 2111? Is 1211 different or the same? $\endgroup$ – Arby Apr 11 '17 at 2:37
  • $\begingroup$ @Arby They are different. Because sequence matters here $\endgroup$ – Ashwin Apr 11 '17 at 2:39
  • $\begingroup$ Do you only consider proper sums of 2 or more summands (e.g., 1+1=2), or do you consider "vacuous" sums of just 1 roll (e.g., roll a 2)? $\endgroup$ – Xoque55 Apr 11 '17 at 2:44
  • $\begingroup$ @Xoque55 : Both are considered $\endgroup$ – Ashwin Apr 11 '17 at 2:51
  • $\begingroup$ So for a sum of 7, you get $2^7-1$ ways as a single roll of 7 is impossible. For 8, a single roll of 8 is impossible, as are rolls with 7 and 1 of which there are two giving $2^8-3$ ways. For 9, you can't have 9, 81, 18, 711, 171, 117, 72, nor 27, giving $2^9-8$ ways. Am I on the right track? $\endgroup$ – Arby Apr 11 '17 at 2:55
1
$\begingroup$

The generating function for the sum of $n$ rolls is $(x+x^2+x^3+x^4+x^5+x^6)^n$ so you can sum the coefficient of $x^X$ in this from $\lceil \frac X6 \rceil$ to $X$. Doing this in Excel is pretty quick if you want a numeric answer. I find the series to be $$1,2,4,8,16,32,63,125,248,492,976,1936,3840,7617,15109,29970,59448,117920,233904,463968,920319,1825529,3621088,7182728,14247536,28261168,56058368,111196417,220567305,437513522,867844316,\ldots$$ These are the Hexanacci numbers, series A001592 in OIES where it says you can get the numbers (with an offset) as coefficients of $\frac {x^5}{1-x-x^2-x^3-x^4-x^5-x^6}$

$\endgroup$
  • 1
    $\begingroup$ For small $n$, the generating function approach would be fine, surely, but it runs in what, $O(n^2)$ time and a lot of memory storage? Recurrence relations should yield the answer in just $O(n)$ time with minimal memory needed. $\endgroup$ – JMoravitz Apr 11 '17 at 3:45
  • $\begingroup$ @JMoravitz: I just found the OEIS link and the overall generating function, which seems like it should run in $O(n)$ time $\endgroup$ – Ross Millikan Apr 11 '17 at 3:47

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