Let $X^{s,d,m}$ be the random variable computing the result of rolling $d$ $s$-sided dice, picking the $m$ highest values and adding all of them. Then $X^{s,d,m}$ takes values in the range $m,\ldots,s\cdot m$. For $k$ in this range I'd like to compute the probabilities $P(X^{s,d,m}=k)$.
Note that $P(X^{s,d,m}=k)=d^{-s}\cdot c^{s,d,m}_k$, where $c^{s,d,m}_k$ is the number of favourable events. These are the numbers I'd like to compute.
The two extreme cases $m=1$ (in which we take the maximum value) and $m=d$ (in which we add all the dice) are more or less simple:
- $c^{s,d,1}_k=k^d-(k-1)^d$.
- $c^{s,d,d}_k$ is the coefficient of $x^k$ in the polynomial $(x+x^2+\cdots+x^s)^d$ and these can be computed explicitly (see e.g. this entry in Mathworld).
I'm able to compute the general case for given $s,d,m$ using Monte Carlo methods, but I'd like to find something more general and explicit expressions such as coefficients of polynomials or using a recursion from simpler cases.
For example if we expand $(x_1+\cdots+x_s)^d$ using the product rule $x_i\star x_j=:x_j^2$ whenever $j>i$, then $c_k^{s,d,1}$ is the coefficient of $x_k^d$ in the expansion. This leads me to think that choosing the right number of variables and the right product we can always compute the terms as coefficients of polynomials.
Do you know of any reference or have any insight on how to compute the values $c^{s,d,m}_k$?
Take an arrangement of $d$ dice with $s$ sides whose $m$ largest values add to $k$, and subtract $1$ from the number on each die. Dice which were originally $1$ will "disappear." The remaining dice will all have values between $1$ and $s-1$, and their $m$ largest values will sum to $k-m$. Letting $i$ be the number of dice which disappear, this leads to the recurrence $$ c^{s,d,m}_k=\sum_{i=0}^d\binom{d}{i}c_{k-m}^{s-1,d-i,m}. $$ Edit: There is a small mistake in the above argument. If some of the largest $m$ dice were equal to $1$, then they will disappear, so there will be fewer than $m$ dice adding to $k-m$. The actual answer is $$ \boxed{c^{s,d,m}_k=\sum_{i=0}^d\binom{d}{i}c_{k-m}^{s-1,d-i,\min(m,d-i)}.} $$