Difference between revisions of "Pascal's triangle"
(→Hockey-stick theorem) |
|||
Line 16: | Line 16: | ||
=== Hockey-stick theorem === | === Hockey-stick theorem === | ||
− | The [[Hockey-stick theorem]] states: | + | The [[Combinatorial identity#Hockey-Stick Identity|Hockey-stick theorem]] states: |
<math>{n \choose 0}+{n+1 \choose 1}+\cdots+{n+k \choose k} = {n+k+1 \choose k}</math>. Its name is due to the "hockey-stick" which appears when the numbers are plotted on Pascal's Triangle, as shown in the representation of the theorem to the right (where <math>n=2</math> and <math>k=3</math>). | <math>{n \choose 0}+{n+1 \choose 1}+\cdots+{n+k \choose k} = {n+k+1 \choose k}</math>. Its name is due to the "hockey-stick" which appears when the numbers are plotted on Pascal's Triangle, as shown in the representation of the theorem to the right (where <math>n=2</math> and <math>k=3</math>). | ||
Revision as of 15:45, 12 January 2011
Pascal's triangle is a triangle which contains the values from the binomial expansion; its various properties play a large role in combinatorics.
Contents
Properties
Binomial coefficients
Pascal's Triangle is defined such that the number in row and column
is
. For this reason, convention holds that both row numbers and column numbers start with 0. Thus, the apex of the triangle is row 0, and the first number in each row is column 0. As an example, the number in row 4, column 2 is
. Pascal's Triangle thus can serve as a "look-up table" for binomial expansion values. Also, many of the characteristics of Pascal's Triangle are derived from combinatorial identities; for example, because
, the sum of the values on row
of Pascal's Triangle is
.
Sum of previous values
One of the best known features of Pascal's Triangle is derived from the combinatorics identity . Thus, any number in the interior of Pascal's Triangle will be the sum of the two numbers appearing above it. For example,
, as shown in the diagram. This property allows the easy creation of the first few rows of Pascal's Triangle without having to calculate out each binomial expansion.
Fibonacci numbers
The Fibonacci numbers appear in Pascal's Triangle along the "shallow diagonals." That is, , where
is the Fibonacci sequence. For example,
. A "shallow diagonal" is plotted in the diagram.
Hockey-stick theorem
The Hockey-stick theorem states:
. Its name is due to the "hockey-stick" which appears when the numbers are plotted on Pascal's Triangle, as shown in the representation of the theorem to the right (where
and
).
Number Parity
Consider writing the row number in base two as
. The number in the
th column of the
th row in Pascal's Triangle is odd if and only if
can be expressed as the sum of some
. For example,
. Thus, the only 4 odd numbers in the 9th row will be in the
th,
st,
th, and
th columns. Additionally, marking each of these odd numbers in Pascal's Triangle creates a Sierpinski triangle.