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

\title{A Method for the Derivation of \\ Constrained Number Probabilities}
\author{\copyright1990 Jim Vassilakos}
\date{jimv@ucrmath.ucr.edu}
\maketitle
\setcounter{page}{4}

{\it \noindent
{\Large I}t is often amusing and occasionally indicting to see just
how high (or low) on the scales of fortune a character's prime statistics
stack-up against the unassailable laws of probability. This article
provides a method by which evidence of ``luck'' or {\em what-have-you}
might be gathered.\\}

{\noindent \Large The General Problem\\}

{\noindent G}iven that we roll {\em n} number of {\em s}-sided dice
(notated as {\em n}d{\em s}), what is the probability distribution
of {\em y} such that {\em y} is the total value of {\em n}d{\em s}.\\

{\noindent \Large Act I \ \ --- \ \ Pascal's Triangle\\}

{\noindent W}e start by making fun of Pascal's infamous {\Large $\bigtriangleup$}\\

{\large
\begin{center}
\begin{tabular}{lccccccccccccccccc}
0 &    &&&&&&&&1&&&&&&&&\\
1 &    &&&&&&&1&&1&&&&&&&\\
2 &     &&&&&&1&&2&&1&&&&&&\\
3 &     &&&&& 1&&3&&3&&1&&&&&\\
4 &     &&&&  1&&4&&6&&4&&1&&&&\\
5 &     &&&   1&&5&&10&&10&&5&&1&&&\\
6 &     &&    1&&6&&15&&20&&15&&6&&1&&\\
7 &     &  1&&7&&21&&35&&35&&21&&7&&1&\\
8 & \ \ \ \ \ \ \ \ 1&&8&&28&&56&&70&&56&&28&&8&&1 \\
\end{tabular}
\end{center}}

Well, it looks something like that anyway. The numbers along the
left-hand side indicate the rank of the row (i.e. row \#3 contains
the values 1, 3, 3, and 1). The value of n (the number of dice we
are rolling) indicates the row number of pascal's triangle we are
concerned with.

Suppose we are interested in finding the probability distribution
of 3d6. We will need to consider the values 1, 3, 3, and 1. Once
we have these values, we need to let every 2nd value in the series
become its own opposite. Thus, we are now considering the values
1, -3, 3, and -1.

{\noindent \Large Act II \ \ --- \ \ Jim's Rectangle\\} 

{\noindent N}ow that we're done with pascal's triangle (yawn\ldots boring),
it's time to introduce jim's parallelogram! Hazzah! Hazzah!
Jim's what????! Well, it began as a parallelogram, then it
devolved into a rectangle because Jim was (and still is) such
a messy dude that he couldn't keep his diagonal lines straight.
But as they say in the Conan `flics, that's a ``whole {\em 'nother}
story.'' Anyhow, suffice it to say that Act Two makes Act One look
like a lame teaser. O'course, if I went into half the other probs
pascal's triangle sets the stage for solving, Act One would be a
full-length creature-feature in and of itself with pop corn and
a free diet soft-drink and plenty of blood and gore and dead
teenagers to boot. Pascal\ldots what a dude.

\vspace{2.4in}
Anyways, where were we? Oh, I `member, Jim's rectangle. Okay,
here we go\ldots Jim's rectangle (abbreviated as ``Monster" for
short) is the method by which we arrive at the top-half of
what I'll call the events-distribution for {\em n}d{\em s}. The horizontal
axis is n+1 cells long. The vertical axis is k-n+1 cells long
where k = $\frac{n(s+1)}{2}$ and is rounded down to the nearest whole number. 
%
\newpage
So for our example of 3d6, n=3 and s=6.

\begin{tabbing}
k \= = $\frac{3(6+1)}{2}$ (round down)\\
  \> = 10.5 (round down)\\
  \> = 10
\end{tabbing}

\begin{tabbing}
h.a. (horizontal axis) \= = 3+1 = 4\\
v.a. (vertical axis)   \> = 10-3+1 = 8
\end{tabbing}

So far, so awful. Here's what our lovable monster looks like just in
terms of where the cells are placed.

\begin{center}
\begin{tabular}{cccc}
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ \\
\end{tabular}
\end{center}

Now we've got to make the axes, one along the top and one along
the right-hand side. Note, these axes are a part of the actual
monster. The horizontal axis is composed of the cells of the
top-most row. The vertical axis is composed of the cells of the
right-most column. We let all the cells of the horizontal axis
carry the value 1. Next, we let all the cells of the vertical axis
carry the value 0. Certain cells of the vertical axis are then
modified (every sth cell starting from the top-right corner to
be precise). Isn't this fun? Now you know why I call it the
monster. Every sth cell (6th cell for 3d6 purposes), gets to
carry one of those values from Act One. See? Pascal wasn't
foolin' when he said his triangle would be important!

Our nth (3rd) row values (every 2nd reversed) turned out to be
1, --3, 3, and --1. We deposit value \#1 into cell \#1 of the
vertical axis. What do you know? It just ``happenstanced" to be
a one. That fits nicely with the horizontal axis. We then stuff
value \#2 (in this case a -3) into the cell {\em s} (6) places down.
That would make cell \#7 go from 0 to --3. And so the story goes
on and on until you're either out of values or you run out of
places to stuff them. The latter case will invariably proceed
the former. Thus, if you followed half of that, we get a
monster looking like this\ldots

\begin{center}
\begin{tabular}{cccc}
1 &  1 &  1 &  1 \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  0 \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  0 \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  0 \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  0 \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  0 \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ & --3 \\
$\heartsuit$ &  $\heartsuit$ &  $\heartsuit$ &  0 \\
\end{tabular}
\end{center}

Neato burrito! Now it's time for the hot sauce.

You take each empty cell in the matrix and let its value equal
the sum of the value in the cell above and the value of the cell
to the right. In other words:

\begin{picture}(200,50)
%                                      a
%       v = a + r     ------------->   v  r
\put(25,30){v = a + r}
\put(75,32){\vector(1,0){50}}
\put(135,25){v \ r}
\put(135,35){a}
\end{picture}

Now we just fill in the numbers...

\begin{center}
\begin{tabular}{cccc}
1  & 1 &  1 &  1 \\
3  & 2 &  1 &  0 \\
6  & 3 &  1 &  0 \\
10  & 4 &  1 &  0 \\
15  & 5 &  1 &  0 \\
21  & 6 &  1 &  0 \\
25  & 4 & --2 & --3 \\
27  & 2 & --2 &  0 \\
\end{tabular}
\end{center}

And that's how we get jim's rectangle (aka: the monster).\\

{\noindent \Large Act III \ \ --- \ \ Pulling Probabilities \\}

{\noindent O}kay, now the easy part. The values in the left-hand column
represent the first half of our events-distribution (Actually, this
is incorrect. They actually represent the number of constrained, ordered
partitions, but this is too much of a mouthful, so to
translate everyone's conflicting jargonese, they represent the number of times
you'd get a particular total y, if you rolled {\em n}d{\em s} $s^{n}$ times
such that you got each possible combination once.)

Here they are, just for fun\ldots 1, 3, 6, 10, 15, 21, 25, 27.

I'll illustrate the ``brute force" method using 2d6 just to
show you the value of the monster.

With 2d6, there are 36 ($6^{2}$) possible combinations. One
representation of those combinations might be as follows:

\begin{center}
\begin{tabular}{cc|cccccc}
&&\multicolumn{6}{c}{Die \#1}\\
     &    &  1 & 2&  3&  4 & 5 & 6\\
\hline
     & 1  &  2 & 3 & 4&  5 & 6 & 7\\
     & 2  &  3 & 4 & 5&  6 & 7 & 8\\
 Die & 3  &  4 & 5 & 6&  7 & 8 & 9\\
 \#2 & 4  &  5 & 6 & 7&  8 & 9 &10\\
     & 5  &  6 & 7 & 8&  9 &10 &11\\
     & 6  &  7 & 8 & 9& 10 &11 &12\\
\end{tabular}
\end{center}

This, then is the events-distribution map. From here we can see
how many times we get a particular total or event.

\begin{center}
\begin{tabular}{cc}
     Total &   Events \\
       2   &     1 \\
       3   &     2 \\
       4   &     3 \\
       5   &     4 \\
       6   &     5 \\
       7   &     6 \\
       8   &     5 \\
       9   &     4 \\
      10   &     3 \\
      11   &     2 \\
      12   &     1 \\
\end{tabular}
\end{center}

What's the chance of getting an 8? 5 events out of 36 possible
combinations = $\frac{5}{36}$, or to restate it p(y=8$\mid$y=yield(2d6)) = 
$\frac{5}{36}$.

With 3d6, you've got to extend the number of possible combos
into a 3rd dimension\ldots kind of hard to show you right now.
Instead of having $6^{2} = 36$ possibilities, we have $6^{3} = 216$
possibilities; the bigger your n, the yuchier it gets.

As it turns out (especially with high n's), making the monster
and pulling the values off his left arm is much easier than the
brute force technique. We've already made monster. Now I'll show
you how to pull the values out.

First of all, we've got to figure out what the smallest and
largest value totals can be, and that's pretty easy. Our
smallest possible total is {\em n}, the largest in $n \times s$.
For 3d6 that equates to a range between 3 and 18. 

We can start at either extreme and just move toward the midsection.
Once we get half the distribution done, we just make the other
half a mirror reflection of what we've done, starting from the
other extreme and moving in. As a sidebar, there are times when
we won't need to copy the lower left-hand value and other times
when we will. It all depends on whether the number of possible
totals is odd or even. Here's what our 3d6 events distribution
looks like.

\begin{center}
\begin{tabular}{cc}
     Total  &  Events\\
       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 \\
\end{tabular}
\end{center}

So there's only a $\frac{21}{216}$ chance of getting an 8 on 3d6.

Of course, it's always a good idea to check your events-distribution,
and one easy way to do that is to total the number of events. If they
do not equal $s^{n}$ (in this case $6^{3} = 216$), then you know you've got a
loser. This is not to say that this check will knock out all losers,
but its a good check anyway. \\

{\noindent \Large The Programs\\}

{\noindent W}hat follows are two programs written in GW-Basic for the IBM-PC.
The first runs a simulation of nds and the second runs monster's
analysis. As a footnote, the {\em fix} command is used to round
numbers down. Most {\em int} commands will do this, but not all so
watch out if you decide to substitute. In reality (at least as
far as I perceive it), {\em fix} rounds all numbers toward zero
(negatives includes). Since these programs should never provide
{\em fix} with negative numbers, the point is moot\ldots but happy
nevertheless. As another note, many versions of basic will stick
an exclamation point at the end of large (or is it long?) numbers
in the expressions (for example, lines 725 in both programs, the
number 1000000 becomes 1000000!. Don't be too alarmed if your
basic does this. Apparently for some odd reason, it's normal. 
Anyway, here we go\ldots \\


{\noindent \Large The Simulation Program\\}


{\noindent U}sing all the versions of basic, fortran, and pascal I've
ever had the conspicuous pleasure of trying out, it is
just plain impossible (well\ldots at least not very easy) to write
a dice-simulation program
which covers the general case {\em n}d{\em s} because {\em n} determines
the number of nested loops
necessary to conduct the simulation, and all these
languages don't allow for this number to be variable. In
other words, you can't say, "Hey youze guyz... I want fifty
nested loops, now do it." Y'see, the computers got together
and formed a union and decided they didn't have to take that
sort of cr$\ast$p.

So, here's what we've got; we've got a simulator which only
does its job for n$\leq$10. Bummer! \\

\begin{verbatim}
5 DIM C(100)
6 DIM P(100)
10 PRINT"DICEY.SIM: THE DICE SIMULATOR BY JPV"
30 PRINT"WHAT'S P(Y=>X: Y=YIELD(NDS), N=\# OF DICE, S=SIDEDNESS)?"
70 INPUT"ENTER N,S,X:";N,S,X
100 REM ROLL 'EM!
110 FOR A1=1 TO S
115 IF N=1 GOTO 300
120 FOR A2=1 TO S
125 IF N=2 GOTO 300
130 FOR A3=1 TO S
135 IF N=3 GOTO 300
140 FOR A4=1 TO S
145 IF N=4 GOTO 300
150 FOR A5=1 TO S
155 IF N=5 GOTO 300
160 FOR A6=1 TO S
165 IF N=6 GOTO 300
170 FOR A7=1 TO S
175 IF N=7 GOTO 300
180 FOR A8=1 TO S
185 IF N=8 GOTO 300
190 FOR A9=1 TO S
195 IF N=9 GOTO 300
200 FOR A10=1 TO S
300 REM 
310 D=A1+A2+A3+A4+A5+A6+A7+A8+A9+A10
320 C(D)=C(D)+1
410 IF N=1 GOTO 600
420 IF N=2 GOTO 590
430 IF N=3 GOTO 580
440 IF N=4 GOTO 570
450 IF N=5 GOTO 560
460 IF N=6 GOTO 550
470 IF N=7 GOTO 540
480 IF N=8 GOTO 530
490 IF N=9 GOTO 520
510 NEXT A10
520 NEXT A9
530 NEXT A8
540 NEXT A7
550 NEXT A6
560 NEXT A5
570 NEXT A4
580 NEXT A3
590 NEXT A2
600 NEXT A1
700 REM TOTALS
702 PRINT
705 PRINT"SUM          EVENTS            PROBABILITY"
710 FOR B=N TO N*S
720 P(B)=C(B)/(S^N)
725 P(B)=INT(P(B)*1000000)/10000
750 PRINT B;"         ";C(B);"           ";P(B);"%"
770 NEXT B
800 REM P(Y=>X)
810 FOR B=X TO N*X
820 Z=Z+P(B)
830 NEXT B
840 PRINT
860 PRINT"P(Y=>";X;") =";Z;"%"
870 PRINT
1000 END
\end{verbatim}

\vspace{.2in}
{\noindent \Large The Monster Program\\}

\begin{verbatim}
5 DIM T(20,20)
6 DIM C(50,50)
7 DIM E(100):DIM P(100)
10 PRINT"MONSTER: DICE PROBABILITY ANALYZER BY JPV"
20 PRINT"WHAT'S P(Y=>X: Y=YIELD(NDS), N=\# OF DICE, S=SIDEDNESS)?"
30 INPUT"ENTER N,S,X:";N,S,X
100 REM CONSTRUCT PASCAL'S TRIANGLE
110 T(0,1)=1
120 FOR A=1 TO N
130 FOR B=1 TO A+1
140 T(A,B)=T(A-1,B-1)+T(A-1,B)
160 NEXT B
170 NEXT A
180 FOR A=1 TO N+1
190 IF A/2=FIX(A/2) THEN T(N,A)=T(N,A)*(-1)
210 NEXT A
300 REM CONSTRUCT AXES OF MONSTER
310 FOR A=1 TO N
320 C(A,1)=1
330 NEXT A
340 D=FIX(N*(S+1)/2)+1-N
350 FOR B=1 TO D
360 C(0,B)=0
370 IF (B-1)/S=FIX((B-1)/S) THEN C(0,B)=T(N,((B-1)/S)+1)
380 NEXT B
400 REM NOW THE HOT SAUCE
410 FOR A=2 TO D
420 FOR B=1 TO N
430 C(B,A)=C(B-1,A)+C(B,A-1)
440 NEXT B
450 NEXT A
490 GOTO 600
500 REM SHOW MONSTER
510 FOR A=1 TO D
515 FOR B=N TO 0 STEP -1
520 PRINT C(B,A);
530 NEXT B
535 PRINT
540 NEXT A
600 REM CONSTRUCT EVENT & PROBABILITY DATA
610 FOR A=1 TO D
620 E(A+N-1)=C(N,A)
630 P(A+N-1)=E(A+N-1)/(S^N)
640 E(N*(S+1)-A-N+1)=E(A+N-1)
650 P(N*(S+1)-A-N+1)=P(A+N-1)
660 NEXT A
700 REM GO PERCENT WITH THE PROBS
710 FOR A=N TO N*S
725 P(A)=INT(P(A)*1000000)/10000
730 NEXT A
799 GOTO 900
800 REM PRINT PROB CHART
801 PRINT
805 PRINT"SUM        EVENTS         PROBABILITY":PRINT
810 FOR A=N TO N*S
820 PRINT A;"        ";E(A);"         ";P(A);"%"
830 NEXT A
900 REM P(Y=>X)
910 FOR A=X TO N*S
920 Z=Z+P(A)
930 NEXT A
940 PRINT:PRINT"P(Y=>";X;") =";Z;"%"
950 PRINT
1000 END
\end{verbatim}

Just some additional notes on the programs\ldots

Unlike our three-act solution which finds the probability of
totaling a specific value on {\em n}d{\em s}, these programs go an extra
step and find the probability of totaling a particular value
or getting above that value. Sounds a lot like the p-value in
Statistics, come to think of it. The reason the programs were
designed to do this relates more to my specific application
than to any idle theory (yes\ldots I'm doing all this for a
reason). If you want to see the full process as per the
three-act solution, just delete lines 490 and 799 from
monster, and it'll show you the whole speel of how it's
getting what its getting. If ``out of range" errors start
cropping up, you may have to extend the variable dimensions,
but other than that, the progs should work just fine. As
a final sidenote, beware that for high {\em n}'s the simulation
program will get real slow. Just a little warning there.
For the time it took to get an answer, it really didn't
make sense to extend the $n\leq10$ constraint. Anyways, that's
all she wrote, or rather that's all he wrote, it being
the case that it is. So long\ldots\\

{\noindent \Large End of Chapter Questions:}

\ \ \ {\em (hee\ldots hee\ldots hee\ldots)}

\begin{enumerate}
\item{Does it work?}
\item{Why or why not?}
\item{Is there an easier method than monster?}
\item{Has this ever been shown before, and if so, where?}
\end{enumerate}

\vspace{3in}

\begin{quote}
``Sometimes I think I learn more when I stay home from school."

\begin{tabbing}
\ \ \ --- \=Dave Nadler\\
\>{\em dnadler@ms.uky.edu}\\
\>University of Kentucky\\
\end{tabbing}
\end{quote}

\end{document}
