# How many different combinations of a six sided die rolls equals n

Say I want to roll a six-sided-die until all the rolls I have made added together equal X (for example a number like 812). How do I calculate how many different possible combinations of dice rolls add up to X?

for example: say I want to find the different roll combinations that equal 6: 6 51 15 42 24 33 123 312 213 114 411 141 1113 3111 1311 1131 11112 21111 12111 11211 11121 and so on...

I have found that this approach does not work for larger numbers. Thanks

Thanks

• You missed out a lot of combinations in your example, such as $1,1,1,1,1,1$ – mrnovice Mar 30 '17 at 4:36
• A somewhat brute-force approach is to use generating functions. Letting $[x^n]$ denote the operation of returning the coefficient of $x^n$ from the expansion of whatever follows (e.g. $[x^3](5x^3+3x^2+x+1)=5$) we have the total will be $\sum\limits_{k=0}^n [x^n]((x+x^2+\dots+x^6)^k)$. Of course, this isn't particularly useful for hand-calculations but its fine for a computer. – JMoravitz Mar 30 '17 at 5:04
• Thanks you, I have updated it – halibet1234 Mar 30 '17 at 5:04
• In essence, what you are asking for is the number of compositions of your desired number, but with the restriction that partsizes be between 1 and 6 as in restricted partitions, like a restricted ordered partition if you will. – JMoravitz Mar 30 '17 at 5:06
• @JMoravitz Thank you! I want to write an algorithm to do this calculation, and this will help a lot – halibet1234 Mar 30 '17 at 5:13

Instead of the clunky generating function approach I mentioned in the comments above, a stronger tool to use for this specific problem is recurrence relations.

Let $a_n$ represent the number of compositions of the number $n$ using only the numbers $1,2,\dots,6$

As the upper bound condition doesn't come into play for $n\leq 6$ these numbers when $n\leq 6$ (not when $n>6$) are the same as the number of ordinary compositions, i.e. $a_1=1, a_2=2, a_3=4, a_4=8, a_5=16, a_6=32$

For $n\geq 7$ any partition of $n$ into parts none of which exceeding $6$ will either end with a $1$, end with a $2$, ..., or end with a $6$. There are exactly $a_{n-1},a_{n-2},\dots,a_{n-6}$ of each of these such compositions respectively.

We have then the recurrence relation

$$a_n = a_{n-1}+a_{n-2}+\dots+a_{n-6}$$

Similar to the fibonacci numbers, these are what some people call the Hexanacci Numbers

$\begin{array}{rl}a_1&=1\\ a_2&=2\\a_3&=4\\a_4&=8\\a_5&=16\\a_6&=32\\\hline\end{array}$

$\begin{array}{lrl}a_7&=a_6+a_5+a_4+a_3+a_2+a_1&=32+16+8+4+2+1&=63\\a_8&=a_7+a_6+a_5+a_4+a_3+a_2&=63+32+16+8+4+2&=125\\a_9&=a_8+a_7+a_6+a_5+a_4+a_3&=125+63+32+16+8+4&=248\\ \vdots\\ a_n&=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5}+a_{n-6}\end{array}$

• So if I understand correctly for say – halibet1234 Apr 1 '17 at 18:49
• @halibet1234 That comment does not make any sense to me. It seems you began a thought and never completed it. It would be like if – JMoravitz Apr 1 '17 at 19:00
• Sorry I hit enter for a new line and it submitted it lol. So if I understand correctly for say a10=a10−6+a10−5+a10−4+a10−3+a10−2+a10−1 will equal 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + 2^9 = 1008? – halibet1234 Apr 1 '17 at 19:02
• No, not quite because $a_{10-1}=a_9$ is not equal to $2^9$ (and not equal to $2^{9-1}$ either which is the pattern you should have thought). The pattern that $a_n=2^{n-1}$ breaks at $a_7$ which is equal to $63$ not $64$. You have $a_7=a_1+a_2+a_3+a_4+a_5+a_6=63\neq 64$, then $a_8=a_2+a_3+a_4+a_5+a_6+a_7=2+4+8+16+32+63=125\neq 128$. – JMoravitz Apr 1 '17 at 19:06
• @user3 correct, that is a different problem entirely. For that use stars and bars with inclusion-exclusion or partition numbers, whichever meets your specific problem. Ask a new question for more details instead of asking in comments of an old question like this and be sure to clarify what does or doesn't count as different arrangements. – JMoravitz Nov 30 '17 at 15:04