[go: up one dir, main page]

TOPICS
Search

Pascal's Triangle


Pascal's triangle is a number triangle with numbers arranged in staggered rows such that

 a_(nr)=(n!)/(r!(n-r)!)=(n; r),
(1)

where (n; r) is a binomial coefficient. The triangle was studied by B. Pascal, in whose posthumous work it appeared in 1665 (Pascal 1665). However, it had been previously investigated my many other mathematicians, including Italian algebraist Niccolò Tartaglia, who published the first six rows of the triangle in 1556. It was also described centuries earlier by Chinese mathematician Yang Hui and the Persian astronomer-poet Omar Khayyám. As a result, it is known as the Yang Hui triangle in China, the Khayyam triangle in Persia, and Tartaglia's triangle in Italy.

Starting with n=0, the triangle is

 1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5  10  10  5  1
1  6  15  20  15  6  1
(2)

(OEIS A007318). Pascal's formula shows that each subsequent row is obtained by adding the two entries diagonally above,

 (n; r)=(n!)/((n-r)!r!)=(n-1; r)+(n-1; r-1).
(3)
Binary plot for Pascal's triangle

The plot above shows the binary representations for the first 255 (top figure) and 511 (bottom figure) terms of a flattened Pascal's triangle.

The first number after the 1 in each row divides all other numbers in that row iff it is a prime.

The sums P_n of the number of odd entries in the first n rows of Pascal's triangle for n=0, 1, ... are 0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, ... (OEIS A006046). It is then true that

 0.812...<P_nn^(-theta)<=1
(4)

(Harborth 1976, Le Lionnais 1983), with equality for n a power of 2, and the power of n given by the constant

 theta=(ln3)/(ln2)=log_23=1.58496250072115...
(5)

(OEIS A020857). The sequence of cumulative counts of odd entries has some amazing properties, and the minimum possible value beta=0.812... (OEIS A077464) is known as the Stolarsky-Harborth constant.

Pascal's triangle contains the figurate numbers along its diagonals, as can be seen from the identity

sum_(i=1)^(n)(i; j)=(n+1)/(j+1)(n; j)
(6)
=(n+1; j+1).
(7)

In addition, the sum of the elements of the ith row is

 sum_(j=0)^i(i; j)=2^i,
(8)

so the sum of the first k rows (i.e., rows 0 to k-1) is the Mersenne number

 sum_(i=0)^(k-1)2^i=2^k-1.
(9)
FibonacciShallowDiags

The "shallow diagonals" of Pascal's triangle sum to Fibonacci numbers, i.e.,

1=1
(10)
1=1
(11)
2=1+1
(12)
3=2+1
(13)
5=1+3+1
(14)
8=3+4+1
(15)

and, in general,

 sum_(k=0)^(|_n/2_|)(n-k; k)=F_(n+1).
(16)

The numbers of times that the numbers 2, 3, 4, ... occur in Pascal's triangle are given by 1, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 2, 4, ... (OEIS A003016; Ogilvy 1972, p. 96; Comtet 1974, p. 93; Singmaster 1971). Similarly, the numbers of rows in which the numbers 2, 3, 4, ... occur are 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, ... (OEIS A059233).

By row 210, the numbers

120=(10; 3)=(10; 7)=(16; 2)=(16; 14)=(120; 1)=(120; 119)
(17)
210=(10; 4)=(10; 6)=(21; 2)=(21; 19)=(210; 1)=(210; 209)
(18)
3003=(14; 6)=(14; 8)=(15; 5)=(15; 10)=(78; 2)=(78; 76)
(19)

have appeared six times, more than any other number (excluding 1). By row 1540,

 1540=(22; 3)=(22; 19)=(56; 2)=(56; 54)=(1540; 1) 
 =(1540; 1539)
(20)

has now occurred six times, by row 3003,

 3003=(14; 6)=(14; 8)=(15; 5)=(15; 10)=(78; 2) 
 =(78; 76)=(3003; 1)=(3003; 3002)
(21)

has now occurred 8 times, and by row 7140, 7140 has appeared six times as well. In fact, the numbers that occur five or more times in Pascal's triangle are 1, 120, 210, 1540, 3003, 7140, 11628, 24310, ... (OEIS A003015), with no others up to 33×10^(16).

It is known that there are infinitely many numbers that occur at least 6 times in Pascal's triangle, namely the solutions to

 r=(n; m-1)=(n-1; m)
(22)

given by

m=F_(2k-1)F_(2k)
(23)
n=F_(2k)F_(2k+1),
(24)

where F_i is the ith Fibonacci number (Singmaster 1975). The first few such values of r for k=1, 2, ... are 1, 3003, 61218182743304701891431482520, ... (OEIS A090162).

There is an unexpected connection between Pascal's triangle and the Delannoy numbers via Cholesky decomposition (G. Helms, pers. comm., Aug. 29, 2005). What's more, despite the two being mathematically unrelated, there's also a topical connection between Pascal's triangle and the so-called rascal triangle; this relationship also provides a tangential relation to the cake cutting problem and hence to the cake numbers.

Pascal's triangle (mod 2) turns out to be equivalent to the Sierpiński sieve (Wolfram 1984; Crandall and Pomerance 2001; Borwein and Bailey 2003, pp. 46-47). Guy (1990) gives several other unexpected properties of Pascal's triangle.


See also

Bell Triangle, Bernoulli Triangle, Binomial Coefficient, Binomial Theorem, Brianchon's Theorem, Cake Cutting, Catalan's Triangle, Christmas Stocking Theorem, Clark's Triangle, Cylinder Cutting, Euler's Number Triangle, Fibonacci Number, Figurate Number Triangle, Leibniz Harmonic Triangle, Losanitsch's Triangle, Number Triangle, Pascal's Formula, Pascal Matrix, Polygon, Rascal Triangle, Seidel-Entringer-Arnold Triangle, Sierpiński Sieve, Space Division by Planes, Square Division by Lines, Star of David Theorem, Stolarsky-Harborth Constant, Trinomial Triangle Explore this topic in the MathWorld classroom

Portions of this entry contributed by Christopher Stover

Explore with Wolfram|Alpha

References

Borwein, J. and Bailey, D. "Pascal's Triangle." §2.1 in Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 45-48, 2003.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, p. 93, 1974.Conway, J. H. and Guy, R. K. "Pascal's Triangle." In The Book of Numbers. New York: Springer-Verlag, pp. 68-70, 1996.Courant, R. and Robbins, H. What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, p. 17, 1996.Crandall, R. and Pomerance, C. Research Problem 8.22 in Prime Numbers: A Computational Perspective. New York: Springer-Verlag, 2001.de Weger, B. M. M. "Equal Binomial Coefficients: Some Elementary Considerations." Econometric Institute Report from Erasmus University Rotterdam, Econometric Institute, No. 118. http://econpapers.hhs.se/paper/dgreureir/1997118.htm.Gardner, M. "Pascal's Triangle." Ch. 15 in Mathematical Carnival: A New Round-Up of Tantalizers and Puzzles from Scientific American. New York: Vintage Books, pp. 194-207, 1977.Guy, R. K. "The Second Strong Law of Small Numbers." Math. Mag. 63, 3-20, 1990.Guy, R. K. and Klee, V. "Monthly Research Problems, 1969-1971." Amer. Math. Monthly 78, 1113-1122, 1971.Harborth, H. "Number of Odd Binomial Coefficients." Not. Amer. Math. Soc. 23, 4, 1976.Le Lionnais, F. Les nombres remarquables. Paris: Hermann, p. 31, 1983.Ogilvy, C. S. Tomorrow's Math: Unsolved Problems for the Amateur, 2nd ed. New York: Oxford University Press, 1972.Pappas, T. "Pascal's Triangle, the Fibonacci Sequence & Binomial Formula," "Chinese Triangle," and "Probability and Pascal's Triangle." The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 40-41 88, and 184-186, 1989.Pascal, B. Traité du triangle arithmétique, avec quelques autres petits traitez sur la mesme matière at gallica. Paris: G. Desprez, 1665.Pickover, C. A. "Beauty, Symmetry, and Pascal's Triangle." Ch. 54 in Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning. Oxford, England: Oxford University Press, pp. 130-133, 2001.Singmaster, D. "How Often Does an Integer Occur as a Binomial Coefficient?" Amer. Math. Monthly 78, 385-386, 1971.Singmaster, D. "Repeated Binomial Coefficients and Fibonacci Numbers." Fib. Quart. 13, 295-298, 1975.Sloane, N. J. A. Sequences A003015/M5374, A003016/M0227, A059233, A006046/M2445, A007318/M0082,A020857, A077464, and A090162 in "The On-Line Encyclopedia of Integer Sequences."Smith, D. E. A Source Book in Mathematics. New York: Dover, p. 86, 1984.Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 284-285, 1999.Wells, D. The Penguin Dictionary of Curious and Interesting Geometry. London: Penguin, pp. 174-175, 1991.Wolfram, S. "Computation Theory of Cellular Automata." Comm. Math. Phys. 96, 15-57, 1984.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 870 and 931-932, 2002.

Referenced on Wolfram|Alpha

Pascal's Triangle

Cite this as:

Stover, Christopher and Weisstein, Eric W. "Pascal's Triangle." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PascalsTriangle.html

Subject classifications