## A Better Lottery?

```Questions are frequently asked about the odds of winning a lottery, and
it usually seems to be the same type of lottery, whether it's in the UK
or in various US states.  The player selects k distinct integers from
the range 1 to N.  Then the "house" randomly chooses k distinct numbers
from the same range, and the player's winnings depend on how many of
his numbers match the "house" numbers.  Someone usually explains that
the probability of matching j numbers is

C(N-k,k-j) C(k,j)
-----------------
C(N,k)

where C(m,n)=m!/(n!(m-n)!).  Although this gives a pedagogically useful
motivation for (and proof of) the elementary identity

k
______
\       /     \   /   \          /   \
>    |  N-k  | |  k  |        |  N  |
/     |  k-j  | |  j  |    =   |  k  |
------  \     /   \   /          \   /
j = 0

it isn't a particularly challenging structure.  Suppose we drop the
requirement for DISTINCT integers.  Let's say when you purchase a
"chance" you are given five randomly selected integers from the range
1 to 45, DUPLICATIONS ALLOWED.  Then the house randomly selects five
integers from the same range (again, duplications allowed).  What is
the probability of matching the house's multi-set of five numbers
exactly?  (Note that the order of selection is unimportant.)

This seems like a more interesting process because the result occurs
in two stages.  First, your personal numbers are selected and, although
this doesn't determine whether you win or lose, the partition you draw
does determine your odds of ultimately winning. (Ideally you would hope
to get five distinct numbers, because that gives you the best odds,
whereas five of a kind gives the worst odds.)  Then the house draws its
numbers to actually determine the winner(s).

Whether this scheme actually has more popular appeal than the
conventional method, it certainly is a bit more challenging to
figure the odds.  The seven possible partitions are

aaaaa          45 = (45)                           1
aaaab        1980 = (45)(44)                       5
aaabb        1980 = (45)(44)                      10
aaabc       42570 = (45)(44)(43)/2                20
aabbc       42570 = (45)(44)(43)/2                30
aabcd      595980 = (45)(44)(43)(42)/6            60
abcde     1221759 = (45)(44)(43)(42)(41)/120     120

The product in the center column is the number of possible occurrences
of the respective partition, without regard to order of selection.  The
right hand column gives the number of distinct sequences that can give
each of the occurrences of the respective partition.

Suppose you draw a multi-set of numbers with the partition "aabcd".
Out of the 45^5 possible selection sequences, there are (60)(595980)
that give this partition, so your probability of drawing one of these
is (60)(595980)/(45^5).  Then to actually win you need the house to get
one of the 60 selection sequences that give your specific values of a,
b, c, and d.  So your odds of actually winning, given a multi-set of
the form aabcd, are 60/(45^5).  The odds for the other partitions can
be figured out in the same way, and the combined result is that your
overall probability of winning is

{ 45(1)^2 + 1980(5)^2 + 1980(10)^2 + 42570(20)^2 + 42570(30)^2

+ 595980(60)^2 + 1221759(120)^2 } / (45^10)

=  19794608145/45^10  =  5.81E-7