4
$\begingroup$

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?

2 Answers 2

5

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

1

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.

  • 0
    @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 useful2019-03-10