You’ve seen Pascal’s triangle before:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
You get the number in each row by adding its two ‘parents’ - for instance, each 10 in the row that starts with 1 then 5 comes from adding the 4 and 6 above it. (Somewhat oddly, that’s normally called the 5th row, even though it’s 6th from the top; the sums get a lot simpler if you call the top row ‘row 0’.)
It’s named after Blaise Pascal, 17th century French philosopher who invented the calculator and was one of the first to talk about probability in any depth.
(It comes up in the binomial expansion and in the binomial distribution - you might almost think the two things were somehow related).
So, even though Pascal invented a calculator, it almost certainly didn’t have an $^nC_r$ button on it. It’s possible, though, to work out rows of Pascal’s triangle on the fly. Here’s how the mathematical ninja would do it.
Let’s say you wanted to find the 5th row. You’re going to need to keep two numbers in mind: the timesy number (which starts as 5) and the dividey number (which starts at 1).
The first number in every row is 1, so write that down. Multiply the previous number (1) by the timesy number ($1 \times 5 = 5$) and divide by the dividey number ($5 \div 1 = 5$). That’s the second number.
Now, drop the timesy number by 1 to get 4, and increase the dividey number by 1 to get 2, and repeat the process: the previous answer, $5 \times 4 \div 2 = 10$. There’s the 3rd number.
Keep going: nudge the timesy number up to 3 and the dividey number down to 3. $10 \times 3 \div 3 = 10$. There’s number 4.
If you keep going, you get back to 1 (and then, of course, 0).
It works for any row (try it, and confirm with your calculator if you must).
For bonus points, try to figure out the Pascal’s Triangle entries with negative numbers - what does the -2nd row look like?
Edited 2015-03-08 and 2016-12-28 to fix LaTeX.
A selection of other posts
subscribe via RSS