# Pascals triangle given an n sided die

I am struggling with a problem that entails the determination of coin/die probability and pascal's triangle. For a two sided coin/die, if you go to the row equivalent to the amount of flips/rolls, the amount of possible combinations for each possible outcome is specified in that row. For example, if a coin was flipped twice and you were to look at the second row of the triangle you would see 1,2,1, meaning that there is one way to roll HH, two ways to roll HT(TH) and one way to roll TT. With this in mind, the problem asks: "Generate the first ten rows of an equivalent triangle for a three sided die." My first thought would be to generate something that looks like this:

            1
111
122211
1333633311 etc...


But this does not seem correct.

• I have restored the original question content. If you want to ask about non-Euclidean geometry, please do so in a separate question. – Blue May 6 '17 at 12:31

## 3 Answers

I might be wrong, but I believe it has to be a three-dimensional object. Whereas the $i$-th layer in Pascal's triangle is a line segment (the zeroth one is 1, the first one is 1 1, the third one is 1 2 1, etc) of length $i+1$, here each layer will be a triangle.

The zeroth one will be $$1$$ the first one will be $$1\\ 1\ 1$$ the second one will be $$1\\ 2\ 2\\ 1\ 2\ 1$$ etc.

Just to clarify the second layer, if the die has faces labelled $0, 1, 2$, the top $1$ corresponds to the outcome $00$, the two $2$ in the second row correspond to $01$ and $02$, and the third row corresponds to $11$, $12$ and $22$.

And the numbers that appear are, fair enough, the multinomial coefficients.

Hint: You could look at the trinomial triangle which are the coefficients when expanding \begin{align*} (1+x+x^2)^n \end{align*}

The coefficients start with \begin{array}{ccc} &&&1\\ &&1&1&1\\ &\color{blue}{1}&\color{blue}{2}&\color{blue}{3}&2&1\\ 1&3&\color{blue}{6}&7&6&3&1 \end{array}

and each entry is determined by the sum of three entries in the row above. E.g. $$\color{blue}{6}=\color{blue}{1}+\color{blue}{2}+\color{blue}{3}$$

Consecutive throws with a two-sided die can be interpreted as lattice walks in the plane with two possible steps $(1,1)$ and $(1,-1)$. Similarly, throws with a three-sided die correspond to lattice walks in the plane with steps in three directions $(1,-1), (1,0)$ and $(1,1)$.

The solution is a tetrahedron, beginning:

$$1$$ $$1\\11$$ $$1\\22\\121$$ $$1\\33\\363\\1331$$ $$1\\4\;\;4\\6\;\underline{12}\;6\\4\;\underline{12}\;\underline{12}\;4\\1\;\;\;4\;\;\;6\;\;\;4\;\;\;1$$

The $n^{th}$ layer, $j^{th}$ row, $k^{th}$ entry is the coefficient of:

$$x^jy^{k-j}z^{n-k}$$

in

$$(x+y+z)^n$$

and obey the recurrence relation:

$$\operatorname{Trin}(j,k,n)=\operatorname{Trin}(j-1,k,n-1)+\operatorname{Trin}(j,k-1,n-1)+\operatorname{Trin}(j-1,k-1,n-1)$$

In closed form:

$$\operatorname{Trin}(j,k,n)=\binom{n}{j}\binom{j}{k}$$