3
$\begingroup$

I'm toying around with the idea of designing a board game. I like the idea of a hexagon-tile setup (a la Catan). There would be some number of different resource categories; I'm trying to determine how many. Each tile would have a number from 1 to 6 associated with each resource category, representing the number you'd have to meet or beat when rolling a D6 to acquire that resource. And you'd get one die roll per resource type. In the interest of fairness, I'd like each tile to have the same total value -- probably the floor of the expected roll value times the number of different resources.

So, for example, if I only had one resource type (let's call it Resource A), then I'd want each tile to have a total value of 3, which trivially means that I'd have one unique type of tile, which had a value of 3 for Resource A. One die rolls that value in exactly one way.

If I had two resource types, Resource A and Resource B, then I'd want the total value of each tile to be 7. Brute-forcing it, I know that there are 6 different permutations of 2D6 rolls that add up to 7 (1 & 6, 2 & 5, 3 & 4, 4 & 3, 5 & 2, 6 & 1). So in that case, I'd have 6 unique types of tiles. But what if I wanted three resource types, with a total value of 10? Or four dice rolls, with a total of 14?

So I'm wondering, what is the formula for generalizing this? Specifically, the number of permutations for which n dice will add up to a total m. And explain it like I'm simple -- it's been a long while since I've done this kind of math. I'm curious for my own enrichment, as well as the (theoretically) practical application of determining how many unique tiles I could potentially include.

$\endgroup$
  • 2
    $\begingroup$ Does this help you? en.wikipedia.org/wiki/Partition_(number_theory) $\endgroup$ – gebruiker May 14 '14 at 19:17
  • $\begingroup$ That's informative, although it may take me some time to grok it. I think technically I want a composition, since order matters, but Wikipedia's page for that is much less detailed. $\endgroup$ – Hammer Bro. May 14 '14 at 20:41
4
$\begingroup$

The number of ways for $2$ dice to sum to $n$ is obviously $0$ for $n<2$ and $n> 12$. For the others, think about how many different numbers that appear on the first die allow you to create a sum of $n$ with the numbers on the other die. For $7$, as an example, no matter what you roll on the first die there is a way to make seven with the other die. For $6$, however, you can't roll a $6$ on the first die and then get a total of $6$ on both dice.

Since for a given number on the first die there is at most one way to make the desired sum with the other die, counting this will give the desired result. It's easy to see that if $n \le 7$ the number is $n-1$ and if $n > 7$ the number is $13 - n$.

Plotting this comes out very nicely:

enter image description here


Per your comment we can extend this somewhat to a more general situation: you want the number of ways to have $n$ dice with values between $1$ and $k$ sum to a value $m$. Mathematicians say that this is a $n$-composition of $m$ with largest part at most $k$.

This is a non-trivial problem. See this page. The solution turns out to be the coefficient of $x^m$ in the polynomial $$\left(\frac{x^{k+1}-x}{x-1}\right)^n.$$

For small values of $m,n$ it's best to compute this by hand or by computer. With large values there are approximation methods, as detailed on the aformentioned link.

$\endgroup$
  • $\begingroup$ I realize now that I wasn't initially as clear as I'd intended to be (I've edited the original question) -- I'm interested in a generalization for finding the permutations of an arbitrary number of dice rolling an arbitrary total. Still a valuable explanation, though. $\endgroup$ – Hammer Bro. May 14 '14 at 20:33
  • $\begingroup$ @HammerBro. I added a bit of information for the general problem. $\endgroup$ – guest196883 May 14 '14 at 21:32
  • $\begingroup$ Spiffy. Didn't realize it was theoretically so complicated. Ironically, I'm also having trouble programming a general method to compute this. But practically, if I just want to type in three or four nested for loops (which the results indicate I want), it's braindead simple. Thanks. $\endgroup$ – Hammer Bro. May 14 '14 at 22:20
4
$\begingroup$

The number of permutations that give a sum of $k$ when rolling $n$ 6-sided dice is: $$P\left( {n,k} \right) =\sum\limits_{i = 0}^{{i_{\max }}} {{{\left( { - 1} \right)}^i}\left( {\begin{array}{*{20}{c}} n\\ i \end{array}} \right)\left( {\begin{array}{*{20}{c}} {k - 6i - 1}\\ {k - 6i - n} \end{array}} \right)}$$ where $\displaystyle {i_{\max }} = \left[ {\frac{{k - n}}{6}} \right]$ and $\left[ x \right]$ represents the "floor" function.

For instance, the number of permutations that yield a sum $k=31$ when rolling $n=10$ dice is: $$P\left( {10,31} \right) = \sum\limits_{i = 0}^3 {{{\left( { - 1} \right)}^i}\left( {\begin{array}{*{20}{c}} {10}\\ i \end{array}} \right)\left( {\begin{array}{*{20}{c}} {31 - 6i - 1}\\ {31 - 6i - 10} \end{array}} \right)} =$$ $$ \left[ {\left( {\begin{array}{*{20}{c}} {30}\\ {21} \end{array}} \right) - \left( {\begin{array}{*{20}{c}} {10}\\ 1 \end{array}} \right)\left( {\begin{array}{*{20}{c}} {24}\\ {15} \end{array}} \right) + \left( {\begin{array}{*{20}{c}} {10}\\ 2 \end{array}} \right)\left( {\begin{array}{*{20}{c}} {18}\\ 9 \end{array}} \right) - \left( {\begin{array}{*{20}{c}} {10}\\ 3 \end{array}} \right)\left( {\begin{array}{*{20}{c}} {12}\\ 3 \end{array}} \right)} \right] =3393610$$ I tried to explain "step-by-step" the inner workings of that formula , using pure combinatorics arguments in my site, at this link and, honestly, this proved to be not an easy task.

$\endgroup$
  • 1
    $\begingroup$ A small suggestion. The last term in the formula could instead be written as ${(k−6i−1)\choose (n-1)}$ $\endgroup$ – true blue anil Jul 6 '15 at 7:03
1
$\begingroup$

The number of times sum of $n$ dice rollings is $m$ can be found as coefficient of $x^m$ in expansion of $(x+x^2+x^3+x^4+x^5+x^6)^n$.

$Example:$ When TWO dice are rolled: $$ (x+x^2+x^3+x^4+x^5+x^6)^2 = x^{12}+2 x^{11}+3 x^{10}+4 x^9+5 x^8+6 x^7+5 x^6+4 x^5+3 x^4+2 x^3+x^2 $$

Because coefficient of $x^7$ is $6$ in above expression, it means there are $6$ combinations that add up to $7$.

$Example:$ When THREE dice are rolled: $$ (x+x^2+x^3+x^4+x^5+x^6)^3 = x^{18}+3 x^{17}+6 x^{16}+10 x^{15}+15 x^{14}+21 x^{13}+25 x^{12}+27 x^{11}+27 x^{10}+25 x^9+21 x^8+15 x^7+10 x^6+6 x^5+3 x^4+x^3 $$

As coefficient $x^{10}$ is $27$ in above expression, that means there are $27$ combinations that add up to $10$.

$\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.