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

Author(s):
pk,i k = 1 k = 2 k = 3 k = 4
i=0
 n-t n

 (n-t)(n-t-1) n(n-1)

 (n-t)(n-t-1)(n-t-2) n(n-1)(n-2)

 (n-t)(n-t-1)(n-t-2)(n-t-3) n(n-1)(n-2)(n-3)

i=1
 t n

 2t(n-t) n(n-1)

 3t(n-t)(n-t-1) n(n-1)(n-2)

 4t(n-t)(n-t-1)(n-t-2) n(n-1)(n-2)(n-3)

i=2
 t(t-1) n(n-1)

 3t(t-1)(n-t) n(n-1)(n-2)

 6t(t-1)(n-t)(n-t-1) n(n-1)(n-2)(n-3)

i=3
 t(t-1)(t-2) n(n-1)(n-2)

 4t(t-1)(t-2)(n-t) n(n-1)(n-2)(n-3)

i=4
 t(t-1)(t-2)(t-3) n(n-1)(n-2)(n-3)

Table 2: Summary of Problems 1-4

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, p1,1 = t/n and p1,0=1- p1,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. Similary, in the calculation of p2,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 p2,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
 i
ö
÷
÷
ø
will always be a factor of pk,i. Let's introduce one more piece of modern notation, by letting
sk,i = pk,i

æ
ç
ç
è
 k
 i
ö
÷
÷
ø
,       so that    pk,i = æ
ç
ç
è
 k
 i
ö
÷
÷
ø
sk,i.

In Problem 5, Euler asks for the general form of pk,i. He introduces r=n-t and writes out the cases k=1, 2, ¼, 6 in this new notation. Observing the pattern, sk,i is seen to be:

 t(t-1)¼(t-i+1)r(r-1)¼(r-(k-i)+1) n(n-1)(n-2)¼(n-k+1) ,
where 0 £ i £ k, 1 £ k £ t £ n, and k £ r=n-t.

Euler does not use this notation, nor does he explicitly give a formula for the general value of sk,i. His notation is as follows:

 Ai
 =
 s1,i
 Bi
 =
 s2,i
 Ci
 =
 s3,i
 Di
 =
 s4,i
 etc.

In Corollary 1 to Problem 5, Euler observes that the sk,i can be given recursively. We may give an explicit formulation as follows. Let

 s1,0= n-t n

and
 s1,1= t n

from Problem 1; then for k > 1, and 0 £ i < k:
 sk,i = r-(k-i)+1 n-k+1 sk-1,i.
Also,
 sk,k = t-k+1 n-k+1 sk-1,k-1.
In Euler's notation, these formulas are given as follows:
 A1= t n ,     A0= r n ;

 B2= t-1 n-1 A1,     B1= r n-1 A1,     B0= r-1 n-1 A0;

 C3= t-2 n-2 B2,    C2= r n-2 B2,     C1= r-1 n-2 B1,     C0= r-2 n-2 B0;

 D4= t-3 n-3 C3,     D3= r n-3 C3,     D2= r-1 n-3 C2,     D1= r-2 n-3 C1,     D0= r-3 n-3 C0;

 etc.

Robert E. Bradley, "Euler's Analysis of the Genoese Lottery - Probabilities in the Genoese Lottery (continued)," Loci (August 2010)