Botches, Failures, and Successes 

Here's an interesting random walk problem. Suppose we have N dice, each of which has a+b+c faces, where "a" is the number of "botch" faces, "b" is the number of failure faces, and "c" is the number of success faces. (Each individual face is considered equally likely). Then, we roll all N of the dice and evaluate the results as follows: Let B denote the number of botched dice, F the number of failures, and S the number of successes. The overall status is either a botch, a failure, or a success accordingly as S−B is less than, equal to, or greater than zero. In other words, we start at zero on the number line, and each botched die moves us 1 to the left, each successful die moves us 1 to the right, and Failures leave our position unchanged. Our overall outcome depends on where we end up relative to zero. 

One way of computing the result is based on the fact that, out of all possible outcomes from rolling the N dice, the number of outcomes for which S−B has the value k is just the coefficient of x^{k} in the expansion of the generating function 



For example, if we have a=1, b=4, c=5, and N=3 dice, the generating function is 



If we multiply this out we find 



which shows that there is 1 outcome with S−B = −3, and there are exactly 12 outcomes with S−B = −2, and so on up to 125 outcomes with S−B = +3. Our criterion says that any outcome with S−B < 0 is an overall botch, so there are 1 + 12 + 63 = 76 botches. Then there are 184 outcomes with S−B = 0, so these are the "failures". Finally, there are 315 + 300 + 125 = 740 successes, i.e., outcomes with S−B > 0. 

Obviously this could be generalized to include other categories. For example, if we have N dice, each with a+b+c+d sides, where a is the number of "superbotches" (which cancel two successes), b is the number of botches, c is the number of failures, and d is the number of successes, then the number of outcomes for which S−B−2D (where D is the number of superbotches) has the value k is just the coefficient of x^{k} in the expansion of the function 



This raises an interesting question: What is the most efficient way of extracting the coefficient of x^{t} from a given generating function? For simplicity, let's increase each power of x by 2, so the number of outcomes for which S−B−2D has the value k−2N is the coefficient of x^{k} in the expansion of 



To find the coefficient of x^{k} we could simply expand the function by raising the polynomial to the Nth power, but another approach would be to numerically evaluate the kth derivatives of f(x) at x = 0. We know that 


so the kth derivative at x = 0 is (k!)c_{k}. If we have enough precision in our calculations we could determine the kth derivative based on k+1 values of f(x) very near x = 0. I'm not sure if this would be more or less efficient than just expanding f(x). Are there any other ways of determining the coefficients implied by a generating function? 

Another interesting question is whether the coefficients are approximated by some known continuous distribution. For example we know that (normalized) coefficients of f(x) = (1 + x)^{N} approach a normal distribution as N increases. What function do the (normalized) coefficients of (a + bx + cx^{2})^{N} approach as N increases? It must be some sort of skewed distribution as suggested by 



By the way, a more explicit answer to the original problem would be: With N dice the number of outcomes for which S−B has the value k−N is 



where the square brackets [x] signify the largest integer less than x. So, the number of "botches" for N dice with a+b+c sides is given by the double summation 



The number of "failures" is the single summation 



The number of successes is the double sum 


