\documentstyle[twocolumn]{article}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-1in}
\setlength{\textheight}{9in}
\begin{document}
\parindent=30pt

\title{A Response to Jim Vassilakos'\\
Method for the Derivation of\\
Constrained Number Probabilities}
\author{\copyright 1991 Jeffrey Contompasis \\ All Rights Reserved.}
\date{JCONTOMP@TUFTS.BITNET}
\maketitle
\setcounter{page}{10}

{\it \noindent
{\Large J}effrey Contompasis {\sf BSChE, MSChE} is a chemical engineer who is
currently part of the evergrowing ``Massachusetts Miserable". His article addresses
{\em Jim's Rectangle} as presented in Guildsman \#3.}

\section{The Problem}

     Given {\em n} ideal {\em s}-sided dice
(abbreviated {\em n}d{\em s}), what is the probability of
rolling a total, {\em t}, and what is overall probability distribution?


\subsection{Answering Jim's Questions}

     Four questions were posed after Jim's Rectangle was created.

     The first two were ``Does it work?" and ``Why?"

     My response it ``yes" because it is based upon summing the probabilities of
rolling one die and the total, {\em t}, minus the value rolled on that first die.  By
continuing this process until there is but one die left will yield the
probability of rolling t on {\em n}d{\em s}.  This will be explained in detail later.

     The second two were ``Is there an easier method?" and ``Has it been shown
elsewhere?"

     The response is ``yes" to the third question for a computer, but probably
``no" for a human.  Jim Vassilakos' method can be scratched out on a piece of
paper easily.  A simpler method actually requires more mindless, tedious,
iterative calculations.  But, this makes it extremely quick to code on a
computer.

     As for other implementations, a library search yielded no book in which a
method like Jim's Rectangle is mentioned in any form.  One might think that
this would be a classic probability exercise.


\subsection{A Recursive Approach}

     Recursion: what is it?  Recursion is essentially answering a question in
such a way that it leads to another question.  This continues until a
``bottoming out" occurs.

     The classic example is the definition of the factorial (symbolized by an
exclamation mark, ``!").  What is $(2!)$?  It is $2 \times (1!)$.  But, there is a
factorial in the answer.  So, what is $(1!)$?  It is $1 \times (0!)$.
What is $(0!)$?  It is defined as 1. That is where the recursion ``bottoms out".
Thus, $(2!) = 2 \times 1 = 2$.  $(3!)$ is $3 \times (2!) = 3 \times 2 \times 1 = 6$.

     Understanding this recursive approach is necessary in finding the total
number of chances in $s^{n}$ possibilities of
obtaining the total, t, efficiently.


\subsection{Deriving the Solution}

     What are the number of possible rolls, {\em x}, on {\em n} dice with
{\em s} sides which
will yield a total, {\em t}?

     If {\em n} is zero, then the solution is trivial.  All chances are zero.
If {\em n} =
1, then the probability for all {\em x} is 1 chance in {\em s}.  This is important in
establishing the ``bottoming out" level in the recursive approach.  The function
$x(1,s,t) = 1$ where 1 is the number of dice, {\em s} the sides, and {\em t} the total.

     If $n > 1$, then the calculation gets increasingly complex with higher {\em n}'s.
Examine 2 six-sided dice.

     The probability of rolling any total, {\em t}, is equal to the sum of all values
from 1 to $(t-1)$.  It is $(t-1)$ because one cannot roll a zero on a six sided
die.  For those unfamiliar with summations, there is a shorthand notation for
expressing this.  $$x(2,s,t) = \sum_{a=1}^{(t-1)} 1$$

\newpage
In this case, {\em s} = 6 and {\em t} ranges from 2 to 12 (which is $n$ to
$n \times s$).  $$x(2,6,4) = \sum_{a=1}^{3} 1 = 1+1+1 = 3$$
Therefore, the odds of rolling a 4 on 2 six sided dice is 3 in 36.

     To obtain a table of all totals and their respective odds, it is only
necessary to calculate the chances for 2 through 7.  This is due to the
symmetry of the event distribution.  If the total is higher than the ``halfway
point", {\em k}, then it has an equivalent total on the other side of the ``halfway
point".  Thus, if $t > k$, then the equivalent total is $((n(s+1))-t)$ where
$k = \frac{n(s+1)}{2}$ rounded down to the closest integer.

     Notice, however, that the ``1" in the summation expression is, in fact,
{\em x(1,s,a)} = 1.  The example can be rewritten.
$$x(2,6,t) = \sum_{a=1}^{(t-1)} x(1,6,a)$$  This leads to an important extension
of the method to higher numbers of dice.

     If {\em n}, {\em s}, and {\em t} are arbitrary, then\ldots
$$x(n,s,t) = \sum_{a=(n-1)}^{(t-1)} x((n-1),s,a)$$
\ldots provided that the total, {\em t}, is
less than or equal to the ``halfway point", {\em k}.  If $t > k$, then {\em t}
is made to equal $((n(s+1))-t)$.

     There is one further complication to consider.  What if the total, {\em t}, is
greater than the number of dice plus the number of sides on each die minus 1?
Mathematically, what if $(t-s) > (n-1)$?

     Why is this important?  As an example, try to calculate $x(3,6,10)$.  One
may only roll the values 1 through 6 on any single die.  Examine the following
table:

\begin{center}
\begin{tabular}{ccc}
   t = 10 & & \\
         Die \#1 &  Die \#2 + Die \#3  &      \# of possible rolls\\
         Min = 1 &                  9    &                4\\
         2 &                  8    &                5\\
         3 &                  7    &                6\\
         4 &                  6    &                7\\
         5 &                  5    &                8\\
         Max = 6 &                  4    &                9\\
\cline{3-3}
         &&total = 27\\
\end{tabular}
\end{center}

     If one rolls a 2 or a 3 on die \#2 and die \#3, there is no roll on die \#1
that can make a 10.  Thus [1,1], [1,2], and [2,1] are not allowed.  Only the 6
(number of sides) values below $(t-1)$ and above $(t-s)$ can be used.  Therefore,
the lower bound of the summation must be changed to $(t-s)$ if $(t-s) > (n-1)$.

     At last, one has a complete, rule-based, recursive approach to calculate
$x(n,s,t)$ for any $n$, $s$, and $t$.  The rules are as follows:

\begin{enumerate}
\item{Given $n$, $s$, and $t$, find $k = \frac{n(s+1)}{2}$ (round down).}
\item{If $t > k$, then the adjusted $t = ((n(s+1) - t)$.}
\item{If $(t-s) <= (n-1)$ then
     $$x(n,s,t) = \sum_{a=(n-1)}^{(t-1)} x((n-1),s,a)$$}
\item{If $(t-s) > (n-1)$ then
     $$x(n,s,t) = \sum_{a=(t-s)}^{(t-1)} x((n-1),s,a)$$}
\end{enumerate}

     The rules of this recursive method form the basis of the source code of
the computer program DICEROLL.


\section{The Prediction Program}

     DICEROLL is written in C because ``for" loops in C can have variable in the
start, stop, and step values.  This is unlike FORTRAN ``do" loops where they
have fixed values.  C also has built in facilities for making recursive
functions relatively easy to implement.  The program will keep on reducing the
value of n internally on each successive call until it ``bottoms out" at $n = 1$.
Then, it starts adding up all the possibilities.  This does, however, slow the
program down with large values of $n$.  For instance, $50d3$ has over 7.17E+23
(that is 717 followed by 21 zeroes) possibilities.  Even a fast computer slows
to a crawl.

\onecolumn
\begin{verbatim}
     /****************************************************************
  Revision History for Program DICEROLL.C

     $ #1 BY: CONTOMPASIS DATE: 01-APR-1991 Original version
----------------------------------------------------------------------

          MODULE TITLE: DICEROLL

          DESCRIPTION: PROBABILITY CALCULATOR

          WRITTEN BY: JEFFREY CONTOMPASIS   DATE WRITTEN: 01-APR-1991

          READ BY:    JEFFREY CONTOMPASIS   DATE READ:    01-APR-1991

          SUBROUTINES CALLED:

             NAME  - print_error(errcode,errtext)
        USAGE - prints out error messages to standard output

             NAME  - x(n_dice,s_sides,t_total)
        USAGE - recursively calculate chances of rolling
                t_total on n_dice of s_sides

             NAME  - raise(s_sides,n_dice)
        USAGE - raises the value of s_sides to the (n_dice)th power

          FILES:

             NAME  - DICEROLL.C
        USAGE - Source code file (self-sufficient)

          DETAILED
     DESCRIPTION:

         This program takes user input of number of dice, number
         of sides on the dice, and calculates the number of chances
         of rolling a particular total or all totals along with the
         total number of combinations on n s-sided dice.

     The syntax for calling the program is:

     diceroll <return>

     The user will be prompted for all necessary input

     ***************************************************************************
/

     #include <stdio.h>

     /******************************************************************
  print_error(errcode,errtext)

        This procedure prints an error message to standard output

     ********************************************************************/

     void print_error(int errcode, char *errtext)

     {
  switch (errcode)
    {
    case 0: printf("\n%s\n", errtext); /* generic error message           */
            break;                     /* prints error text passed to it. */

         case 1: printf("\nSomething \"%s\" not found\n\n", errtext);
            break;

         case 2: printf("\n%s\n", errtext);
            printf("Syntax is: diceroll <return>\n\n");
            break;

         default:break;

          } /* end case statement */
}


     /*******************************************************************

     raise(s,n)

     Directly calculate the total number of possible combinations
on n s-sided dice

     *********************************************************************/
int raise(int s, int n)
{
  int i, p;
  p = 1;
  for (i = 1; i <= n; ++i)
      p = p * s;
  return(p);
}

     /*******************************************************************

     int x(n,s,t)

     Recursively calculate the number of chances of rolling t
on n s-sided dice.

     *********************************************************************/
int x(int n, int s, int t)
{
int sigma, lower_bound, upper_bound, k, leftside, rightside, a;

     k = ((n*(s+1))/2);

     /* adjust t in case it is in the second half of the
   event distribution.  If it is in the second
   half, it is switched to the equivalent value in
   the first half.  In essence, a mirror image is
   formed by repeating values. */

     if (t > k){
    t = ((n*(s+1))-t);
}

     leftside = (t-s);
rightside = (n-1);

     /* Because t has been forced to be in the first half
of the event distribution, the upper bound is always
one less than the total desired */

     upper_bound = (t-1);

     /* x(1,s,t) is defined as being 1 since it is a linear
   distribution.  It is the "bottoming out" level in
   the recursion.  The lower bound is one less than
   the number of dice rolled provided that none of
   the remaining rolls are greater than the maximum
   possible die roll on any one die.  Otherwise, it
   is the difference between the total desired and
   the maximum die roll. */

     if (n == 1)
    return(1);
else if ((leftside <= rightside)){
        lower_bound = (n-1);
     }
else if ((leftside > rightside)){
        lower_bound = (t-s);
     }
else
        print_error(0,"Error in variables");

     /* reset summation value */
sigma = 0;

     for ( a = lower_bound; a <= upper_bound; a++)
    sigma = sigma + x((n-1),s,a);

     /* send back the total number of chances */
return (sigma);

     } /* end x(n,s,t) */

     /***********************************************************************

     main

     *********************************************************************/

     main()

     {
int option, chances, possibilities, n_dice, s_sides, t_total, all;

     /* get user information */
printf("\n1) Single calculation or 2) Table ? ");
scanf("%d",&option);
printf("\nHow many dice? ");
scanf("%d", &n_dice);
printf("\nHow many sides on each die? ");
scanf("%d", &s_sides);

     /* find the total number of possibilities directly */
possibilities = raise(s_sides,n_dice);

     /* break into the two options */

     if (option == 1){
    printf("\nWhat is the desired total? ");
    scanf("%d", &t_total);
    /* find the total number of chances recursively */
    chances = x(n_dice,s_sides,t_total);
    /* output is the probability outlook */
    printf("\nThe chance of rolling %d on %d, %d-sided dice is ",
          t_total, n_dice, s_sides);
    if (chances == 1)
        printf("%d chance in %d\n", chances, possibilities);
    else
        printf("%d chances in %d\n", chances, possibilities);
}
else {
    /* Print an output header */
    printf("\nTotal on %d, %d-sided dice | Chance of rolling\n",
          n_dice, s_sides);
    /* Reset the value for all possibilities */
    all = 0;
    /* go into a loop from n to n*s */
    for (t_total = n_dice; t_total <= (n_dice*s_sides); t_total++)
    {
    /* find the total number of chances recursively */
    chances = x(n_dice,s_sides,t_total);
    /* output is the probability outlook */
    printf("%20d %20d\n", t_total, chances);
    all = all + chances;
    }
    printf("\nThe sum of all possibilities is %d out of %d\n",
          all,possibilities);
}
}
\end{verbatim}
\twocolumn

\subsection{Sample runs}

     The following output is from actual runs made on a VAX mainframe running
the DICEROLL program.

     The first test is to make sure that a single die produces a linear
distribution of possibilities.

{\small
\begin{verbatim}
1) Single calculation or 2) Table ? 2
How many dice? 1
How many sides on each die? 6
Total on 1, 6-sided dice | Chance of rolling

                   1                    1
                   2                    1
                   3                    1
                   4                    1
                   5                    1
                   6                    1

The sum of all possibilities is 6 out of 6
\end{verbatim}}

     Note that the sum of all possibilities is equal to 6 to the first power.
This is to be expected.  Next, one tries a non-linear or bell distribution.

{\small
\begin{verbatim}
1) Single calculation or 2) Table ? 2
How many dice? 2
How many sides on each die? 6
Total on 2, 6-sided dice | Chance of rolling
                   2                    1
                   3                    2
                   4                    3
                   5                    4
                   6                    5
                   7                    6
                   8                    5
                   9                    4
                  10                    3
                  11                    2
                  12                    1

The sum of all possibilities is 36 out of 36
\end{verbatim}}

     The majority of rolls is in the center portion of the range.  This is to
be expected.  This time the total possibilities is 6 squared.  Higher values of
{\em n} produce similar distributions.

{\small
\begin{verbatim}
1) Single calculation or 2) Table ? 2
How many dice? 3
How many sides on each die? 6
Total on 3, 6-sided dice | Chance of rolling
                   3                    1
                   4                    3
                   5                    6
                   6                   10
                   7                   15
                   8                   21
                   9                   25
                  10                   27
                  11                   27
                  12                   25
                  13                   21
                  14                   15
                  15                   10
                  16                    6
                  17                    3
                  18                    1

The sum of all possibilities is 216 out of 216


1) Single calculation or 2) Table ? 2
How many dice? 4
How many sides on each die? 6
Total on 4, 6-sided dice | Chance of rolling
                   4                    1
                   5                    4
                   6                   10
                   7                   20
                   8                   35
                   9                   56
                  10                   80
                  11                  104
                  12                  125
                  13                  140
                  14                  146
                  15                  140
                  16                  125
                  17                  104
                  18                   80
                  19                   56
                  20                   35
                  21                   20
                  22                   10
                  23                    4
                  24                    1

The sum of all possibilities is 1296 out of 1296
\end{verbatim}}

     Hand calculations confirm that the method is still working.  The hand
calculations, however, took a considerable amount of time.  {\em Jim's Rectangle}
is apparently faster in these cases.  The program can even roll strange dice like
a two sided die.  A coin is an example of such a die.

{\small
\begin{verbatim}
1) Single calculation or 2) Table ? 2
How many dice? 10
How many sides on each die? 2
Total on 10, 2-sided dice | Chance of rolling
                  10                    1
                  11                   10
                  12                   45
                  13                  120
                  14                  210
                  15                  252
                  16                  210
                  17                  120
                  18                   45
                  19                   10
                  20                    1

The sum of all possibilities is 1024 out of 1024
\end{verbatim}}

     The reason for programming in C becomes apparent when one notes the
ability to use almost any number of {\em s}-sided dice.  One does not need to know
the maximum number and size in advance.  However, very large numbers of dice
require recasting the program with ``long int" rather than ``int" for most
variables.  Otherwise, the values will overflow the space allocated them and
produce bizarre results.  The next example took the mainframe about 5 times as
long to complete than the others.  Examine the total number of possibilities,
and the reason becomes clear.

{\small
\begin{verbatim}
1) Single calculation or 2) Table ? 2
How many dice? 6
How many sides on each die? 12
Total on 6, 12-sided dice | Chance of rolling
                   6                    1
                   7                    6
                   8                   21
                   9                   56
                  10                  126
                  11                  252
                  12                  462
                  13                  792
                  14                 1287
                  15                 2002
                  16                 3003
                  17                 4368
                  18                 6182
                  19                 8532
                  20                11502
                  21                15168
                  22                19593
                  23                24822
                  24                30877
                  25                37752
                  26                45408
                  27                53768
                  28                62712
                  29                72072
                  30                81642
                  31                91188
                  32               100458
                  33               109192
                  34               117132
                  35               124032
                  36               129668
                  37               133848
                  38               136422
                  39               137292
                  40               136422
                  41               133848
                  42               129668
                  43               124032
                  44               117132
                  45               109192
                  46               100458
                  47                91188
                  48                81642
                  49                72072
                  50                62712
                  51                53768
                  52                45408
                  53                37752
                  54                30877
                  55                24822
                  56                19593
                  57                15168
                  58                11502
                  59                 8532
                  60                 6182
                  61                 4368
                  62                 3003
                  63                 2002
                  64                 1287
                  65                  792
                  66                  462
                  67                  252
                  68                  126
                  69                   56
                  70                   21
                  71                    6
                  72                    1

The sum of all possibilities is 2985984 out of 2985984
\end{verbatim}}

     Nearly three million possible combinations, and DICEROLL was able to account
for all of them.

\section{Future Work}

     Summing up {\em n} ideal {\em s}-sided dice is relatively easy once the recursive
definition is made.  What about the following problems?

\begin{itemize}

\item Summing up {\em n} ideal {\em s}-sided dice and {\em m} {\em r}-sided dice.
For example, what
is the probability of rolling a 6 on 1d4 and 1d6?  One would have to determine
the ``excluded possibilities" more carefully.  As another example, if the total
desired is 10, there is only one possibility.  Rolling a 5 or less on the d6
prevents the rolling of a total of 10.

\item Summing up {\em n}+1 ideal {\em s}-sided dice and removing the lowest value.  The
classic example is 4d6, take the highest 3.  What is the probability now?  This
is particularly difficult since the assumption of a symmetrical event
distribution is invalidated.  Rolling a 3 on 4d6 (less the low d6) is a 1 in
1296 chance since any roll higher than 1 on any of the 4 dice would knock out a
1.  But, rolling an 18 is a 1 in 216 chance since rolling 3 sixes would
immediately knock out any roll on the last die (even another 6).

\item Summing up {\em n}+{\em m} ideal {\em s}-sided dice and removing the {\em m}
lowest.  The
skewing is  even more acute.  This may be considered a generalized case of \#2.
This method is actually used sometimes in which rolls of primary importance get
the highest value of {\em n}+{\em m}.  For instance, roll 6d6 and throw out the 3 lowest
for a primary attribute.  Roll 5d6 and throw out the 2 lowest for a secondarily
important attribute and so on.

\item Summing up {\em n}+2 ideal {\em s}-sided dice and removing the top and bottom
rolls.  This is somewhat like ``Olympic averaging" in sporting events.  Take the
judges' 7 scores and average the middle 5.  This supposedly eliminates bias for
and against a participant.

\item Summing up {\em n}+{\em m} ideal {\em s}-sided dice and removing the
top {\em i} and bottom {\em j}
rolls where {\em i}+{\em j} = {\em m}.  This is an extension of \#4.

\item Loaded dice.  Determine the skewing from the ideal.  What if all the
dice are loaded in the same way?  What if some ideal dice are mixed in with
some loaded dice?  What if the dice are all loaded in a different way?

\end{itemize}

     That is only a sample of the other probability puzzlers that can arise
while rolling dice.  It might be interesting to see what programs readers of
this article write to solve them.

\newpage

\ \\
\vspace{6in}

\begin{quote}
``\ldots one of those most bizarre of mathematical concepts, a
recipriversexcluson, a number whose existence can only be defined
as being anything other than itself."

\ \ \ --- Hitchhiker's
\end{quote}

\end{document}
