pk,i |
k = 1 |
k = 2 |
k = 3 |
k = 4 |
i=0 |
|
|
|
(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 |
|
|
|
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 |
|
|
|
|
6t(t-1)(n-t)(n-t-1)
n(n-1)(n-2)(n-3)
|
|
|
i=3 |
|
|
|
|
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
will always be a factor of
pk,i. Let's introduce one more piece of modern notation, by letting
sk,i = |
pk,i
|
, so that pk,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:
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
and
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:
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; |
|