Jacob Ballou

Math 307

4/3/2019

Pascal’s Triangle and Generalized

M-Simplex Numbers
Pascal’s Triangle is a fascinating construct with applications in many areas of mathematics, from

Combinatorics to Algebra to the study of fractals. Its beautiful emergent properties may be

demonstrated via the proof that:

For any positive M, Diagonal D M of Pascal’s Triangle contains the Simplex Numbers of

dimension M.

Obtaining a sequence of Simplex Numbers is useful to the field of Combinatorics because the

M
simplex numbers of dimensionality M are equivalent to the binomial coefficient Sn = (
(n+ ( M −1 ))
M
, )
M
where Sn is the nth simplex number. Solving R-Combination problems algebraically can be

( )
N = N!
computationally expensive due to the use of three factorials in the formula . Factorials
r r ! ( N−r ) !

have exponential time complexity, making solving them demanding.

The numbers in Pascal’s Triangle, and thus the N-Simplicial numbers, while initially expensive to

compute, may be stored as arrays for later reference. Arrays are lists of lists that contain values or

objects and specify position via one or more indices. For example, if one were to retrieve the 4 th entry

from the 6th column of a two-dimensional array, one would specify “myArray [3][5]”. Pascal’s Triangle,
and thus the simplex numbers, may be stored in a two-dimensional array, letting us reduce the time

complexity for solving an R-combination problem to O(n 2) rather than O(2n ).

Definitions

Triangular numbers are numbers T i=N such that one can arrange N vertices in a regular triangular grid

of side length i. The most common example of this kind of grid is the way a bowling alley sets up its pins.

The smallest triangular number is T 1=1. T 2=3, T 3 = 6, and T 4=10 . The respective arrangements

are shown below, in figure 1.

n
Notably, triangular numbers are sums of natural numbers such that T n=∑ i .
i=1

For example, T 5 is 15, which is equal to (1+2+3+4+5).

Fig. 1

3
Tetrahedral numbers are numbers Si =N such that N vertices may be arranged into a

tetrahedron of side length i. The pyramidal pattern that cannonballs are stacked in is a well-known
example. These arrangements have a triangular base, and any layer of the stack will also be triangular.

3
This property is shown in figure 2. From this, one can conclude that any given tetrahedral number Sn is a

summation of the triangular numbers such that S =∑ T i .

3
n
i=1

Fig. 2

A simplex is a generalized shape possessing any number of spatial dimensions, resembling a

triangle or tetrahedron, and having the least amount of corner vertices possible for its dimensionality

(The minimum number of points required to fill a hypervolume of dimensionality M is M + 1). The most

common Simplices encountered in day-to-day life, the triangle and tetrahedron, have dimensionalities

of two and three respectively. The point and line are Simplices of dimension zero and one, but these are

trivial examples. Figure 3 shows a simplex of dimensionality 4, projected into 3-dimensional space. The

red point is the simplex’s 5th vertex. A simplex of dimensionality M may also be constructed by stacking

simplices of dimensionality M-1.

 Fig. 3

We know that the Nth triangular number is the sum of nonzero integers from 1 to N. We also

know that the Nth tetrahedral number is the sum of the triangular numbers from 1 to T n. However, we

must prove a similar case for all simplicial numbers, of all dimensionalities. In sections 1 and 2 of my

proof, “size” refers to the cardinality of the M-simplex, and thus the number of vertices per edge (the

first M-simplex has size 1, the second has size 2, and so on).

1) Proof that the Nth M-simplicial number is the sum of the first N M-1

simplicial numbers

Any slice of a simplex of M spatial dimensions parallel to that simplex’s face will contain an (M-

1)-dimensional simplex which is geometrically similar to that face. Slicing an M-simplicial arrangement of

points parallel to its base yields an (M-1)-simplicial arrangement of points, of size proportionate to the

slice’s distance from the M-simplex’s vertex point.

By definition there must be an M-simplicial number of points to form an M-simplicial arrangement. An

(M-1)-dimensional slice of that M-simplex is an (M-1)-simplicial arrangement of points, and contains an

(M-1)-simplicial number of points by definition. Therefore, an M-simplicial number is a sum of M-1

simplicial numbers.

Since the Nth M-simplex has all side lengths equal to N, it’s face will be a simplex of M-1 dimensions but

will also be of side length N.

Since the M-simplex begins with a vertex and ends with a face, and by definition it’s edges directly

connect the vertex to the opposite face, any slice of the M-simplex will be less than or equal to the face

in size. Furthermore, since the vertex and face are connected by straight lines, the slices will have an

edge length directly proportionate to their distance from the vertex. Therefore, since the vertex is of

size 1, and the face is of size N, the slices increase in size from 1 to N.

Any slice contains an (M-1)-simplicial number of points, and the M-simplex contains an M-simplicial

number of points, so the Nth M-simplicial number is proven to consist of the sum of the first N

(M-1)- simplicial numbers.

2) Proof that the Nth M-simplicial number is the sum of the (N-1)th M-

simplicial number and the Nth (M-1)-simplicial number

The (N-1)th M-simplicial number is the sum of the first (N-1) (M-1)-simplicial numbers by definition. If

added to a “base” consisting of the Nth (M-1) simplicial number, the sum will be the sum of the first N

(M-1) simplicial numbers. As proven above, this means that the sum is the Nth M-simplicial number.
 Now that we have proven that the M-simplicial numbers are sums of (M-1) simplicial numbers, and

that the Nth M-simplicial number is the sum of the (N-1)th M-simplicial number and the Nth (M-1)-

simplicial number, we can proceed with the proof that:

3) The Mth diagonal of Pascal’s triangle contains the simplex numbers for a

simplex of dimension M, by Induction

Let us denote Diagonal M of Pascal’s triangle as D m . Due to the inherent symmetry of Pascal’s triangle,

there is no need to distinguish between the diagonals aligned from top-left to bottom-right and the

diagonals aligned from bottom-left to top-right.

The 4th property of the binomial coefficient is that ( NR+1)=( R−1 ) ( R ). Pascal’s triangle follows this
N + N

rule, so that any number within the triangle is equal to the sum of the two numbers above it.

Base cases

A given number in either of the 0th diagonals has less than two numbers above it. As such, we count the

absent number as a zero.

3a) Proof that the 0th diagonal consists entirely of ones:

The 0th number of D 0 is 1.

Any Nth number in D 0 is the sum of 0 and the (N-1)th number in D 0 by the 4th property of the

0
binomial coefficient. Thus, since the base case, D 0 = 1, all numbers in diagonal D 0 are equal to 1 by

0
induction. Furthermore, because Pascal’s triangle is symmetrical, D M equals 1 for any nonnegative M.

3b) Proof that the 1st diagonal consists of the positive integers
As proven in section 3a), D M equals 1 for any nonnegative M. Thus, D 1=1 .
0 0

Any Nth number in D 1is the sum of the Nth number in D 0 and the (N-1)th number in D 1 by the 4th

property of the binomial coefficient.

(n−1 )
Since D 0 consists entirely of ones, the Nth number in D i is equal to ( D 1 +1). By induction, D1

consists of the positive integers.

3c) Proof that the 2nd diagonal consists of the triangular numbers

As established in section 3a), the 0th number of D 2 is equal to 1. Any Nth number in D 2 is equal to

(n−1 ) n
D2 + D 1 by the 4th property of the binomial coefficient.

n
Since we proved that D 1=n in section 3b), the Nth number of D 2 is equal to the (N-1)th number + N.

0 0
Since Pascal’s triangle is symmetrical, D M equals 1 for any nonnegative M. Thus, D 2 equals 1.

n
By induction, D 2 is equal to the sum of the first N natural numbers. This fits the definition of the

n
triangular numbers, meaning that D 2 gives the Nth triangular number.

3d) Proof that the 3rd diagonal consists of the tetrahedral numbers

0 0
As proven in section 3a), D M equals 1 for any nonnegative M. Thus, D 3 equals 1.

(n−1 ) n
Any Nth number in D 3 is equal to D 3 + D 2, by the 4th property of the binomial coefficient.

In section 2), we proved that the Nth M-simplicial number is the sum of the (N-1)th M-simplicial number

and the Nth (M-1)-simplicial number. Since the 1st M-simplicial number is 1 for any non-negative M, and

n n
D2 is the Nth triangular number as proven in section 3c), D3 is the Nth tetrahedral number by

induction.
 3) Proof that the Mth diagonal consists of the M-simplicial numbers

By the 4th property of the binomial coefficient, ( NR+1)=( R−1 ) ( R ).

N + N

(N−1) N
Pascal’s triangle follows this rule. Thus, if D M is the (N-1)th M-simplicial number, D M will be the sum

N
of that number and D (M −1) .

n 0
Since Pascal’s triangle is symmetrical and D 0 = 1, D M equals 1 for any nonnegative M. Since the

0
sequence of M-simplicial numbers begins with 1, for all non-negative M, D M is an M-simplex number.

As proven in section 1, the Nth M-simplicial number is the sum of the (N-1)th M-simplicial

number and the Nth (M-1)-simplicial number.

Thus, by induction, if D (M −1) is proven to consist of the (M-1)-simplicial numbers, D M is the sum
N

of the first N (M-1) simplicial numbers.

N N
Since D 2 and D 3 are proven to consist of the 2-simplex numbers and 3-simplex numbers,

respectively, we have repeatedly confirmed that the base case is true.

N
Thus, by induction, D M is proven to be the Nth M-simplicial number, and D M

Is proven to be the sequence of M-simplicial numbers.

Implications of the proof

While this proof is somewhat long and unwieldy, it showcases a beautiful emergent property of

Pascal’s triangle. In addition to demonstrating the kind of elegance found within the rules of

mathematics and logic, this property also provides an easy way to solve combinatorics problems with
very large terms, either computationally or by hand. While calculating the values in Pascal’s triangle is

certainly resource-intensive, storing them and retrieving them is not. By calculating the values of

Pascal’s triangle beforehand and storing them in an array, we can reduce the resource-intensive process

of finding an algebraic solution to the relatively simple process of looking up the value in a table. Since

the simplex numbers of dimensionality M are equivalent to the binomial coefficient,

( )
Sn = (n+ ( M −1 )) , we can simply choose values of N and M that fit the coefficient we are
M

trying to solve. We are already given M as the lower term of the unsolved coefficient, and we can find N

by subtracting (M-1) from the upper term. Once we have N and M, all we need to do is access myArray

[M][N], and we have the solution, all with a time complexity of O(N ¿¿ 2)¿, even for extremely large

coefficients.

Sources:

http://oeis.org/wiki/Simplicial_polytopic_numbers