A Lotto bet is picking 6 numbers out of 49 -- if you pick the correct combination, you get the jackpot!

If N persons play, there will be many repeats, since it's highly probable that some combinations will be chosen by two persons or more. (This is known as the "birthday paradox".)

What's the expected number of DIFFERENT combinations that will be chosen, if N persons play? (Assume these persons pick their combinations totally randomly.)

I can't get Charlie's formula to agree with Charlie's simulation results, so I will take a stab at another formula (and hopefully add to the knowledge here :-) )

I'm thinking that this may be the perfect place for a Stirling number of a second kind. Let S[n,d] be the number of ways of partitioning n objects into d non-distinct, non-empty sets.
d! S[n,d] will now count the permutations of placing the objects within the sets. Multiplying this by the binomial C[C[49,6],d] gives
C[C[49,6],d] d! S[n,d]
which counts all the ways n people can choose exactly d lotto numbers. dividing by all possibilities
C[49,6]^n
gives the probability. multiply this by d and summing over d gives the expected value
Sum[d C[C[49,6],d] d! S[n,d]/C[49,6]^n, d=1, n]

If we have more people than lotto combos, we would stop the sum at C[49,6]

I believe this can be simplified using a different approach of exclusion/inclusion, but I will leave that to someone else. Taking Charlie's suggestion, using 10 instead of C[49,6], the formula gives 8.78423 for 20 people and 9.99973 for 100 people.

(Spoiler) for referencing, this angle of the problem is known in the literature as the coupon collector problem (the birthday problem another angle of the same distribution); it is the kind of mathematics that is why parents should be deathly afraid of pokemon trading schemes.

Posted by owl on 2005-01-14 22:43:47