Mission Heavens, Mathematics / Pascal

BLOG LIST | powered by NetKismet

Pascal Triangle Color Coding:

Color coding of even and odd entries in the Pascal triangle with 16, 32, and 64 rows.

The Pascal Triangle

Blaise Pascal (1623-1662) was a great French mathemetician and scientist. When he was twenty years old, he built some 10 mathematical machines for the addition of integers, a precursor to modern computers. What is known as the arithmetic triangle (or Pascal's Triangle) was not originally his discovery. The first printed form of the arithmetic triangle in Europe dates back to 1527. A Chinese version had already been published in 1303.

But Pascal used the arithmetic triangle to solve some problems related to chances in gambling, which he had discussed with Pierre de Fermat in 1654. This research later became the foundations of probability theory.

a decorative gold, white and black horizontal line

The arithmetic triangle is a triangular array of numbers composed of the coefficients of the expansion of the polynomial (1 + x)ⁿ. Here n denotes the row starting from n = 0. Row n has n + 1 entries. For example, for n = 3 the polynomial is (1 + x)³ = 1 + 3x + 3x² + x³. Thus, row number 3 reads: 1,3,3,1. (see images below)

There are two ways to compute the coefficients. The first one inductively computes one row based on the entries of the previous row. Assume that the coefficients a₀,...,a_n in row n are given:
(1 + x)ⁿ = a₀ + a₁x + ...+ a_nxⁿ, and the coefficients b₀,...,b_n + 1 of the following row are required:

(1 + x)^{n + 1} = b₀ + b_1x + ...+_{n + 1}x^{n + 1}

Comparing coefficients we obtain the result:
b₀ = a₀,
b_k = a_{k - 1}a_k for k = 1,...,n,
b_{n + 1} = a_n.

REF: Wikipedia Binomial coefficient
In mathematics, the binomial coefficient $\tbinom nk$ is the coefficient of the x^k term in the polynomial expansion of the binomial power (1 + x)ⁿ. $\tbinom nk$ is often called the choose function of n and k;
$\tbinom nk$ is the number of k-element subsets (the k-combinations) of an n-element set; that is, the number of ways that k things can be 'chosen' from a set of n things. Given a non-negative integer n and an integer k, the binomial coefficient is defined to be the natural number;
${n \choose k} = \frac{n \cdot (n-1) \cdots (n-k+1)} {k \cdot (k-1) \cdots 1} = \frac{n!}{k!(n-k)!} \quad \mbox{if}\ 0\leq k\leq n \qquad (1)$ and ${n \choose k} = 0 \quad \mbox{if } k < 0 \mbox{ or } k>n$ where n! denotes the factorial (factorial: the product of all positive integers less than or equal to n of n. Alternatively, a recursive defition can be written as: ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$

where ${n \choose 0} = {n \choose n} = 1$ The notation $\tbinom nk$ was introduced by Albert von Ettinghausen in 1826, although these numbers were already known centuries before that (see Pascal's triangle). The function $(n,k)\mapsto\tbinom nk$ is often called the choose function, and $\tbinom nk$ is often read as "n choose k".The binomial coefficients are the coefficients of the series expansion of a power of a binomial. If the exponent nonnegative integer then this infinite series is actually a finite sum as all terms with k>n are zero, but if the exponent n is negative or a non-integer, then it is an infinite series.

(REF: textbook 'Chaos and Fractals: the New Frontiers of Science')

Applying the formula to (1 + xⁿ) we immediately obtain the k^th coefficient b_k (k runs from 0 to n) of row number n of Pascal's triangle. For example, the coeffient for k = 3 in row n = 7 is: ${7 \choose 3} = \frac{7!}{3!(7-3)!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(3 \cdot 2 \cdot 1)(4 \cdot 3 \cdot 2 \cdot 1)} = \frac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1} = 35.$ The calculation of the binomial coefficient is conveniently arranged like this: ((((5/1)·6)/2)·7)/3, alternately dividing and multiplying with increasing integers. Each division produces an integer result which is itself a binomial coefficient.

The recipe to compute the coefficients of a row is thus very simple. The first and last lines are copied from the line above. These will always be equal to 1. The other coefficients are just the sum of the two coefficients in the row above. In this scheme it is most convenient to write Pascal's triangle in the form with the top vertex centered on a line above it as shown (in the image above. $(1+x)^n = \sum_{k=0}^\infty {n \choose k} x^k. \qquad (2)$
Another identity is easy to derive: the sum of all coefficients in row number n of Pascal's triangle is equal to 2ⁿ, which is seen by setting x = y = 1 in the binomial formula. (NOTE: while Christian Kramp (Algrebra textbook, 1808) and Euler wrote [n]; Gauss (German mathematician and physicist) used the notation π( n).

Pascal's rule is the important recurrence relation : ${n \choose k} + {n \choose k+1} = {n+1 \choose k+1}, \qquad (3)$ which follows directly from the definition: $\begin{align} {n \choose k} + {n \choose k+1} &{}= \frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-(k+1))!} \\ &{} = \left(\frac{n!(k+1)}{k!(n-k)!(k+1)} + \frac{n!(n-k)}{(k+1)!(n-(k+1))!(n-k)}\right)\\ &{} = \left(\frac{n!(k+1 + n-k)}{(k+1)!(n-k)!}\right) \\ &{} = \frac{(n+1)!}{(k+1)!((n+1)-(k+1))!} \\ &{} = {n+1 \choose k+1} \end{align}$ The recurrence relation just proved can be used to prove by mathematical induction that C(n, k) is a natural number (and C = combinations or choices) for all n and k. Pascal's rule also gives rise to Pascal's triangle.

Row number n contains the numbers C(n, k) for k = 0,…,n. It is constructed by starting with ones at the outside and then always adding two adjacent numbers and writing the sum directly underneath. This method allows the quick calculation of binomial coefficients without the need for fractions or multiplications. For instance, by looking at row number 5 of the triangle, one can quickly read off that:

(x + y)⁵ = 1 x⁵ + 5
x⁴y + 10 x³y² +
10 x²y³ + 5 x y⁴
+ 1 y⁵.

The differences between elements on other diagonals are the elements in the previous diagonal, as a consequence of the recurrence relation above. In the 1303 AD treatise Precious Mirror of the Four Elements, Zhu Shijie mentioned the triangle as an ancient method for evaluating binomial coefficients indicating that the method was known to Chinese mathematicians five centuries before Pascal.

a decorative gold, white and black horizontal line

Mathematics decorative image, collage with a compass, a formula written on a chalboard, and two formulas

MATHEMATICS / Pascal