An introduction to Pascal's Triangle of numbers and applications
in algebra, coin tossing, with some basic theorems illustrated and proved.
The calculators and other effects on this page require JavaScript but you appear to have switched JavaScript off
(it is disabled) in this browser.
Please go to the Preferences or Properties menu item for this browser and enable it and then Reload this page.
Contents of this page
The icon means there is a
You Do The Maths... section of questions to start your own investigations.
The calculator icon
indicates that there is a live interactive calculator in that section.
Choosing a Selection
Blaise Pascal
(1623 - 1662) was a French mathematician and philosopher who studied probabilites
and took an interest in a triangle of numbers which, though named after him,
had been known about for many centuries already.
The Triangle contains the number of ways of choosing some objects out of a larger set of different things.
These choices make a subset of the set of possible choices where
a collection means a subset and the order of the items in the subset is of no importance.
Sets are written as a list of objects inside curly brackets { and }.
The empty set of no objects is also a set and is written as {}.
We can standardise the choices by numbering the elements of the set of possible elements to choose and then
just finding a subset of these indices to indicate which elements are in the collection (subset).
For instance, if we use numbers 1 to n for the objects to choose from them the subsets are also the index
numbers of the items in the set
2 objects: 1 and 2
we can choose 1 of them in two ways {1} and {2}
all of them {1,2}
or none of them {}
# of items seleted
0
1
2
# of ways
1
2
1
with a total of 4 ways of selecting a collection.
3 objects: 1, 2, 3
# of items seleted
0
1
2
3
selections
{}
{1} {2} {3}
{1,2} {1,3} {2,3}
{1,2,3}
# of ways
1
3
3
1
with a total of 8 = 2 ways of selecting a subset
In general there are 2n ways of choosing a subset of n items.
This is because each item in the master set may be in the selection or not in a selection,
so each has 2 possibilities. With n objects to choose from then there will be
have 2n subsets of choices in total.
Notation
n! means "n factorial". It the number of ways to arrange n things, so the order of the
items in the arrangement is important.
n! is the product of all the numbers from 1 to n.
For example:
If we have 6 books to arrange on a shelf, then
we can choose any of the 6 as the first on the shelf,
followed by any of the remaining 5 for the second making 6×5=30 ways to fill the first two
places on the shelf.
The third place can take any of the remaining 4 books so there are 6×5×4 = 120 ways to fill the first
3 places.
and the fourth choice is one of 3 books,
the fifth is one of the remaining 2
leaving one left for the last place.
Thus there are 6×5×4×3×2×1 = 720 orderings or arrangements of the
6 books on the shelf. This is denoted 6! .
(
n
)
= Binomial(n,r) = nCr = "n choose r" for 0≤r≤n
r
=
n!
(n-r)! r!
=
n(n−1)...(n−r+1)
r(r−1)...3×2×1
0! = 1
The reason for this formula for Binomial(n,r) (or n choose r meaning the number of collections (sets)
of r things from n ) is that there are n×(n-1)×...×(r+1) (there are r numbers in
this product)
ways to pick the r objects where the order matters (so that AB is counted as well as BA)
so if we are interested just in which are items chosen or not (subsets)
and not in the order in which they are chosen,
then every collection of r items will appear in r! different orders or arrangements.
So for subsets - which is what Pascal's Triangle shows - we need to divide by r!
to account for the the number of arrangements of each collection of r things chosen from n.
Binomial(n,c) has other notations in maths books , for example:
nCc, nCc or Cn,c
All are pronounced "(from) n choose c".
Pascal's Triangle
n
r= 0
1
2
3
4
...
1
0
1
1 1
1
1
1
1 2 1
2
1
2
1
1 3 3 1
3
1
3
3
1
1 4 6 4 1
4
1
4
6
4
1
...
...
...
Each entry in the triangle on the left is the sum of the two numbers
above it.
If we re-align the table to look the one on the right then each number is the sum of the one above it and the one to the left of that one where a blank space can be
taken as "0". Note that each row starts and ends with "1".
A recursive definition
Each element in Pascal's Triangle above, which is left-justified here, is the sum of the element above
and the element to the left of that one where blank entries mean "0". The right-hand elements
in column 0 are always 1:
The recursive definition
nCc =
(
n
)
=
(
n − 1
)
+
(
n − 1
)
, c ≥ c > 0
x
c
x − 1
(
n
)
= 1;
(
n
)
= 0 otherwise
0
c
Pascal's Triangle has lots of uses including
Calculating probabilities.
If you throw n coins randomly onto a table then
the chance of getting H heads among them is the entry in row N, col H
divided by 2n:
for instance, for 3 coins, n=3 so we use row 3:
3 heads: H=3 is found in 1 way (HHH)
2 heads: H=2 can be got in 3 ways (HHT, HTH and THH)
1 head: H=1 is also found in 3 possible ways (HTT, THT, TTH)
0 heads: H=0 (i.e. all Tails) is also possible in just 1 way: TTT
Pascal's Triangle (Binomial) Calculator
This calculator can compute elements of Pascal's triangle individually or by rows or show the subsets.
Pascal's Triangle C A L C U L A T O R
n=
r=
R E S U L T S
Binomial expansion using Pascal's Triangle
The rows as coefficients
Apart from counting subsets and additions using 1s and 2s, another application of Pascal's Triangle
is to find the coefficients when we expand (1+x)n.
We will find it convenient to use the triangle in its left-leaning form:
The coefficients of the powers of x, from x0 to xn
The numbers on row n of Pascal's Triangle are the coefficients (multiples) of the powers of x
The coefficient of xc is in column c of row n.
Since (1+x)n = (1+x)(1+x)n-1,
it is easy to show that the coefficient of xc in (1+x)n is
made up of the coefficient of xr in the (1+x)c-1 row PLUS
x times the coefficient of xc-1 from the same n-1 row also. This gives us the
recursion formula that we found above:
Since (1+x)0 = 1 then we have the same starting conditions too, and therefore the
same triangle of numbers for the coefficients and for Pascal's triangle!
We can generalise this to expansions of (a+b)n too
where a+b has two variables, forming a binomial expression:
(a+b)0 = 1
(a+b)1 = 1 a + 1 b
(a+b)2 = 1 a2 + 2 ab + 1 b2
(a+b)3 = 1 a3 + 3 a2b + 3 ab2 + 1 b3
...
The terms of (a + b)n are made by choosing one of the two variables, a or b, form each bracket and multiplying them.
So each term has a power of a and a power of b where the power must sum to n.
Each has a multiple before it, called its coefficient whhich is a number on row n of Pascal's Triangle.
The coefficient of acbn-c in the expansion of (a+b)n
is binomial(n,c)
The terms are Binomial(n,c) acbn-c
The columns as coefficients
n
c= 0
1
2
3
4
...
0
1
1
1
1
2
1
2
1
3
1
3
3
1
4
1
4
6
4
1
...
...
The columns also are important as coefficients of expansions of
1
(1−x)c + 1
Unlike the rows, the columns go on for ever and the powers of 1/(1+x)2
have a coefficient for each and every (non-negative) power of x.
Since the powers go on for ever, we must ensure -1<x<1 or else when adding the terms up
we will not get a finite number (the expansion will not converge).
1/(1−x) = 1 + 1 x + 1 x2 + 1 x3 + ... which is column c=0 of Pascal's Triangle
1/(1−x)2 = 1 + 2 x + 3 x2 + 4 x3 + ... which is column c=1 of Pascal's Triangle
1/(1−x)3 = 1 + 3 x + 6 x2 + 10 x3 + ... which is column c=2
An application of this is to let x=1/10 and look at decimal expansions of some fractions:
1/(1-0.1) = 10/(10-1) = 10/9 = 1 + 1/10 + 1/100 + 1/1000 + ... = 1.111...
1/(1-0.1)2 = 100/(92 = 100/81 = 1 + 2/10 + 3/100 + 4/1000 + ... = 1.23456...
x=0.01:
1/(1-0.01) = 100/(100-1) = 100/99 = 1 + 1/100 + 1/10000 + ... = 1.010101...
1/(1-0.01)2 = 10000/(99×99) = 1 + 2/100 + 3/1000 + 4/10000 +... = 1.02030405...
There is much more about decimal expansion of fractions on the
Fractions and Decimals page.
Note: We need to be careful about what values we use for x since
sometimes the expansions do not converge to a number but keep increasing the more terms we add on.
Divisibility in Pascal's Triangle
What do you notice about the prime-number rows of Pascal's Triangle?
Apart from the starting and ending 1's, all the entries are divisible by the prime row number.
This is not true for rows n where n is a non-prime number.
The more general result applicable to all rows is left as an investigation in the
You Do The Maths... section below.
The remainder after dividing n by d in mathematics is written
n modulo d or n mod d.
You can see the patterns and experiment for yourself in the Calculator below.
You do the maths...
It looks like every element that is bigger than 1 on row n has a prime factor in common with the row number.
Can you prove this or find a counter-example? Answer
Here is a table of the gcds of the row number and the elements of that row:
n:
1
1
1
2
1
2
1
3
1
3
3
1
4
1
4
2
4
1
5
1
5
5
5
5
1
6
1
6
3
2
3
6
1
7
1
7
7
7
7
7
7
1
8
1
8
4
8
2
8
4
8
1
9
1
9
9
3
9
9
3
9
9
1
10
1
10
5
10
10
2
10
10
5
10
1
11
1
11
11
11
11
11
11
11
11
11
11
1
12
1
12
6
4
3
12
12
12
3
4
6
12
1
13
1
13
13
13
13
13
13
13
13
13
13
13
13
1
14
1
14
7
14
7
14
7
2
7
14
7
14
7
14
1
15
1
15
15
5
15
3
5
15
15
5
3
15
5
15
15
1
16
1
16
8
16
4
16
8
16
2
16
8
16
4
16
8
16
1
17
1
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
1
18
1
18
9
6
18
18
6
18
18
2
18
18
6
18
18
6
9
18
1
19
1
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
19
1
20
1
20
10
20
5
4
20
20
10
20
4
20
10
20
20
4
5
20
10
20
1
r:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
So yes, it is true that
Every Binomial bigger than 1 has a factor in common with its row number:
GCD(n,Binomial(n,r))>1 if Binomial(n,r)>1
The Art of Pascal's Triangle Remainders
There are some fantastic patterns in Pascal's Triangle which we look at later on this page
but one which is simple involves the remainders when we divide every element by a given number.
For instance, dividing by 7 will leave us with 0,1,2,3,4,5 or 6 as the possible remainders for every element
and dividing by 2 will give remainders 0 and 1 or the even and the odd numbers.
If a remainder is 0 when dividing by d then the number is a multiple of d.
We talk above looking just at remainders when dividing by d as "modulo d" or mod d
for short.
Here are rows 0 to 8 of Pascal's Triangle with the even number paler:
and here it is when we just coloured dots for the remainders and center each row,
You can see the fractal nature of the pattern - that is, each part in repeated in the larger pattern.
The patterns are beautiful and either simple or complex depending on the mod chosen.
Here is a Calculator for you to investigate for yourself:
Remainder Patterns Calculator
Remainders C A L C U L A T O R
row:
.. mod=
bigger?:
R E S U L T S
How often does a number appear in Pascal's Triangle?
Using a few facts:
each row is a palindrome - that is, it is the same when reversed, called reflection symmetry
or row symmetry.
row n begins 1,n and ends n,1
the numbers increase on every row until the centre and then decrease (by the reflection symmetry rule)
we can search Pascal's Triangle and find:
2 is the only number to appear just once.
All the elements that appear more than 2 times will be in the inner part of Pascal's
Triangle, between columns 2 and n-2 on row n. If we list these number in order we have:
6,10,15,20,21,28,35,36,45,55, 56,66,70,78,84,91, ... A006987
...
... whereas the complement of that sequence
is the numbers in Pascal's triangle that appear just twice:
3, 4, 5, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 22, 23, 24, 25, 26, 27, ... A137905
The first numbers to appear 3 times are 6, 70, 252, 924, 3432,
12870, ... which appears to be all the Central Binomial coefficients Binomial(2n,n)
that are greater than 2:
A000984
Occurring 4 times are 10, 15, 28, 35, 36,45, 55, 56, ... .
A098564
No number has been found yet that appears just 5 times
6 times: 120, 210, 1540, 7140, 11628, 24310, ...
A098565
These include the values of Binomial( Fib(2k)×Fib(2k+1), Fib(2k+1)2 )
see A090162
where Fib(n) is the n-th Fibonacci number
These numbers get large very rapidly. 3003 has 4 digits and the next have
29, 205, 1412 and then 9688 digits!
No number has been found that appears just 7 times
3003 appears 8 times but no other numbers are known.
No number has been found that appears more than 8 times
Interesting facts about 3003:
3003 is also the sum of the two previous binomials on the same row:
`([14],[4])=1001, ([14],[5])=2002` with sum `([14],[6])=3003` Are there any more?
The next two are:
`([103],[38]) + ([103],[39]) = ([103],[40])` with 29 digits each
`([713],[271]) + ([713],[272]) = ([713],[273])` with 205 digits each
Pascal's Triangle (Binomial) Calculator
This calculator can compute elements of Pascal's triangle individually or by rows or show the subsets.
Pascal's Triangle C A L C U L A T O R
n=
r=
of numbers
..
R E S U L T S
You do the maths...
Use the Calculator above to find as many numbers as you can that occur just 4 times in Pascal's Triangle as you can.
Can you spot any patterns? Note
The list of these numbers is
A098564 but no general formula (or even
a formula for a subset) is known.
Use the Calculator above to find as many numbers as you can that occur 5 or more times in Pacal's Triangle as you can.
Can you spot any patterns? Note
The list of these numbers is
1, 120, 210, 1540, 3003, 7140, 11628, 24310, 61218182743304701891431482520
A003015
and it is known that there are
infinitely many of them that occur just 6 times.
There are no more numbers less than the last in the list above!
What is a formula for the central numbers,
that is those that appear in the centre of an even-numbered row? Answer
These are the Central Binomial Coefficients Binomial(2n,n):
No number is known that appears just 5 times. Since 5 is odd, it must appear once as a central number.
Can you find one? (The Calculator above will compute numbers in Pascal's Triangle with a very large number
of digits).
Which numbers in Pascal's Triangle are doubled on the next row, same column? Answer
If we find a row with two identical central numbers then they are doubled on the next row
by the The Recursive Definition.
These are the Central Binomial Numbers: Binomial(2n,n): See the Question above
about central numbers
Binomial(5,2)=Binomial(5,3)=10, Binomial(6,3)=20
Binomial(7,3)=Binomial(7,4)=35, Binomial(8,4)=70
...
See A001700
Which numbers in Pascal's Triangle are followed by their double on the same row? Answer
The general answer is Binomial(3n-1,n-1) and Binomial{3n-1,n):
Binomial(8,2)= 28, Binomial(8,3)=56
Binomial(11,3)=165, Binomial(11,4)=330
Binomial(14,4)=1001, Binomial(14,5)=2002
... See A025174
The Fibonacci Numbers in Pascal's Triangle
Can we find the Fibonacci Numbers in Pascal's Triangle? Yes! The answer lies in the diagonals in the triangle:
Sum
1
1 ↗
1
1
1 ↗
1
2
1
2 ↗
1
3
3
1
3 ↗
1
4
6
4
1
5 ↗
1
5
10
10
5
1
8 ↗
1
6
15
20
15
6
1
13↗
1
7
21
35
35
21
7
1
21↗
...
Why do the Diagonals sum to Fibonacci numbers?
It is easy to see that the diagonal sums really are the Fibonacci numbers if we
remember that each number in Pascal's triangle is the sum of two numbers in the
row above it (blank spaces count as zero),
so that 6 here is the sum of the two 3's on the row above.
The numbers in any diagonal row are therefore formed from adding numbers in the
previous two diagonal rows as we see here where all the blank spaces are zeroes
and where we have introduced an extra column of zeros which we will use later:
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
The green diagonal sums to 5;
the blue diagonal sums to 8;
the red diagonal sums to 13
Each red number is the sum of a blue
and a green number on the row above.
Notice that the GREEN numbers are on one diagonal and the
BLUE ones on the next. The sum of all the green numbers
is 5 and all the blue numbers add up to 8.
Because all the numbers in Pascal's Triangle are made the same way -
by adding the two numbers above
and to the left on the row above,
then we can see that each red number is just the
sum of a green number and a blue number and we use up all the blue and green numbers
to make all the red ones.
The sum of all the red numbers is
therefore the same as the sum of all the blues and all the greens: 5+8=13!
The general
principle that we have just illustrated is:
The sum
of the numbers on one diagonal is the sum of the numbers on the previous
two diagonals.
If we let D(i) stand for the sum of the numbers on the Diagonal that starts with
one of the extra zeros at the beginning of row i, then
D(0)=0 and D(1)=1
are the two initial diagonals shown in the table above. The green diagonal
sum is
D(5)=5 (since its extra initial zero is in row 5) and the blue diagonal sum is D(6)
which is 8. Our red diagonal is D(7) = 13 = D(6)+D(5).
We also have shown that this is always true: one diagonals sum id the sum of the
previous two diagonal sums, or, in terms of our D series of numbers:
D(i) = D(i-1) + D(i-2)
But...
D(0) = 1
D(1) = 1
D(i) = D(i-1) + D(i-2)
is
exactly the definition of the Fibonacci numbers! So D(i) is just F(i) and
the sums of the diagonals in Pascal's Triangle are the Fibonacci numbers!
Another arrangement of Pascal's Triangle
By drawing Pascal's Triangle with all the rows moved over by 1 place, we have a clearer
arrangement which shows the Fibonacci numbers as sums of columns:
1
2
3
4
5
6
7
8
9
10
1
.
.
.
.
.
.
.
.
.
.
1
1
.
.
.
.
.
.
.
.
.
1
2
1
.
.
.
.
.
.
.
.
1
3
3
1
.
.
.
.
.
.
.
1
4
6
4
1
.
.
.
.
.
.
1
5
10
10
5
.
.
.
.
.
.
1
6
15
20
.
.
.
.
.
.
.
1
7
21
.
.
.
.
.
.
.
.
1
8
.
.
.
.
.
.
.
.
.
1
1
1
2
3
5
8
13
21
34
55
This table can be explained by referring to one of the
(Easier) Fibonacci Puzzles - the one about
Fibonacci for a Change. It asks how many ways you can pay n pence (in the UK)
using only 1 pence and 2 pence coins. The order of the coins matters, so that 1p+2p will pay for a 3p item
and 2p+1p is counted as a different answer.
[We now have a new two pound coin that
is increasing in circulation too!]
Here are the answers for paying up to 5p using only 1p and 2p coins:
Let's look at this another way - arranging our answers according to the number of
1p and 2p coins we use. Columns will represent all the ways of paying the amount at the head
of the column, as before, but now the rows represent the number of coins in the solutions:
cost:
1p
2p
3p
4p
5p
1 coin:
1
2
2 coins:
1+1
1+2 2+1
2+2
3 coins:
1+1+1
1+1+2 1+2+1 2+1+1
1+2+2 2+1+2 2+2+1
4 coins:
1+1+1+1
2+1+1+1
1+1+1+2 1+1+2+1 1+2+1+1
5 coins:
1+1+1+1+1
If you count the number of solutions in each box, it will be exactly the form of Pascal's triangle that
we showed above!
If you tossed a coin 10 times, how many possible sequences of Heads and Tails could
there be in total (use Pascal's Triangle extending it to the row numbered 10)?
In how many of these are there 5 heads (and so 5 tails)? What is the probability of
tossing 10 coins and getting exactly 5 heads therefore - it is not 0·5!
Draw up a table for each even number of coins from 2 to 10 and show the
probability of getting exactly half heads and half tails for each case. What is happening
to the probability as the number of coins gets larger?
[HINT: Use the Calculator below.]
Write out the first few powers of 11. Do they remind you of Pascal's
triangle? Why? Why does the
Pascal's triangle pattern break down after the first few powers?
(Hint: consider (a+b)m where a=10 and b=1).
Galton's Quincunx
This is a device with nails arranged in a regular
hexagon pattern. Its name derives from the Latin word quincunx
for the X-like shape of the spots on the 5-face of a dice:
Hopper for balls
balls fall onto nails with an
equal chance of bouncing to
left or right each time
balls collect in bins
When balls are poured onto the network of nails at the top, they fall
through, bouncing either to the right
or to the left and so hit another nail on the row below. Eventually they fall
off the bottom row of nails and are collected in the bins.
If we arrange pins on a board so that a ball, falling onto any pin has an equal chance
of falling off to the left or to the right
then we can simulate the selections of n objects into n bins under the final row of pins.
Here is a simulator which lets you choose how many balls are dropped onto the top pin and how
many pins are on the bottom row, counting the number of balls which land in each bin below the pins if
they randomly bounce off to the left or right.
In the Calculator here, the histogram of the number of balls in each box
empty boxes are omitted at either side.
A Simulator
Quincunx S I M U L A T O R
Drop balls
falling into bins
Show pins?
R E S U L T S
There is a very nice
Maths is Fun simulation of a quincunx
showing each ball bouncing as it falls.
You do the maths...
Make a real Galton Quincunx.
If you have a lot of nails and a lot
of little balls (good sources for these are
small steel ball-bearings
from a bicycle shop or ping-pong balls for a large version
or even dried peas or other cheap round seeds from the supermarket)
then they end up forming a shape in the containers that is
very much like the Bell curve of the
previous exploration.
You will need to space the nails so they are as far apart as about
one and a half times the width of the balls you are using.
This makes a good practical demonstration for a Science Fair
or Open Day
at your school or college.
Block Walking
The Quincinx of the last section gives us another interpretation of the Binomial coefficients of
Pascal's Triangle, called Block Walking invented by George Polya.
x
y
00
1
2
3
4
5
1
ABC
2
3
4
Imagine that the Quincunx is turned on its side so that the balls fall down on the sloping diagonal
to the right. The board is then a map of part of a city where the roads are laid out in a grid, such as in New York.
The pins become the (square) blocks and the roads are the edges around them that the falling balls travel along.
We count the number of shortest paths
from top left corner (n=0,r=0) to the intersection n rows down and r columns across
travelling only to the right or down.
There is clearly just 1 way to reach each intersection on the top edge and on the left edge.
There is 1 way to reach point A (n=0,r=1): going to the next intersection right from the origin.
There is 1 way to reach point B (n=1,r=0): going 1 block down from the origin.
So there are 2 ways to reach point C (n=1,r=1).
In general, the number of ways to reach a given intersection is
the number of ways to get to the intersection above it (then go down)
PLUS the number of ways to get to the intersection to its left (and then go right), which is just the
Pascal's Triangle Addition (Recursion) formula.
Here is a table of the number of different shortest paths from the Origin to each intersection:
0→
1→
1→
1→
↓ 1→
↓ 2→
↓ 3→
↓ 4→
↓ 1→
↓ 3→
↓ 6→
↓ 10→
↓ 1→
↓ 4→
↓ 10→
↓
↓
↓
Each intersection is identified by the number of Downs and the number of Rights
to reach it.
Given the number of Ds and Rs then any order of Ds and Rs will get to the same location.
The paths are found by computing the subsets of the numbers 1 to #D+#R
( the number of Ds plus the number of Rs taken to reach the location).
So, for example, #D=4 and #R=2 intersection is reached in Binomial(6,4) ways to choose the
Ds which is, of course, the same as the number Binomial(6,2) which chooses the Rs.
Paths and Coins Calculator
Paths and Coins C A L C U L A T O R
for n=
and r=
R E S U L T S
Patterns in the Binomial Coefficients
Symmetry on rows
If we think of the Pascal's triangle element Binomial(n,r) as the number of ways to get r
heads when tossing n coins. For a fair coin this is the same number as tossing n coins and getting r tails.
But getting r tails is the same as getting n−r heads and that is Binomial(n-r,r).
For instance, tossing 6 coins there are Binomial(6.4) =15 ways to get 4 heads.
Use the Binomial Calculator above to produce the 15 subsets of {1,2,3,4,5,6} which
we can interpret as the number of the coins that are Heads, the missing numbers being Tails.
subset
coins 123456
{1,2,3,4}
HHHHTT
{1,2,3,5}
HHHTHT
{1,2,3,6}
HHHTTH
...
...
The number of ways of getting 4 heads is the same as the number of ways of getting 6-4=2 Tails
so that Binomial(6,4) and Binomial(6,6-4) = Binomial(6,2) must be the same number.
So any row can be reversed and still look the same:
Binomial(n,r) = Binomial(n,n-r) nCr = nCn−r
Row sums
If we interpret the Binomial coefficients as probabilities of getting a number (r) or Heads when throwing (n) coins,
then there are 2n possibilities because each coin in the toss has two possibilities (Head or Tail).
So the sum of all the entries in row n in Pascal's Triangle is 2n.
`\sum_{r=0}^{n} ([n],[r]) = 2^{n}`
Alternating sums along a row
The sum of the alternate elements along a row is the same as the sum of the elements not used:
The formulas below take a smaller Binomial coefficient and update it to get the next one
along a row or column of diagonal:
From one row to the next in the same column:
`([n],[r]) = \frac{n}{n-r}([n-1],[r])`, n>0, 0≤r≤n
From one column to the next on the same row:
`([n],[r])=\frac{n-r+1}{r}([n],[r-1])`, n>0, 0<r<n
From one row and column to the next row and column:
`([n],[r])=\frac{n}{r}([n-1],[r-1])`, 0<n, 0<r
Let's look at the hexagon of 6 numbers surrounding an element in Pascal's triangle, the two above, the two on either side
the same row and the two numbers below. For instance, the 4 on row 4, column 1 has these 6 neighbours:
13 1 4 6510
We have grouped them into two triangles (to make a Star of David pattern), alternating round the hexagon, one red and the other green.
If we multiply all those of the same colour, what happens?
We get the same product for both triangles:
in this case 1×3×10 = 1×6×5 = 30.
This is not a coincidence:
This works for any element of Pascal's triangle! n-1CrnCr-1n+1Cr+1
=
n-1Cr-1nCr+1n+1Cr
For the 1's at the ends of the rows, this product is 0 if we count a gap as having the value of 0.
The product of all the 6 neighbours in the hexagon will always be a square number.
A proof
Using The recursive definitionabove,
we want to show n-1CrnCr-1n+1Cr+1 =
n-1Cr-1nCr+1n+1Cr
LHS =
n-1Cr
nCr-1
n+1Cr+1
=
(n-1)!
n!
(n+1)!
r!(n-r-1)!
(r-1)!(n-r+1)!
(r+1)!(n-r)!
Rearrange the factorials in the denominator...
=
(n-1)!
n!
(n+1)!
(r-1)!(n-r)!
(r+1)!(n-r-1)!
r!(n-r+1)!
RHS =
n-1Cr-1
nCr+1
n+1Cr
Since the product of the 3 numbers in both triangles is the same,
the product of all 6 numbers will be a square number
The gcd of the triangles is the same
Another property of these two triangles is
The gcds of all the numbers in each triangle is the same
Since there is a 1 in each of the triangles for the example above, let's try
the hexagon around 126 on row 9, column 4:
567084 126 126210252
gcd(70, 84, 252) = 14 = gcd(56, 126, 210)
Hexagon Calculator
Hexagonal C A L C U L A T O R
around row= col=
R E S U L T S
The Hexagon Rule above is just a special case of the equation A K Gupta
published in 1974 (see References)
with r = s = 1. Here the Binomials rows and columns
are shown in a table indicating if they appear on the Left Hand Side or the Right Hand Side of this equality:
Column:
m-r
m
m+s
Row:
n-s
RHS
LHS
n
LHS
*
RHS
n+r
RHS
LHS
More recursions
`([n],[r])([r],[k]) = ([n],[k])([n-k],[r-k])`
which is easily proved by expanding each Binomial into its factorial form.
Sum of squares of a row
If we square every element on a row n, the total is another element of Pascal's triangle,
in the centre of row 2n, in column n:
For example, row n=4 is 1 4 6 4 1 and
1² + 4² + 6² + 4²+ 1² = 70 = Binomial(8,4)
`\sum_{k=0}^{n} ([n],[k])^2 = ([2n],[n])`
Proof by "Committees"
One way to interpret binomial coefficients is as when choosing members of a committee. So
Binomial(n,r) is the number of ways of selecting a committee of r people from n available to serve on it.
As an example of proving results by such reasoning, let's take the Sum of Squares result in the last section.
The RHS is Binomial(2n,n) so we are choosing a committee of n people from 2n available. If we think of those available
as being from two schools, for instance, then we have n members from each school available.
If we want to form a committee of n people to run a joint event, then we have Binomial(2n,n) ways to do this.
We can also think of it as having from 0 to n members from the first school on the committee,
the other n-k being chosen from the second school.
This is
`\sum_{k=0}^{n} ([n],[k]) ([n],[n-k])`
But, since the number of ways of choosing n-k from school 2 is exactly the same
as the number of ways of not choosing k of the available n
or, the Row Symmetry property that we found above, this is the same as
`\sum_{k=0}^{n} ([n],[k]) ([n],[k]) = \sum_{k-0}^n ([n],[k])^2` as so
`\sum_{k-0}^n ([n],[k])^2 = ([2n],[n])`
Proof by "block walking"
We know that we can think of Binomial(n,r) as the number of different paths in a city map of a grid of roads
to get from one intersection to another n blocks down and r blocks right by the shortest routes
(always travelling towards the destination).
So the Sum of Squares result is about the number of routes from an origin intersection to one
2n blocks right and n blocks down.
x
y
00
1
2
3
4
5
6
1
2
3
Clearly, we will have to cross the green vertical line of streets.
We can go via the top intersection: there are Binomial(3,0) ways to get to the topmost intersection
on this line, then a choice of Binomial(3,3) ways to get from there to our destination at the bottom right.
`([3], [0])([3],[3])` ways
or we go via the (3,1) intersection on the mid-line with Binomial(n,1) ways
to get to it then Binomial(n,2) ways from it to our
goal.
`([3],[1])([3],[2])`
Similarly there are Binomial(3,2) × Binomial(3,1) ways to go via the (3,2) intersection
`([3],[2])([3],[1])`
and finally
Binomial(3,3)×Binomial(3,0) ways via the bottommost midline intersection.
`([3],[3])([3],[0])`
This gives us all the ways to
get to our goal: Binomial(2n,n).
By the same argument as above, applying the Row Symmetry rule, we change the
second Binomials in each product to be identical to the first ones, and the result follows.
`\sum_{k=0}^{3} ([3],[k])^2 = ([6],[3])`
The Hockey Stick Theorems
Every number in the triangle is the sum of all of those numbers
in the diagonal leading up and left starting from the number above itand also the sum of all those numbers above it in the previous column
Select which you direction you want for the hockey stick handle
Click on a number in the triangle to see the hockey stick.
Hockey Sticks Demonstrator
Hockey Stick handle: :Left diagonal
OR :right diagonal
n
0
1
1
1
1
2
1
2
1
3
1
3
3
1
4
1
4
6
4
1
5
1
5
10
10
5
1
6
1
6
15
20
15
6
1
7
1
7
21
35
35
21
7
1
r=
↗ 0
↗ 1
↗ 2
↗ 3
↗ 4
↗ 5
↗ 6
↗ 7
The numbers used make a hockey stick shape in two orientations. For the handle going upwards to the left, we have for row n=7 and column r=3: 7C3 = 20 + 10 + 4 + 1 = 35:
(
7
)
=
(
6
)
+
(
5
)
+
(
4
)
+
(
3
)
3
3
2
1
0
The Hockey Stick Theorem 1:
`([n+r+1],[r]) = \sum_{i=0}^{r} ([n+i], [i])`
For the handle going up to the right, we have, for example, n=7,r=3: 7C3 = 15 + 10 + 6 + 3 + 1 + 0 + 0 = 35
(
7
)
=
(
6
)
+
(
5
)
+
(
4
)
+
(
3
)
+
(
2
)
+
(
1
)
+
(
0
)
3
2
2
2
2
2
2
2
The Hockey Stick Theorem 2:
`([n+1],[r+1]) = \sum_{i=r}^[n] ([i],[r])`
These are the same Theorem by row-symmetry
Since every row is symmetrical in that it is the same when reversed, then by flipping the
whole Triangle about a vertical axis and then choosing the mirror-image element on the same row, we see that each
of the two Theorems is just a reflection of the other.
Central Binomials
The binomial numbers in the centre of the even rows (those rows of Pascal's Triangle
that begin: 1, 2n, ...) are:
1, 2, 6, 20, 70, 252, 924, ... `frac{(2n!)}{(n!)^2}` A000984
They have some interesting applications:
The number of ways of getting exactly half Heads and half Tails when tossing an even number 2n of coins
(or 1 single coin 2n times) is Binomial(2n,n).
Dividing this by 22n (the total number of possibilities when tossing 2n coins)
gives the probability of getting the same number of Heads as Tails
For 4 tosses of a coin we have just 6 ways with half Heads and half Tails:
HHTT HTHT HTTH TTHH THTH THHT
out of the 24=16 possible
arrangements of Heads and Tails.
#coins
2
4
6
8
10
12
#equal
2
6
20
70
252
924
#possible
4
16
64
256
1024
4096
Probability
0.5
0.375
0.3125
0.2734
0.2461
0.2256
#coins
100
1000
1000000
#equal
1.001×1029
2.70×10299
7.89×10301026
#possible
1.27×1030
1.07×10301
9.90×10301029
Probability
0.0795
0.02522
0.0007979
Block sequences
Suppose a city has a grid system of roads similar to that in Manhattan in New York,
where avenues run north-south
and streets run East-West and each is numbered.
The number of shortest paths on a grid to go from one point (intersection of two roads)
to another point n blocks East and n blocks North
is Binomial(2n,n):
Or think of a square lattice and paths from (0,0) to (n,n) with steps going East:
1 unit (in the positive x direction) (1,0)
or one unit North (in the positive y direction) (0,1).
Since the path is n blocks right and n blocks north we need 2n steps. We can choose which n of them
are East then the remaining n will be North: Binomial(2n,n) possibilities.
Here is a diagram for
n=2 and there are 6 paths always going right or up each time.
A convenient way to represent each path is to list the number of each E-W street on the path. Or, viewing the
path as a bar-chart, what is the height of each bar from left to right.
In a tournament of games where the winner
is the "best of 3"="first to 2 wins", "best of 5"="first to 3 wins" and, in general,
"best of (2n-1)" = "first to n wins",
any odd number (2n-1) of games, how many patterns of game-wins are there before a winner is found or a draw declared?
For an even number of games there may be a draw but not if the number of games is odd.
For example,
best of 3 games = first to 2 wins
we could have the following 6 possible match results before a winner is found:
A wins:
B wins:
AA
BB
ABA
BAB
BAA
ABB
A Game Tree for 3 games (best of 3 games or first to 2 wins)
If we stop as soon as there is a clear winner (best of 3), we can show the games in a Game Tree
where horizontal and vertical lines mark the individual game's winner:
Here we have 2 wins out of 3 games for A and 2 wins out of 3 games for B;
1 way to win for each tam involving just 2 games.
.
A game tree for "best of 5"or "first to 3 wins"
Here A wins in 1+3+6=10 cases, B wins in the same number of cases.
Tracing the paths form the start in the lower-left corner to each of the numbers, with
A wins vertically and B wins horizontally
we have the following results:
There is one win for A in 3 games AAA and also for B with BBB;
There are 3 wins with the other team winning 1 and the winning team winning 3: BAAA, ABAA, AABA, for A
and ABBB, BABB, BABB with B winning;
There are 6 wins for each team where the other team wins 2:
ABABA, ABBAA, AABBA, BABAA, BBAAA, BAABA where A is victor and
BABAB, BAABB, BBAAB, ABABB, AABBB, ABBAB where B wins the tournament.
Why are there Binomial(2n,n) games in these tournaments?
If we use a block diagram with counts of the number of routes from the origin to that point, we get our usual Pascal's
triangle. Here a left track means a win for team A and a right track a win for team B.
We add the numbers above a location
because those from the left on the row above are before B won the latest game
and those from the right element are from
before A won.
If we want the best of (2n+1) which is the same as "the first to win n games" then we stop as soon as
n+r is (2n+1),
the winner being A for routes ending r<n and the winner being B if r>n and a draw if r=n.
For instance with n=1 for "best of 3" the games tree looks like this:
So there are 1+3 game paths ending with a win for A on the left side and the same on the right hand side
with wins for B. The 6 on the bottom row is the number of ways to get a draw.
For "best of 5" (first to 3) we have:
`([6],[3]) = 2 (([2],[0])+([3],[1])+([4],[3])) = 2 (1+3+6) = 20`
`([8],[4]) = 2 (( [3],[0])+([4],[1])+([5],[2])+([6],[3])) = 2(1+4+10+20) = 70`
and, in general:
`([2n],[n]) = 2 \sum_{r=n-1}^{2n-2} ([r],[r-n+1]) if n>0`
Central Binomials Calculator
Central Binomials C A L C U L A T O R
Binomial(2n,n)
all block paths (0,0) to (n,n)
games in first to win n games
grid diagram for first to win n games
for n=
R E S U L T S
Computing Binomials efficiently
By efficiently we mean using only integers and exact division to avoid the approximations of real
numbers and dividing.
The definition of Binomial(n,r) is
`([n],[r]) = frac{n!}{(n-r)!r!}` and `n! = n.(n-1).(n-2) ... 3.2. 1`
this formula as it stands involves three factorials:
>
`n!`, `(n-r)!` and `r!`
as well as dividing the first by the product of the
other two.
In practice, we see that in `(n!)/(r!)` all the bottom terms cancel with the last `r` numbers in the numerator's
factorial to give
`n.(n-1). ... .(n-r+1)` which involves no divisions.
However for Binomial(n,r)
we still need to divide `(n!)/(r!)` by `(n-r)!`
Exact integer limits
253−1 ≈9.0×1015 is the maximum exact whole number in many programming languages
(for example, JavaScript). Numbers larger than that are then automatically converted into real numbers (floating point numbers)
and are not exact. For example:
18! ≈ 6.4×1015 but
19! ≈ 1.2×1017
and so
Binomial(56,28) ≈ 7.6×1015 will be ok but
Binomial(57,28) ≈ 1.5×1016 will exceed the exact-integer limit
The 57-th row of Pascal's Triangle is the first row to have a value exceeding the 253−1 integer limit.
This causes programming problems if we want accurate computations for large Binomial values.
So we can ask the question:
Can we compute Binomials efficiently, not involving floating-point (real) numbers resulting from division?
Can we compute Binomials using only divisions that are exact?
Here are two ideas:
Is it possible to compute the terms by multiplying whilst ensuring that each divide will be
exact?
Can we avoid divisions altogether by computing directly
the power of each of the primes in the prime factorization of Binomial(n,r)?
We examine these questions now:
Updating Binomials
Since there are the same number of numbers to multiply in the numerator
of Binomial(n,r) as there are to divide by in the denominator,
we can try
`frac{n}{1} * frac{n-1}{2} * frac{n-2}{3} … * frac{n-r+1}{r}`
Will this ensure that we never get a fractional value after a division?
Yes! This is because if starting at the left of the expression above, having computed
Binomial(n,i) we can update it to Binomial(n,i+1)
by multiplying by (n-i+1) and dividing by (i+1). We start with i=1 and go up top i=r:
`frac{n.(n-1). ... .(n-i+1)}{1.2 ... .i} = ([n],[i])`
`frac{n.(n-1). ... .(n-i+1)}{1.2 ... .i} \color{blue}{frac{(n-i)}{(i+1)}} = ([n],[i+1])`
Both of the above are integers
and so we see that the following will always involve exact division:
`([n],[i+1]) = ([n],[i])frac{n-i}{i+1}`
As i goes from 1 to r, starting from B=Binomial(n,1)=n, we multiply and divide to update B
to Binomial(n,2) then Binomial(n,3) until we reach B = Binomial(n,r) and
we can compute all these values as exact whole numbers.
Here is a computer program to do this efficiently; first we deal with the values of n and r that give 0 or 1 in Pascal's
Triangle, then we check if the Row Symmetry rule might reduce the number of times we multiply-and-divide:
To compute Binomial(n,r) as a function whose result is the value to return
Key
.
indicates that the program can exit the function
ASSERT
shows what limits there are on the values of n and r at that point in the code.
←
copies the value on its right into the variable on its left.
We must ensure that
Binomial(0,0) = Binomial(0,r) = Binomial(n,0) = 1 for all r>0 and all n>0
Binomial(n,r) = 0 if r<0 or n<0 or r>n.
Input n and r
ASSERT r and n are integers
If(n<0) result is 0.
ASSERT n ≥ 0, r is an integer
If(r<0) result is 0.
ASSERT r ≥ 0 and n ≥ 0
If(r>n) result is 0.
ASSERT 0 ≤ r ≤ n
If(r=0) result is 1.
ASSERT 0 < r ≤ n or n = 0
If(n=0) result is 1.
ASSERT 0 < r ≤ n
If(n=r) result is 1.
ASSERT 0 < r < n
If(n-r<r) r=n-r
ASSERT 0 < r ≤ n/2
B ← 1;
For i ← 0 up to r-1 in increments of +1:
B ← B * (n - i) / (i + 1);
result is B.
The 8 Neighbours recursions
Here are the formulas to update Binomial(n,r) to find each of its 8 neighbours:
Prove each of the above formulas for the 8 neighbours.
Hint: One way is to use the factorial formula for each and compare it to `([n],[r])`
Legendre's Prime Power Factors in Binomial(n,r)
Our second idea is to work solely with the prime factorization of n! using an amazing result of A Legendre.
For each prime in the factorization of Binomial(n,r) (each prime ≤ n)
we write n in base p and
let s be the sum of the base p digits of n,
then the power of prime p
that occurs in the prime factorization of n! is given by `(n-s)/(p-1)`.
.
He gave a slightly different but equivalent definition:
Legendre's Formula
`\nu_p(n!) = \sum_{i=1}^{} \lfloor n/p^i \rfloor`
Eventually the prime power will become too big and resulting terms in the sum will be 0.
This uses a beautifully simple way to calculate the power of each prime
that factorizes n!.
If p, a prime, is a factor of n! then it occurs as a factor
exactly `frac{n - s}{p - 1}` times,
where `s` is the sum of the digits of n in base p
or, equivalently, the power of p is
the sum of the quotients when computing n in base p
For example, let's look at 12! and find the number of times 2 is a factor:
To do this, write 12 in the base p, the prime whose power we want to find:
2
12
2
6
remainder 0
2
3
remainder 0
2
1
remainder 1
0
remainder 1
so 12 in base 2 (binary) is 1100 (reading the remainders upward).
You can see that
the sum of the quotients 6 + 3 + 1 + 0 = 10
PLUS the sum of the base 2 digits 0 + 0 + 1 + 1 = 2
is n = 12 itself.
Legendre showed that this is always the case for any number in base 2.
The maximum power of 2 that is a factor of 12! is 12 - (sum of binary digits)
divided by one less than the prime 2 (so we divide by 1)
and the sum of the digits 1 1 0 0 is 2 so the power of 2 involved in 12!
is (12 - 2)/1 = 10.
So the prime factorisation of 12! begins 210
For other primes the general formula is
Legendre's Theorem The sum of base-p digits of n PLUS (p-1) times the sum of the quotients is always n
Let's look at how many times the prime 3 is a factor of 12!
Express 12 in base 3:
3
12
3
4
remainder 0
3
1
remainder 1
0
remainder 1
so 12 in base 3 (termary) is 110
Note that n = 12 = (1+1+0) + (3-1) × (4+1+0)
The sum of the base 3 digits of 12 is 1 1 0 = 2 and so the power of 3
we need is (12-2)/(3-1) = 5.
It is also the sum of the quotients: 4 + 1 + 0 = 5
So now we have 12! = 210 ×35.
Repeating with p=5, p=7 and finally p=11
(all the primes up to 12)
we get the full factorization of 12! as
12 ! = 210355271111
which we can easily check by expanding 12! as
12 ! =
12
×11
×10
×9
×8
×7
×6
×5
×4
×3
×2
×1
2×2×3
11
2×5
3×3
2×2×2
7
2×3
5
2×2
3
2
You can see the above working for any factorial in this Calculator which uses exact integers of many digits
and is practically instantaneous even for 1000!
Patterns in the Prime Factors of Binomial(2n,n)
All primes from n+1 up to 2n are factors of Binomial(2n,n)
This was known to Chebychev in 1850 ccording to Pomerance 2015
No prime from 2n/3 to n are factors of Binomial(2n,n)
Other patterns are observable in these graphs
Graph of n against the prime factors of Binomial(2n,n) with
y=n and y=2n/3 lines:
The gap ends on y=n+1.
Factorial Factors Calculator
This Calculator will illustrate Legendre's method of factorizing n! using the base p
representations of n for each prime p:
Factorial's Prime Factors C A L C U L A T O R
of
of
prime in
!
!!
of
leave lower input empty for ALL of the row
(
)
R E S U L T S
You do the maths...
How many zeroes are there at the end of 100!?
[Hint: There are more 2's in the factorisation of 100! than 5's] Answer
The number of zeroes is the number of times 10 is a factor of 100!
10 is 2×5 so in the prime factorisation of 100! we count
the pairs of a 2 with a 5.
There are more 2s as factors than there are 5s so we just count the number of times 5 is a factor
Using the calculator above -- or the formula counting the quotients when computing 100 in base 5:
5
100
5
20
remainder 0
5
4
remainder 0
0
remainder 4
Sum of quotients is 20 + 4 + 0 = 24
There are 24 zeroes at the end of 100!
Find a simple argument that shows
Every product of n consecutive whole numbers is divisible exactly by n!
Answer
Suppose the n consecutive integers are x+1 up to x+n.
Then `([x+n],[x]) `
` = frac{(x+n)!}{(x+n-x)! x!} = frac{(x+n)!}{n! x!}`
` = frac{ (x+n)(x+n-1)...(x+1)}{n(n-1)... 3.2.1 }
frac{\color{red}{x(x-1)...3.2.1}} {\color{red}{x(x-1)...3.2.1 }}`
` = frac{ (x+n)(x+n-1)...(x+1)}{n(n-1)... 3.2.1 } `
is a whole number (because it is a binomial coefficient in Pascal's Triangle)
so n! (the denominator) must divide exactly into the numerator which is
the product of the n numbers (x+1) ... (x+n)
For which values of `n` is `frac{n!}{n+1}` an integer? Answer
By testing to see if n+1 is a factor of n! using the Calculator, we find the first few values are
5, 7, 8, 9, 11, 13, 14, 15
Consulting the OEIS we find A118742
is Numbers n for which the expression n!/(n+1) is an integer.
and is also the list of numbers after 3 for which the (n+1) is not a prime.
For a proof see the link.
The Hidden Hexagon Squares V E Hoggatt, W Hansell Fib Q 9 (1971) pages 120, 13.
Generalised Hidden Hexagon Squares A K Gupta,Fib Q 12 (1974), pages 45-46.
Concrete Mathematics
(2nd edition, 1994) by Graham, Knuth and Patashnik, Addison-Wesley has a lot on binomials and formulas
that is quite accessible even though much of the rest of the book is at university level.
History of Pascal's Triangle
by Mrs Wheeler is a good summary of earlier records of the Triangle before Pascal studied it
Divisors of the Middle Binomial Coefficient C Pomerance,
Amer. Math. Monthly 122 (2015) pp 636-644
PDF
Computing Binomial Coefficients P Goetgheluck, Amer Math Monthly vol 94 (1987), pp 360-365
has a simple program to compute the power of each prime in binomial(n,r)
Théorie des nombres A Legendre, (ed 2 1808, ed 3 1830) gives the
formula for the highest power of prime p that is a factor of n!
History of the Theory of Numbers, Vol 1:Divisibility and Primality L E Dickson
(1919, Dover 2005 paperback) chapter 9 has a compact history of the Legendre theorem
How Often Does an Integer Occur as a Binomial Coefficient?
D Singmaster,
American Mathematical Monthly 78 (1971) pages 385-386
icon means there is a
You Do The Maths... section of questions to start your own investigations.
calculator icon
indicates that there is a live interactive calculator in that section.
Calculating probabilities.
simulation of a quincunx
showing each ball bouncing as it falls.
