Euler's Analysis of the Genoese Lottery - Probabilities in the Genoese Lottery (continued)

Euler's reasoning is entirely elementary, and each Problem builds on the results of the previous one. If \(k=1\), the player is choosing just one number from among n. Since t of these will be winning numbers, \(p_{1,1}\) = t/n and \(p_{1,0}=1-p_{1,1}\).

To calculate the probabilities when \(k=2\), we can think of the player as choosing the two numbers one at a time. Therefore, there are \(n-1\) ways to choose the second number, having made the first choice from among n. This accounts for the denominator \(n(n-1)\) in all three of the probabilities in the second column of Table 2. The case \(k=2, i=2\) arises from choosing one of the t winning numbers first, and one of the remaining \(t-1\) winning numbers next. Similarly, in the calculation of \(p_{2,0}\), the player first chooses one of the \(n-t\) losing numbers, and then chooses one of the remaining \(n-t-1\) losing numbers. The interesting case is \(i=1\). There are two ways this can happen, either by choosing a winning number followed by a losing number, or by choosing a losing number followed by a winning number. There are t good choices and \(n-t\) bad choices, so the numerator of \(p_{2,1}\) has to be \(2t(n-t)\).

Elements of the pattern in Table 2 gradually come into focus quickly. Particularly noteworthy is the presence of binomial coefficients. The details of Euler's solutions of Problems 1–4 make this identification certain, as the coefficient of every entry in each column, except the first and last, arises a sum of two coefficients in the previous column, thereby obeying precisely the same recursive formula as the entries in Pascal's triangle. For example, one can bet on \(k=4\) numbers, and get \(i=2\) of them correct in two different ways: either by matching 2 of the first 3 numbers bet upon, and then failing to match on the fourth one, or by matching only 1 of the first 3, and then succesfully matching the fourth one. Therefore, the binomial coefficient

\(k \choose i \)

will always be a factor of \(p–{k,i}\). Let's introduce one more piece of modern notation, by letting

\(s_{k,i}=\frac{p_{k,i}}{k \choose i}\)

so that

\(p_{k,i}={k \choose i}s_{k,i}\)

In Problem 5, Euler asks for the general form of \(p_{k,i}\). He introduces \(r=n-t\) and writes out the cases \(k=1,2, \dots, 6\) in this new notation. Observing the pattern, \(s_{k,i}\) is seen to be:

\(\frac{t(t-1)\cdots(t-i+1)r(r-1)\cdots(r-(k-i)+1)}{n(n-1)(n-2)\cdots(n-k+1)}\)

where \(0 \leq i \leq k\), \(1 \leq k \leq t \leq n\), and \(k \leq r = n-t\).

Euler does not use this notation, nor does he explicitly give a formula for the general value of \(s_{k,i}\). His notation is as follows:

\(A^i = s_{1,i}\)

\(B^i = s_{2,i}\)

\(C^i = s_{3,i}\)

\(D^i = s_{4,i}\)

etc.

In Corollary 1 to Problem 5, Euler observes that the \(s_{k,i}\) can be given recursively. We may give an explicit formulation as follows. Let \(s_{1,0}=\frac{n-t}{n}\) and \(s_{1,1}=\frac{t}{n}\) from Problem 1; then for \(k > 1\), and \(0 \leq  i < k\):

\(s_{k,i}=\frac{r-(k-i)+1}{n-k+1}s_{k-1,i}\)

Also,

\(s_{k,k}=\frac{t-k+1}{n-k+1}s_{k-1,k-1}\)

In Euler's notation, these formulas are given as follows:

\(A^1=\frac{t}{n} , A^0=\frac{r}{n}\) ;

\(B^2=\frac{t-1}{n-1}A^1 , B^1=\frac{r}{n-1}A^1 , B^0=\frac{r-1}{n-1}\) ;

\(C^3=\frac{t-2}{n-2}B^2 , C^2=\frac{r}{n-2}B^2 , C^1=\frac{r-1}{n-2}B^1 , C^0=\frac{r-2}{n-2}B^0\) ;

\(D^4=\frac{t-3}{n-3}C^3 , D^3=\frac{r}{n-3}C^3 , D^2=\frac{r-1}{n-3}C^2 , D^1=\frac{r-2}{n-3}C^1 , D^0=\frac{r-3}{n-3}C^0\) ;

etc.

Editor’s note: This article was published in April 2004.