If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

### Course: Math for fun and glory>Unit 2

Lesson 1: Brain teasers

# Path counting brain teaser

Counting paths in a square. Created by Sal Khan.

## Want to join the conversation?

• What is Pascal's triangle?
And what is a coefficient?
• what is binomial coefficient?
• In a binomial like (5x + 7)(3x + 2), 5 and 3 are binomial coefficients because a coefficient means the number behind the variable.
• At the third column to the left would have 0 on top of the one, so 0+1=1 1+2=3, 3+3=6,6+4=10,10+5=15, and 15+6=21. So +1,+2,+3,+4,+5,+6!
• there are more patterns
i.e. the diagonal goes up by 3(# of (nth term-1))+2^((2(nth term-1))-1) by their first differences
2,6,20,70,252 first differences are
4,14,50,182
Does that work for 4 to n?
3(# of (2nd term-1))+2^((2(2nd term-1))-1)
=3(# of 1st term)+2^((2(1st term))-1)
=3(4)+2^((2)-1)
=12+2^(1)
=12+2
=14
Let's try from 14 to n now.
3(# of (3rd term-1))+2^((2(3rd term-1))-1)
=3(# of 2nd term)+2^((2(2nd term))-1)
=3(14)+2^((4)-1)
=42+2^3
=42+8
=50
etc.
• How many ways does a 100*100 square have?
• A 100 by 100 square has 22,750,883,079,422,934,966,181,954,039,568,885,395,604,168,260,154,104,734,000 ways.
• So, What would be a 1,000 by 1,000 square?
(1 vote)
• A 1000 by 1000 square would have 512,294,053,774,259,558,362,972,111,801,106,814,506,359,401,696,197,357,133,662,490,663,268,680,890,966,422,168,317,407,249,277,190,145,438,911,035,517,264,555,381,561,230,116,189,292,650,837,306,095,363,076,178,842,645,481,320,822,198,226,994,485,371,813,976,409,676,367,032,381,831,285,411,152,247,284,028,125,396,742,405,627,998,638,503,788,368,259,307,920,236,258,027,800,099,771,751,391,617,605,088,924,033,394,630,230,806,037,178,021,722,568,614,945,945,597,158,227,817,488,131,642,780,881,551,702,876,651,234,929,533,423,690,387,735,417,418,121,162,690,198,676,382,656,195,692,212,519,230,804,188,796,272,372,873,746,380,773,141,117,366,928,488,415,626,459,630,446,598,074,332,450,038,402,866,155,063,023,175,006,229,242,447,751,399,777,865,500,335,793,470,023,989,772,130,248,615,305,440,000 ways.
• At , Sal mentions something called Pascal's Triangle. What is pascal's triangle?

• Great question!
Pascal's triangle is an array of binomial coefficients arranged in a triangle; where each number in the triangle is the sum of the two numbers above it.
here: https://en.wikipedia.org/wiki/Pascal%27s_triangle
• So this way is a bit like Fibonacci numbers?
• Yes, it is!
Pascal's Triangle has its diagonals sum to the Fibonacci sequence!
You can't post pictures here, though. Here's the link: http://shorturl.at/fkyA2
Here why in mathematical terms, the sum of the entries in the n-th diagonal of Pascal's triangle is equal to the n-th Fibonacci number for all positive integers n . shorturl.at/louB0
(1 vote)
• To get from S to star, you need to take 5 steps down and 5 steps to the right. Since these steps can be taken in any order, it is like asking how many permutations of 5 Ds and 5 Ls are possible. The answer is 10 choose 5 = 252. Is this explanation correct?