Roll a single 6 faced dice as many times as you want to reach a sum X [duplicate]

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?

marked as duplicate by JMoravitz, Ross Millikan combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 11 '17 at 3:48

• 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? – Arby Apr 11 '17 at 2:55
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}$
• 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. – JMoravitz Apr 11 '17 at 3:45
• @JMoravitz: I just found the OEIS link and the overall generating function, which seems like it should run in $O(n)$ time – Ross Millikan Apr 11 '17 at 3:47