next up previous contents
: Sierpinski like gaskets made : pascal like triangles : How students discovered Pascal   Contents

The mathematical background for Pascal like triangles.

In this section we are going to study the mathematical background of Pascal like triangles.

First we are going to define the Russian roulette game and a mathematically equivalent game.

Definition 1: Let $ p, n, m$ be fixed natural number such that $ m \leq n$. We have players $ \theta_{1}, \theta_{2}, ...,\theta_{p}$ who are seated around a circle. The game begins with player $ \theta_{1}$. Proceeding in order, a partially loaded revolver is passed from hand to hand. The gun has $ n$-chambers and initially $ m$-bullets in them. When a player receives the gun, he points it to himself without spinning its cylinder,and pulls the trigger. If any player gets shot, he is the loser of the game and the game ends.

For some people the Russian roulette is not a good subject to study, and hence the authors present a mathematically equivalent game in Definition 2.

Definition 2: Let $ p, n, m$ be fixed natural number such that $ m \leq n$. We have players $ \theta_{1}, \theta_{2}, ...,\theta_{p}$ who are seated around a circle. The game begins with player $ \theta_{1}$. Proceeding in order, a box is passed from hand to hand. The box contains n numbers. The numbers in the box are assigned in numerical order, from $ 1$ to $ n$. When a player receive the box, he draws a number from the box. The players cannot see the numbers when they draw numbers, and hence they draw at random. Once a certain number was taken from the box, that number will not be returned to the box. If any player gets a number $ x$ such that $ x \leq m$, he will be the loser of the game and the game ends.

From now on the authors are going to use Definition 2 for the game they study in this article.

We denote by $ R(n,m,y)$ the probability of the game ends in the $ y$ th round.

Lemma 1: For natural numbers $ n,m,y$ such that $ y \le n-m+1$ we have

$\displaystyle R(n, m, y) = \left( \displaystyle \prod_{k = 0}^{y-2} \frac{n - (...

...k} \right) \times \frac{m}{n - (y - 1)} = \frac{{}_{n-y} C _{m-1}}{{}_n C _m} .$ (1)

Proof. If the game is to end in the $ y$-th round, the players have to continue the game without becoming the loser from the first round to the $ (y-1)$-th round. The probability to survive the first to the $ (y-1)$-th round are $ \frac{n - m}{n} , \frac{n - (m + 1)}{n - 1}, \dotsb ,\frac{n - (m + y - 2)}{n - (y - 2) }$ respectively and the probability of one of the players loses in the $ y$-th round is $ \frac{m}{n - (y - 1)} $.
Therefore we have (1).
$ \square$
We are going to use the floor function. For any real number $ x$ the function $ \lfloor x \rfloor$ gives the greatest integer less than or equal to $ x$.

Theorem 1: $ F(p, n, m, v) =\sum_{z=0}^{t-1} {R (n, m, v + pz)}= \sum_{z=0}^{t-1} {\frac{{}_{n-v-pz} C _{m-1}}{{}_n C _m}}$ , where $ t = \lfloor \frac{n - m + p - v + 1}{p} \rfloor$.

Proof. Clearly the number of rounds is $ n-m+1$ at most. The $ v$-th player plays the $ v$-th, $ v+p$-th, $ v+2p$-th, $ \dots, v+(t-1)p$-th round, where $ t$ is the biggest natural number that satisfies $ v+(t-1)p \le n-m+1$, and hence
$ t = \lfloor(n-m+p-v+1)/p\rfloor $.
Therefore by Lemma 1
$ F(p, n, m, v) =\sum_{z=0}^{t-1} {R (n, m, v + pz)}= \sum_{z=0}^{t-1} {\frac{{}_{n-v-pz} C _{m-1}}{{}_n C _m}}$.
$ \square$
Definition 3: We define
$ \displaystyle U (p, n, m, v) = \sum_{z=0}^{t-1} {{}_{n - v - pz} C _{m - 1}}$, where $ t = \lfloor \frac{n - m + p - v + 1}{p} \rfloor$.


This number $ U (p, n, m, v)$ is important throughout this article. By Theorem 1 and Definition 3
$ F(p, n, m, v) = \frac{U (p, n, m, v)}{{}_n C _m}$.

Lemma 2:
(1) $ U(p, n, 1, v) = \lfloor\frac{n - v }{p} \rfloor + 1$.
(2) $ U(1, n, m, 1) = {}_{n} C _{m}$.
(3) $ U(p, n, n, 1) = 1$.
Proof. These equations are direct from Definition 3.
(1) $ \displaystyle U (p, n, 1, v) = \sum_{z=0}^{t-1} {{}_{n - v - pz} C _{0}}$
$ = t = \lfloor\frac{n + p - v }{p} \rfloor = \lfloor\frac{n - v }{p} \rfloor + 1$.
(2) $ \displaystyle U (1, n, m, 1) = \sum_{z=0}^{n-m} {{}_{n - 1 - z} C _{m - 1}} = {{}_{n} C _{m}}$.
(3) $ U(p, n, n, 1) = \sum_{z=0}^{0} {{}_{n - 1 - z} C _{n - 1}} = {{}_{n-1} C _{n-1}} = 1$.
$ \square$
In the following Theorem 2 we are going to prove that $ U (p, n, m, v)$ has the property that is very similar to the property of $ {}_n C _m$. To prove this we have only to use the well known formula $ {}_{r} C _{m - 1} + {}_{r} C _{m} = {}_{r + 1} C _{m}$ for each term of $ U (p, n, m, v)$.

Theorem 2: $ U (p, n, m, v) + U (p, n, m + 1, v) = U (p, n + 1, m + 1, v).$

Proof. By Definition 3 we have

$\displaystyle U (p, n, m, v) = \sum_{z=0}^{t_1-1} {{}_{n - v - pz} C _{m - 1}} ,$ (2)

and


$\displaystyle U (p, n, m + 1, v) = \sum_{z=0}^{t_2-1} {{}_{n - v - pz} C _{m}} ...

...\tag{4} \intertext{ where } t_1 = \lfloor(n - m + p - v + 1)/p\rfloor , \tag{5}$ (3)

and


$\displaystyle t_2 =\lfloor(n - (m + 1) + p - v + 1)/p\rfloor t_3 = \lfloor(n + ...

... - pz} C _{m - 1} + {}_{n - v - pz} C _{m} = {}_{n + 1 - v - pz} C _{m}.\tag{8}$ (6)

By (5) and (6) $ t_1 = t_2$ or $ t_1 = t_2 + 1$. We are going to deal with these two cases separately.
(a) If $ t_1 = t_2$ , by (2), (3), (4), (5), (6), (7) and (8) we have
$ U(p,n,m,v)+U(p,n,m+1,v)=U(p,n+1,m+1,v)$.
(b) If $ t_1 = t_2 + 1$, then we have only to prove that the $ t_1$ -th term of (2) is equal to the $ t_1$ -th term of (4), since (3) does not have the $ t_1$ -th term.
By the fact that $ t_1 = t_2 + 1$, we know that $ n-m+p-v+1$ is a multiple of $ p$, and hence we have
$ n-m+p-v+1 = pt_1$.
From this we have
$ n - v - p (t_1 - 1)= m - 1$
and
$ n + 1 - v - p (t_3 - 1)= m$,
which imply that

$\displaystyle \left\{ \begin{array}{l}

{}_{n - v - p(t_1 - 1)} C _{m - 1} = {}_...

...n + 1 - v - p(t_3 - 1)} C _{m} = {}_{m} C _{m} = 1.\tag{9}

\end{array}\right.

$


By (2), (3), (4), (5), (6), (7), (8) and (9) we have $ U (p, n, m, v) + U (p, n, m + 1, v) = U (p, n + 1, m + 1, v).$
$ \square$
Remark. When $ p$ = 2, Theorem 2 was proved by one of the authors (Sakaguchi) when he was a high schoool student. See Sakaguchi, Miyadera and Masuda [3].
Theorem 2 was proved by two of the authors (Minamatsu and S.Hashiba) for any natural number $ p$, when Hashiba was a high school student and Minematsu was a freshman in a university.
Although the teacher (Miyadera) helped them to make a proof, these students could prove the theorem almost by themselves.

By Theorem 2 and Lemma 2 (2) $ U (p, n, m, v)$ can be considered as a generalization of $ {}_n C _m$.
By Theorem 2 for fixed natural numbers $ p, v$ the list { $ F(p, n, m, v) = \frac{U (p, n, m, v)}{{}_n C _m}$, $ m \leq n$ and $ n$ = 1,2,3,...} forms a pattern of fractions that is similar to Pascal's triangle.


next up previous contents
: Sierpinski like gaskets made : pascal like triangles : How students discovered Pascal   Contents