What's the probability of rolling at least $k$ on $n$ dice with $s_1,\ldots,s_n$ sides?

Is there a way to determine the chance of rolling at least $k$ on $n$ dice with $s_1,\ldots,s_n$ sides?

Example: What is the chance of rolling a sum of at least 13 on 3 dice with 6, 8, and 10 sides?

I know that the chance of rolling exactly $k$ on $n$ dice with $s$ sides is

$$F_{s,n}(k)=\sum_{i=1}^{k-n+1} F_{s,1}(i)F_{s,n-1}(k-1)$$

where $F_{s,1}(k)=\frac{1}{s}$ for all $1\leq k\leq s$ and $0$ otherwise (see this Wikipedia page), but I am not sure how to either generalize it for differently sided dice or combine it for different values of $s$.

Note: This will be done programmatically so efficiency is very important to me.

-

Recursively, $\displaystyle F_{s_1,\cdots,s_n}(k)=\sum_iF_{s_1}(i)F_{s_2,\cdots,s_n}(k-i)$ with $\displaystyle F_{s}(k)=1/s$ if $1\le k\le s$ and $0$ otherwise. The sum can be over every $i$ in $\mathbb{Z}$.

Another approach One can also compute the generating function of the coefficients $F_{s_1,\cdots,s_n}(k)$, defined as $$G_{s_1,\cdots,s_n}(x)=\sum_kF_{s_1,\cdots,s_n}(k)x^k.$$ The generating function for a dice with $s$ sides being $(x+x^2+\cdots+x^s)/s$, $$(s_1\cdots s_n)G_{s_1,\cdots,s_n}(x)=\prod_{i=1}^n(x+x^2+\cdots+x^{s_i}).$$ Thus $(s_1\cdots s_n)F_{s_1,\cdots,s_n}(k)$ is the coefficient of $x^k$ in $$\prod_{i=1}^n(x+x^2+\cdots+x^{s_i})=\frac{x^n}{(1-x)^n}\prod_{i=1}^n(1-x^{s_i}).$$ Likewise, the sum over every $k\le K$ of $(s_1\cdots s_n)F_{s_1,\cdots,s_n}(k)$ is the coefficient of $x^K$ in $$\frac1{1-x}\frac{x^n}{(1-x)^n}\prod_{i=1}^n(1-x^{s_i}),$$ which is also the coefficient of $x^{K-n}$ in $$\frac1{(1-x)^{n+1}}\prod_{i=1}^n(1-x^{s_i}).$$

Numerical application For $K=12$, $s_1=6$, $s_2=8$ and $s_3=10$, $n=3$ hence one is interested in linear integer combinations of $6$, $8$ and $10$ at most equal to $K-n=9$, that is, in the coefficient $c_{9}$ of $x^{9}$ in $$\frac1{(1-x)^4}(1-x^6-x^8).$$ The coefficient of $x^k$ in $1/(1-x)^4$ is $a_k=(k+3)(k+2)(k+1)/6$ hence $$c_9=a_9-a_3-a_1,$$ and the chance of a sum at least $13$ is $$1-\frac{c_9}{6\cdot8\cdot10}=\frac{71}{120}.$$ Verification The chances that a dice with $s$ faces produces $s+1-k$ or $k$ are equal hence the probabilities of the sums $s_1+\cdots+s_n+n-k$ and $k$ are equal. In our case, $27-k$ and $k$ are equiprobable for each $k$ between $1$ and $26$ hence a result $\le13$ and a result $\ge14$ are equiprobable. A result $\ge13$ has probability $1/2$ plus the probability of a result exactly equal to $13$ hence one should check that a result equal to $13$ has probability $11/120$, or equivalently, that there exists $44$ ways to choose three positive integers less than $6$, $8$ and $10$ respectively such that their sum is $13$ (and this is true!).

-
Just to clarify - this algorithm is for the probability of getting exactly k on s1,...,sn dice. At least k is trivial from here though. Thanks! –  dpatchery May 3 '11 at 17:43

You can generalise your probability of rolling exactly $k$ from the first $n$ dice as

$$F_n(k) = \frac{1}{s_n} \sum_{i=k-s_n}^{k-1} F_{n-1}(i),$$

starting at $F_0(k)=0$ for all non-zero $k$, and $F_0(0)=1$. There are efficient ways of calculating this through addition and subtraction of running totals.

$$\sum_{j \ge k} F_{n}(j)$$
$$1- \sum_{j < k} F_{n}(j)$$