2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ You missed out a lot of combinations in your example, such as $1,1,1,1,1,1$ $\endgroup$ – mrnovice Mar 30 '17 at 4:36
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Mar 30 '17 at 5:04
  • $\begingroup$ Thanks you, I have updated it $\endgroup$ – halibet1234 Mar 30 '17 at 5:04
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Mar 30 '17 at 5:06
  • $\begingroup$ @JMoravitz Thank you! I want to write an algorithm to do this calculation, and this will help a lot $\endgroup$ – halibet1234 Mar 30 '17 at 5:13
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So if I understand correctly for say $\endgroup$ – halibet1234 Apr 1 '17 at 18:49
  • $\begingroup$ @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 $\endgroup$ – JMoravitz Apr 1 '17 at 19:00
  • $\begingroup$ 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? $\endgroup$ – halibet1234 Apr 1 '17 at 19:02
  • $\begingroup$ 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$. $\endgroup$ – JMoravitz Apr 1 '17 at 19:06
  • 1
    $\begingroup$ @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. $\endgroup$ – JMoravitz Nov 30 '17 at 15:04

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.