In Brazil’s Mega-Sena lottery you choose 6 numbers out of 60. How many different tickets are there? Listing them all would take a lifetime: there are more than fifty million. But you can count without listing, and Pascal showed how.

Choosing without order

Start with a small case: in how many ways can you choose 2 people out of a group of 5 to form a committee?

If order mattered, there would be $5$ options for the first person and $4$ for the second: $5\cdot4=20$. But on a committee “Ana and Bruno” is the same as “Bruno and Ana”, and every pair has been counted twice. There are $20/2=10$ committees.

In general, the number of ways of choosing $k$ things out of $n$, regardless of order, is

$$\binom nk=\frac{n!}{k!\,(n-k)!},$$

where $n!=n\cdot(n-1)\cdots2\cdot1$. It is read “$n$ choose $k$”. For the committee, $\binom52=\frac{120}{2\cdot6}=10$.

Why they are the numbers of the triangle

Pascal noticed that $\binom nk$ is exactly the number $C(n,k)$ of the arithmetic triangle. The reason is the same addition rule.

Pick one person in the group, say Ana. Every committee of $k$ people out of $n$ either includes Ana or does not. If it does, we still have to choose $k-1$ people from the other $n-1$. If it does not, all $k$ people come from the other $n-1$. So

$$\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k},$$

which is the rule of the triangle. Since both start with the same $1$s on the edges and obey the same rule, they are the same table.

The Mega-Sena

Now the big calculation is easy:

$$\binom{60}{6}=\frac{60\cdot59\cdot58\cdot57\cdot56\cdot55}{6\cdot5\cdot4\cdot3\cdot2\cdot1}=50{,}063{,}860.$$

A single ticket has a chance of one in just over fifty million. If you played one ticket a week, you would expect to wait, on average, almost a million years to win.

The power of a sum

The same reasoning explains another appearance of the triangle. When you multiply out

$$(a+b)^3=(a+b)(a+b)(a+b),$$

each term of the result picks $a$ or $b$ from each of the three brackets. To get $a^2b$, you must pick $b$ in exactly one of the three: there are $\binom31=3$ ways. That is why

$$(a+b)^3=a^3+3a^2b+3ab^2+b^3,$$

and, in general,

$$(a+b)^n=\sum_{k=0}^n\binom nk a^{n-k}b^k.$$

Taking $a=b=1$, the left side becomes $2^n$: once again the sum of row $n$. This formula holds for whole-number exponents. Ten years later Newton discovered what happens with fractional exponents: see the generalized binomial.

The drunkard’s walk

A man leaves the bar and tries to get home. At each step he goes forward ($F$) or back ($B$), with equal chance. After two steps, the possible paths are

$$FF,\quad FB,\quad BF,\quad BB.$$

In two of the four he is back where he started. With three steps there are eight paths: $FFF$, three with two $F$s, three with one $F$, and $BBB$. Notice that the count is the expansion of the binomial:

$$(F+B)^2=F^2+2FB+B^2,\qquad (F+B)^3=F^3+3F^2B+3FB^2+B^3.$$

After $n$ steps there are $2^n$ paths, and the chance of having taken exactly $k$ steps forward is

$$\frac{1}{2^n}\binom nk.$$

It is the fountain of bowls from the previous post, with steps instead of water. This model, the random walk, now describes the motion of molecules in a gas, share prices and the spread of a perfume through a room.

The first proof by induction

In the treatise, Pascal wanted to prove a property for all rows of the triangle: two neighbouring numbers in the same row are in the ratio

$$\frac{\binom{n}{k+1}}{\binom nk}=\frac{n-k}{k+1}.$$

He could not check infinitely many rows. So he argued in two steps: first, the property holds in the first row; second, if it holds in one row, then it holds in the next. Therefore it holds in all of them.

This argument is mathematical induction. Similar ideas had appeared before, but Pascal’s treatise is considered the first time it was stated clearly, as a method.

With this ratio, each number in a row comes from the previous one by a single multiplication, without building the whole triangle. In row 5: $1$, then $1\cdot\frac51=5$, then $5\cdot\frac42=10$, then $10\cdot\frac33=10$.

Exercise: what is the coefficient of a²b² in (a + b)⁴?

We must choose the two positions of $b$ among the four brackets: $\binom42=6$. Indeed, $(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4$.

Exercise: after 4 steps, what is the chance that the drunkard is back where he started?

He needs 2 steps forward and 2 back. The chance is $\dfrac{1}{2^4}\binom42=\dfrac{6}{16}=\dfrac38$, or 37.5%.

Sources: Pascal biography, MacTutor · the letters of Pascal and Fermat, in English translation.

All Pascal topics · ← Pascal’s triangle: build it by adding · The Chevalier de Méré’s dice and the fair split →

Image credits.