Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Define a function $F(A, B, C)$ as the number of ways you can roll $B$ $C$-sided dice to sum up to $A$, counting different orderings (rolling a $2$, $2$, and $3$ with three dice is different from rolling a $2$, $3$, and $2$).

Example:

With three $5$-sided dice, the list of $F(A, B, C)$ values in the domain of the possible values of $A$ for $B = 3$ and $C = 5$ is:

$$F(3, 3, 5), F(4, 3, 5), F(5, 3, 5), F(6, 3, 5), ... , F(15, 3, 5)$$ is evaluated to: $$1, 3, 6, 10, 15, 18, 19, 18, 15, 10, 6, 3, 1$$ Call this list $L_1$.

Let $s$ be the number of sides on each die, let $n$ be the number of dice, and let $v$ be the total value to roll from the $n$ dice. Let $L_2$ be the list of ${v - 1}\choose{v - n}$ in the domain of $v$ values for $n = 3$. Then $L_2$ is: $${{3 - 1}\choose{3 - 3}}, {{4 - 1}\choose{4 - 3}}, {{5 - 1}\choose{5 - 3}}, {{6 - 1}\choose{6 - 3}}, ... , {{15 - 1}\choose{15 - 3}}$$ Which is evaluated to: $$1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91$$ Comparing $L_1$ with $L_2$, we see that only the first $s$ values of the lists are equal: $$1, 3, 6, 10, 15$$ I have observed that this property holds with other values of $s$, $v$, and $n$, and $A$, $B$, and $C$.

Can someone please explain why $L_1$ and $L_2$ share the first $s$ values?

share|cite|improve this question
up vote 5 down vote accepted

The first $s$ terms of $L_1$ are the compositions of $A$. They stop being the compositions of $A$ at that point because you hit the limit. In your example, you miss the composition of 8 as 6+1+1 because the dice only have 5 sides. The compositions of $n$ into exactly $k$ parts are given by ${{n - 1}\choose{k - 1}}$ as shown here

share|cite|improve this answer

Refer to answers to Rolling dice problem , because this is the same as finding a $B$-tuple, with values in the range $1..C$, summing up to $A$, i.e. with values in the range $0..C-1$, summing up to $A-B$. So

$$N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right.$$

with $m=B,\ r=C-1,\ s=A-B$.

The formula for $Nb(s,r,m)$ is given in the answers to the question linked above.

share|cite|improve this answer
    
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review – user190080 Mar 19 at 18:44
    
@user190080, the review you are reffering to, itself says it is looking OK. – Subhadeep Dey Mar 19 at 19:07
    
@SubhadeepDey actually I am not referring to that specific review - in which I've recommended the deletion of the above answer as it is. However, since I am the only one of the four reviewer who thought this way I guess the answer stays. Still I think it can be improved or would be better suited as comment as a whole. – user190080 Mar 19 at 19:13
    
@user190080, yes, I like your view. But (unfortunately) the user is $\lt 50$ reputation. So, he can't comment. – Subhadeep Dey Mar 19 at 19:18
    
@SubhadeepDey true. But you can get 50 reps pretty fast and besides, the question has already seen some time to say the least so probably some more days wouldn't have mattered anyway. After all it's fine, the link seems to be really useful – user190080 Mar 19 at 19:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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