Pascal's Pyramid Or Pascal's Tetrahedron? 

By Jim Nugent lastnamefirstinitial at ameritech.net This is a copyrighted document. The text, charts, graphs and illustrations are covered by various copyrights 

ABSTRACTA lattice of octahedra and tetrahedra (octtet lattice) is a useful paradigm for understanding the structure of Pascal's pyramid, the 3D analog of Pascal's triangle. Notation for levels and coordinates of elements, a standard algorithm for generating the values of various elements, and a ratio method that is not dependent on the calculation of previous levels are discussed. Figures show a bell curve in 3 dimensions, the association of elements to primes and twin primes, and the values of elements mod(x) through patterns arranged in triangular plots. It is conjectured that the largest factor of any element is less than the level index. This 22K article contains illustrations and animations that are quite large. These files can take a few minutes to download if you access the Internet with a modem or slow connection. 

Pascal's Pyramid Or Pascal's Tetrahedron?I. Introduction 


In a 1966 Scientific American column, Martin Gardner mentions in passing that there are, ". . . endless variants
on the [Pascal's] triangle, and many ways to generalize it, such as building it in tetrahedral form to give the
coefficients of trinomial expansions." One of the illustration of Pascal's triangle, included with that article shows the first 100 rows of the triangle with odd and even numbers represented as dots. The pattern of dots representing odd and even numbers in the two dimensional Pascal's triangle correspond to the octahedral and tetrahedral sections of an octtet lattice (see figures 1 and 2). The octahedron faces of the lattice map to the even dots while the tetrahedron faces map to the odd dots. 

If we construct a three dimensional Pascal's triangle will the distribution of odd and even values for the elements
in the interior correspond to the octahedral and tetrahedral components of an octtet lattice? A Galton board simulation, rolling marbles through a triangular maze, generates values that approximate the values of coefficients of a binomial expansion. At each fork in the maze the marble has a 5050 chance to go either way until it falls into bins at the bottom of the maze in proportions that roughly approximate a bellshaped curve. The Galton Board can be simulated with a computer program that is a variation of the one used to generate the 3D analog of Pascal's triangle. 
II. PrecursorsStephen Mueller published a paper in 1969 on Recursions Associated With Pascal's Pyramid. In Mueller's definition, "Pascal's pyramid is the threefaced pyramidal array of coefficients in the expansion of the trinomial, (a+b+c)^{j}, such that the coefficients of (a+b+c)^{j} are systematically placed beneath those of (a+b+c)^{j1}, resulting in a Pascal triangle on each of the three faces." Mueller labels the initial plane, containing one term, as level 0 (see figure 3) which turns out to be a good choice of notation. Terms on higher levels are expressed as the product of two binomial coefficients. 

John Staib and his son Larry published The Pascal Pyramid in 1978. Like Mueller, the Staibs also used a stack of successively larger triangles to form a pyramid (seefigure 3). They developed a coordinate notation for each point on each triangular level, a system for determining which of the small triangles were centered above a point on the next level, that the sums of the trinomial coefficients associated with the vertices of an upper triangle were equal to the trinomial coefficient found directly below that triangle, that a trinomial expansion could be generalized from a binomial expansion and that a BASIC computer program could be written to generate the coefficients of (x+y+z)^{n} in the form of layers of a pyramid. In a 1938 book, Steinhaus gives a short example of a method of determining winners in a three way election with a similar notation except that he breaks the triangle into hexagonal cells.  
In 1986, Bollinger attempted to lay pyramid power to rest with, "It would seem that in spite of the appeal of an array for multinomial coefficients similar to the triangle for binomials, one is better off for most purposes using a convenient algorithm to generate the mpart compositions of n, from which the exponents on the x_{i} and the multinomial associated with a given term are immediately available." III. The Proper ParadigmTwo key concepts needed for a clearer understanding of the 3D analog of Pascal's triangle are missing from these earlier works. 

Figure 4 
First, the octahedrontetrahedron lattice is a more accurate 3D analog for the 2D Pascal's triangle. A triangular base pyramid is descriptive of outward shape but lacks any ability to illuminate the interconnectedness of multiple subdivisions. The levels of the 3D analog of Pascal's triangle are connected by an octahedrontetrahedron lattice. Some of the tetrahedra are oriented with a point up and some with a face up (see figure 4). Loeb states it clearly: (Link to standalone OctahedronTetrahedron Animation (figure 4)) "It is not possible to fill space with regular tetrahedra [or pyramids] only; four tetrahedra and an octahedron are necessary to produce a tetrahedron having eight times the volume (twice the linear dimension) of the original tetrahedron." In order to fill space octahedra are used in combination with tetrahedra (see figure 1). Subdividing the pyramid into these two components makes it a simple task to model the 3D analog of Pascal's triangle. 
Secondly, Pascal's pyramid (or tetrahedron) can be modeled with ordinary Cartesian coordinates. A tetrahedron is pointforpoint congruent to a cubecorner (see figure 5). If you visualize the X, Y, and Z axes as the three legs of a collapsible photo tripod, the transformation from cube corner to octtet lattice is as like changing the angle between legs from 60 to 90 degrees. As you raise the tripod the legs get longer but the angles between them grow more acute.  
IV. The OctahedronTetrahedron LatticeLike Bollinger [6], Staib and Staib [4] state that, ". . .the threedimensional nature of the Pascal pyramid makes it awkward to use for hand calculating the trinomial coefficients." Staib and Staib [4] and Mueller [3] both use illustrations of pyramids containing planes and levels with no interconnections between levels. Drawing a tetrahedron, let alone a subdivided tetrahedral lattice can be hard. Without actual physical models it can be daunting to visualize how tetrahedra in combination with octahedra might provide the needed paradigm for interconnecting the pyramid's levels (see figure 3 and 4). Octtet lattices are also harder to picture in twodimensioned figures and illustrations because most of our drawing conventions are based on viewing cubic forms. Looking for patterns among 2 or 3 thousand forty digit numbers is not easy work. "Computer graphics is an excellent method by which patterns in Pascal's pyramid can be made obvious to both the mathematician and interested layperson," according to Pickover and Khorasani . The figures in the following sections are computer generated visualizations that highlight certain information while masking other things. To decide if a 50 digit number is odd or even we only need to examine one digit, the last one. The octtet lattice provides not only a mental model but also a physical model of a 3D analog of Pascal's triangle. A group of small models made of toothpicks, soda straws, or cardboard can prove useful in order to "think" about tetrahedra. 

V. Basic Notation The notation in figure 6 is suitable, it agrees closely with Staib and Staib's notation for coordinates on any level while it uses Mueller's scheme for numbering the levels. The first level is set at zero. This is convenient because the value of the second element in the first row at higher levels is equal to the level and the sum of the coordinates for each point on a level is equal to the level index. 

True BASIC Program to calculate Pascal's Tetrahedron Element Values. 

VI. Some Interesting PropertiesA. A Fully Rounded Bell CurveAny row in Pascal's triangle yields the coefficients of a binomial expansion. A plot of the coefficients gives us the familiar, flat, two dimensional "bell" curve. This normal distribution can be modeled with a Galton Board simulation or with a series of heads or tails coin tosses, each with a probability of 1/2. The triangular levels of the 3D analog yield the coefficients of trinomial expansions. A plot of the coefficients gives us a threedimensional "bell" curve (see figure 7 and 8). The 3D version can also be modeled. By constructing the edges of the octahedra and tetrahedra in an octtet lattice with hollow tubes it would be possible to construct a working 3D version of a Galton Board. Here we would have a series of decisions with three possible outcomes, each with a 1/3 probability. Figure 7.A three dimensional bell curve. Level 74 of Pascal's Tetrahedron 

True BASIC Program to generate Bell Curve Plot 
True BASIC Program to generate Log Bell Curve Plot 
The three edge rows of the 3D "bell" curve (see figure 7) and the three flat faces of the log plot (see figure 8 which shows log plots of values for 6 different levels) are 2D "bell" curves. The elements on three of the four faces of the tetrahedral 3D analog are the same as the elements of the 2D Pascal's triangle. Pascal's triangle is contained in the 3D version.


B. Factoring ElementsIt appears that each element of a level factors into values that are less than the level number (click for proof). A random example. The value of the central element on level 1152 is a 547 digit number (click to see figure 9). It has 227 factors, the largest being 1151. This 547 digit number has factors that included 85% of the primes below it's level index of 1152 (click to see figure 10). It took 23 hours to come up with this central element's value and another 11 hours to factor it, on a standard IBM PC. For example, Pomerance states, ". . . factoring is hard. It has been estimated conservatively . . . that to factor certain composite n with 75 decimal digits, using the fastest factoring algorithm known on an imaginary computer faster than any now in existence would take about 15 weeks. For certain numbers with 100 digits it could take a life time." The elements of the 3D analog of Pascal's triangle are exceptions to Pomerance's statement. The numbers mentioned above are so large that few personal computer languages can handle them.
The True BASIC language along with two language
extension packages, the 3Dimensional Graphics and the Mathematician's Toolkit, were used to compute the examples in this article.
The Hugelib library allows for arithmetic of arbitrary precision, up to 100,000 digits by packing numbers into
strings. 

C. Odds and Evens A number of interesting 2D (and 3D) patterns can be generated by representing the values of the elements of a level with colored dots. These are similar to the patterns of odd and even distribution within Pascal's triangle . In the 3D analog the odds and evens are distributed into octahedral and tetrahedral components. When we plot the distributions of other multiples for various levels we obtain other interesting patterns (see figure 11). 

True BASIC Program to generate Mod Plots of Pascal's Tetrahedron Element Values 

Figure 11A screen shot of level 128  modulus 2 showing odd and even numbers resembles a Sierpinski gasket

The mod(2) patterns for the slices of levels 7, 15, 31, 63, 127 . . . are the same at the patterns for the three "exterior" faces of the tetrahedron (see figure 2). For a tetrahedron that is one level less than a power of two, all four faces have the same pattern. D. Plus or Minus One Primes The values of the elements of this 3D analog of Pascal's triangle factor into many small primes, they are divisible by a high percentage of integers (level 75 element values). These same element values plus or minus one have few divisors and few factors. Upon investigation we find that many of them are prime. Many elements are one more or less than a prime number. Some are between twin primes (see figure 12). Because computer languages for personal computers can handle about 15 significant digits you can calculate values for elements up to about level 35 in a straight forward manner. Program and array size limitations in many popular languages such as BASIC limit exploration of the 3D analog of Pascal's triangle to the first 18 levels. Brute force factoring methods also become unbearably time consuming at these levels. 

Figure 12 aA visualization of level 129 of Pascal's Tetrahedron. Elements are color coded.

To explore above level 18 I switched from using brute force factoring as a prime test to using Fermat's
Little Theorem with a base of 2 as a composite test. This can be stated: if b^{n}  b is a multiple of n, then n is a composite number. Above level 18 the composites I've identified are
composite, the primes are another story. Some might be pseudoprimes, some might be Charmichael numbers. It will
take more than a personal computer to be able to tell which is which. There have been some estimates of the number of pseudoprimes. "The scarcity of pseudoprimes to the base 2 among all the numbers smaller than 20 billion suggests that any number that passes the Fermat test to base 2 is likely to be prime," according to Pomerance . Of course a good proportion of the values from the 3D analog of Pascal's triangle that I've looked at are above Pomerance's 20 billion limit. The central values of level 74 are approximately 3.4x10^{34}. 

Figure 12b

True BASIC Program to record images 

True BASIC Program to playback images 

Exploration above level 18 would benefit from faster algorithms and computer systems that are more powerful. Since any element, from one of the levels of the tetrahedral array, is easy to factor (all factors have been less than the level index for every element factored to date). It might be possible to use Dixon's algorithm which is based on a complete factorization of n1, or other newer algorithms based on partial factorizations of n1 or n+1.  

Figure 12c




E. The OctTet AlgorithmThe first line of code sets point(0,0,0) equal to 1 by definition. Next we assign a value of 1 to any point (on a vertex) that has 2 coordinates of zero. If an element is not the initial point or a vertex point then we check to see if it's on the tetrahedral face. If it is we sum the two values from the level above for any element that is on the edge of a level. The final ELSE statement assigns a value for all the points not on an edge or vertex, setting them equal to the sum of the 3 elements from the level above. Let PT(0,0,0) = 1 FOR level = 1 TO top FOR x = level TO 0 STEP 1 FOR y = (level  x) TO 0 STEP 1 FOR z = (level  (x+y)) TO 0 STEP 1 IF x = 0 AND y = 0 OR x = 0 AND z = 0 OR y = 0 AND z = 0 THEN LET pt(x,y,z) = 1 ELSE IF x = 0 LET pt(x,y,z) = pt(x,y1,z) + pt(z,y,z1) ELSE IF y = 0 THEN LET pt(x,y,z) = pt(x1,y,z) + pt(z,y,z1) ELSE IF x = 0 THEN LET pt(x,y,z) = pt(x1,y,z) + pt(z,y1,z) ELSE LET pt(x,y,z)=pt(x1,y,z)+pt(x,y1,z)+pt(x,y,z1) NEXT z NEXT y NEXT z NEXT level 

F. An Alternate AlgorithmIn order to explore above level 18 of the 3D analog of Pascal's triangle on a PC it is necessary to use a language that uses more than 64K of memory and can handle more than 16 digit integers. Since each level is dependent on only one previous level it would also be possible to explore higher levels if we could find an algorithm that made more sparing use of computer memory. Alternating between two flat arrays rather than creating one large cubic array would be one solution. The drawback is that it would involve lots of coordinate manipulation. On the other hand mapping an octahedrontetrahedron lattice onto the standard x,y,z cubic coordinate system is wasteful of computer memory because we can only store 5456 elements in the 27,000 storage locations in an array 30 by 30 by 30. Another method of reaching higher levels in the 3D analog of Pascal's triangle (also true of Pascal's triangle) is based on the fact that each element of the tetrahedral array is related by a simple whole number ratio to the 12 elements around it (see figure 13). The value of any element can be calculated from any one of it's neighbors. We can start at any vertex element (which has a value of 1, by definition) on any level and apply a ratio calculation, proceeding from element to element, each time incrementing the denominator and decrementing the numerator of the interval ratio by 1. Using this system the need for array storage is cut drastically. 



G. Some Other PropertiesThe value of any element is equal to the number of different paths from the apex of the tetrahedron to that element. In Pascal's triangle this is the basis of "Taxicab" geometry. The sum of the unique elements on any level equals 3 to the power of the level index. For instance level 7 has eight unique elements; 1, 7, 21, 35, 42, 105, 140, and 210. These add up to 2187 or 3 to the seventh power. VII. SummaryThe three dimensional analog of Pascal's triangle is of interest for the same reasons that Pascal's triangle is of interest. It touches on number theory, the distribution of primes and twin primes, divisors, factors, combinatorics, and geometry. The patterns to be found in Pascal's triangle and it's 3D analog seem endless. ReferencesCheck the complete article in Computers and Graphics: An International Journal of Applications in Computer Graphics,
Volume 15, Number 2 1991 for more information. Pergamon Press ISSN 00978493 Footnotes


Visualizing Plus/Minus Primes on Multiple LevelsA Thought ExperimentThe elements Pascal's Tet are very divisible, but if we add or subtract one from an element's value we get some very undivisible numbers, i.e., primes or at least something like primes. Visualize Pascal's Tetrahedron as a stack of marbles. One marble for each element. A triangle of marbles for each level of the tetrahedron. Code the marbles red, green and blue if the plus or minus one value is prime. If not make it yellow. Levels 8, 9 & 10 in the 3D illustration below exhibit some interesting patterns. Here are the numerical values that go with the various "marbles" Values for
level 8, 9 & 10 


File Name 
What the file does or contains 
RECIMAGEC.EXE 

PLAYIMAG.EXE 
Quickly plays back the screen drawing of a triangular array of disks for any level of Pascal's Pyramid. TheRECIMAGE program is very CPU intensive and can take hours to compute a single level of values and draw the triangular array on the screen. Once those text files have been recorded with the RECIMAGE.EXE program, this PLAYIMAG.EXE program will quickly redraw the screenshots that have been saved to disk. 
README.TXT 
Info from True BASIC and Microsoft on DLL files and WIN32 files in Windows 3.1 
TB510.DLL 
These three DLL files from True BASIC, Inc. need to be installed in your Windows/System directory for the executable files to run 
XNMBA420.DLL 

XNMTE420.DLL 
the 765 Kilobyte archive file with the programs and files listed in the table above
Get the True BASIC Webapp plugin wbreader.exe
(a 678 Kilobyte self unzipping file)
from the True BASIC website (available in Mac and Windows formats)
Run RECIMAGE.TRC in your web browser with the True BASIC Webapp plugin
Run PLAYIMAG.TRC in your web browser with the True BASIC Webapp plugin
Illustrations and text adapted for the Internet by Jim Nugent using Visual Page,
Corel Draw, and Corel Paint.
Last updated on January 1, 2006
Jim Nugent