Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer 1

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|improve this answer
add comment

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.