Throwing dice.

Welcome back my friend!

With this post I want to talk about some interesting applications of the theory of generating functions in relation to the enumeration of combinations.

For this purpose let’s introduce a very simple problem: “Say we throw three regular dice, in how many ways the sum of the upper faces can be equal to 15?” That sounds like a reasonably simple problem for which we will develop a set of combinatorics tools, don’t be scared by the math, is really simple and at the end of the post we will be able to extend this exercise to n dice and any valid resulting sum. The theory behind the calculations here performed has some extremely important implications in the theory of coding and in general might be extended to a wider set of problems, but for now let’s start with the three dice..

So, we want to have where , that make perfectly sense right? Regular dice have six faces and we want the sum of the faces to be 15. For the moment let’s start with a much simpler enumeration problem which will give us some insight on how to proceed: “In how many ways can we select three distinguishable objects and ?”

For every possible combination we have to decide whether we want to take or not take , then perform the same decision for and . We can display this dilemma in mathematical language by building the schematic product for our decision problem: We can either pick no or one , we cannot pick more than one , the same logic apply for and , we either pick nothing ore one.

This mean that can build a sequence: , and . In general for any given , we have a generating function which in our simple case is just ,  and , that is, only two terms,

The schematic product for our selection problem is given by the expression (Where the sum is an OR operation and the multiplication an AND operation):

Which have the meaning of: one can either pick zero or one and zero or one &c, after the obvious simplification for the first coefficient (the zero coefficient), the expression can be expanded to:

Where the coefficients are giving us the ways to select the three distinguishable objects and , including the empty selection which is represented by that lonely 1. Now, if you put you get the number of selections:

Which is what we’re looking for, the coefficients of the expression are telling us in how many ways we can pick the three objects: Three ways of picking one object, three ways of picking two objects and one way to pick them all..

That’s great, let’s come back to our original problem since now we have one important tool to solve it. A dice have six faces, each face have a value and we have three dice, so our schematic product is:

note that the term for the zero coefficient is missing, that is because we cannot have zero as possible result for a dice roll, the exponent three is due to the amount of dice we have, that is clearly the multiplication of three generating functions which are modelling our dice.

What we need to solve our problem is the coefficient of , remember this is the same setup as for the simple problem, we want the amount of possible combinations which give us 15. To find this coefficient we do not need to expand that expression, I mean we can, but that’s a tedious and error prone exercise and for sure is not possible for bigger problems with 100 dice for example (is possible, but stupid).

We need to reformulate that expression in a way which allow us to perform some manipulation, let’s start with some series:

In our case, we have:

Which can be further simplified to:

Very well, we’re almost done! From this expression we need to find the coefficient . The only problematic part seems to be or more generally , if you have a closer look you can spot that the the Maclaurin series expansion for  is:

for

which would be very helpful if there wasn’t any exponent to that fraction, to find the coefficient we’re looking for one can use the binomial theorem putting instead of and instead of we have that the coefficient of is given by , which after some manipulations ends up to be equal to .

That’s not a coincidence that the coefficient of is equal to the amount of ways to place indistinguishable balls into distinguishable cells, but for the moment let’s go back to our original question, how to find the coefficient of .

Our expression has three parts which are multiplied together, each part has a certain amount of terms which have the form of from , and from and the obvious from guess what… …

We need to fulfill this condition:

where

applying the binomial theorem we can find the coefficients for and using  the coefficients of , so we can put all together and see from what that 15 can be made of:

1. 
2. 
3. 

For which we have: ! That’s done, the solution for our problem is 10! There are 10 ways to get 15 from the sum of the upper faces of three rolled dice, we can verify this by expanding our original expression (or by rolling 3 dice).

Let’s see how to use this knowledge to solve larger problems, we can use the exact same procedure developed here to calculate any valid sum for any number of dice:

using myint = int_fast32_t;
myint number_of_sums( myint n, myint t )
{
    myint solution{ 0 };
    myint c1{ 0 }; //This is the coefficient of (1-x^6)^n
    myint c2{ 0 }; //Coefficient of (1-x)^(-n)
    for( myint i{ 0 }, k{ 0 }; k + n <= t ; k += 6, ++i )
    {
        c1 = pascal[ n ][ i ];
        if( 0 != i%2 ) {
            c1 *= -1;
        }
        c2 = pascal[ t - k - 1 ][ t - n - k ];
        solution += c1 * c2;
    }
    return solution;
}

Where pascal is the pascal’s triangle, which can be build with some simple method like this:

constexpr myint max_size{ 1000 };
myint pascal[ max_size ][ max_size ];
void calculate_pascal()
{
    for( myint i{ 0 } ; i < max_size ; ++i )
    {
        pascal[ i ][ 0 ] = 1;
        pascal[ i ][ i ] = 1;
    }
    for( myint n{ 2 } ; n < max_size ; ++n )
    {
        for( myint k{ 1 } ; k < n ; ++k )
        {
            pascal[ n ][ k ] = pascal[ n-1 ][ k-1 ] + pascal[ n-1 ][ k ];
        }
    }
}

and now we calculate the amount of ways to obtain a sum of 250 when rolling 100 dice: 5.270.981.265.418.279.600! Cool!

Thanks for reading, hope you had fun!