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.

The number of ways to obtain a total of $p$ in $n$ rolls of $s$-sided dice is:

$$c=\sum_{k=0}^{\lfloor(p-n)/s\rfloor}(-1)^k\binom{n}k\binom{p-sk-1}{n-1}\;.$$

What I'm interested in is making the $n$ rolls, but then disregarding the lowest $m$ rolls. E.g. out of five rolls $1, 5, 3, 5, 6$, disregard the lowest two - the $1$ and $3$.

I want to know the number of ways to obtain $p$ as the sum of the remaining $n-m$ rolls. (In my example, the sum was $5+5+6=16$, with of course $n=5, m=2$)

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

This is a brute force approach, resulting in very long expressions and summations. I am not sure if this is helpful, but I guess, it is a start.

Let $c(n,p,s)$ denote the number of ways to get a sum of $p$ in $n$ rolls of $s$-sided dice. If it is given that the values of all the rolls are at least $r$ and the value $r$ occurs exactly $k$ times, then the remaining $n-k$ values can be determined in $c(n-k, p-rn, s-r)$ ways.

Suppose $n$ rolls satisfy the property that $n-m$ largest among them add up to $p$. Let $r$ be the smallest among the largest $n-m$ values. Let there be exactly $k$ rolls with value $r$ among the largest $n-m$. And let the number of rolls among the smallest $m$ rolls, whose value is equal to $r$ be $m-i$. Then the number of ways we can get such $n$ rolls is given by

$$ \binom{n}{i} \binom{n-i}{k+m-i} (r-1)^i c(n-m-k,p-r(n-m),s-r) $$

(The positions for $i$ rolls (whose values are less than $r$) and $k+m-i$ rolls (whose values are equal to $r$) can be picked in $\binom{n}{i} \binom{n-i}{k+m-i}$ ways. Each of these $i$ rolls can take any value less than $r$, so there are $(r-1)^i$ possibilities for that. And the remaining $n-m-k$ should all be greater than $r$ and add up to $p-rk$, hence the $c(.)$ term.)

The required answer is obtained by summing the above expression over all possible $i$, $r$ and $k$ values.

$$ \sum_{r=1}^{s} \sum_{k=1}^{n-m} \left[ c(n-m-k,p-r(n-m),s-r) \sum_{i=0}^{m} \binom{n}{i} \binom{n-i}{k+m-i} (r-1)^i \right] $$

share|improve this answer
    
First of all, thank you for your effort! I'm still trying to figure out the logic, but immediately I see a problem with $h(n,m,r)$. Namely, when $r=1,i=0$, the expression is indeterminate because the factor $(r-1)^i$ becomes $0^0$. –  vedran Jan 2 '13 at 11:09
    
@vedran Looks like it should be treated as $1$ here. But I am having doubts about the logic itself, it looks like it has a lot of flaws, particularly about $h(n,m,r,k)$. –  polkjh Jan 2 '13 at 11:43
    
Yes, it seemed like it should be regarded as $1$. Still, in the final expression, theres the third argument to $c$, which is $s-r$. $r$ iterates from $1$ to $s$, so it would seem there's going to be $c(..., ..., 0)$ which doesn't make sense because you can't roll dice with 0 sides. –  vedran Jan 2 '13 at 12:15
    
@vedran Handling border cases should not be a problem. In some cases, the expression itself might give the required value and even if it doesn't, we can just force values on border cases so that they fit the rest of the arguments. For example, (with $a \neq 0$), $c(0,0,0) = c(0,0,a) = 1$, $c(0,a,0)=c(a,0,0) = 0$ etc. There were many logical issues in the earlier answer, I edited it now, hopefully it has no more flaws! –  polkjh Jan 2 '13 at 12:41
    
Looks like it works better now, but it seems to always yield zero for the maximum sum, i.e. $p=s(n-m)$. –  vedran Jan 2 '13 at 13:18
show 1 more 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.