Hi, alexander-ga:
Here's a way to calculate the chance that all the songs will be from
different albums, assuming ten are chosen without repetition but with
equal probabilities.
Consider the order in which the songs are chosen. The first song can
be chosen in 1,000 ways (100 albums x 10 songs each), and all of these
choices are okay (no two from the same album yet). So far probability
of all songs from different albums is 1000/1000 = 1.
For the second song there are 999 possible choices, but only 990 of
these meet the restriction of no two from the same album. So at this
point the chance of having all songs from different albums is:
1 * (990/999)
Continuing in this fashion to choose all 10 songs, we will avoid
getting two from the same album with probability:
1 * (990/999) * (980/998) * (970/997) * . . . * (910/991)
= 10^10 * (100!/90!) / (1000!/990!)
= 0.657163295...
Therefore the chance of getting two or more from at least one album is
the complementary probability:
1 - 0.657163295... = 0.342836705...
To carry this sort of calculation to high number of repeats from any
album, we can calculate the chance of getting two (from at least one
album) and not more than two from any of the albums. This probability
is part of the chance shown above, and when it is subtracted away, the
remaining probability will be the chance of getting three or more from
at least one album.
Similarly the chance of getting four or more from at least one album
would be the result of subtracting from THAT the probability of
getting three (from at least one album) and not more than three from
any of the albums.
These calculations are a bit tedious because of the number of ways
that the songs may be distributed among the albums, with some album
having two songs and no album having more than two songs.
We could have:
a. one album with two songs, eight albums each with one song
b. two albums each with two songs, six albums each with one song
c. three albums each with two songs, four albums each with one song
d. four albums each with two songs, two albums each with one song
e. five albums each with two songs
Here we can consider the "universe" of probability to be combination
of the 1000 songs taken 10 at a time:
C(1000,10) = 1000!/(10!990!)
which in fact gives another way to compute the earlier chance of
getting no more than one song from any one album. One counts the
number of ways to choose 10 albums, times the number of ways to choose
one song from each of those albums, and divides by the number above,
the combinations of 1000 songs taken 10 at a time:
Pr(no more than 1 from any album)
= C(100,10) * 10^10 / C(1000,10)
But now we have to repeat this sort of analysis for each of the five
disjoint cases listed above:
a. There are C(100,1) ways to choose the album that will have two
songs, times the C(10,2) ways to choose two songs from it, times
C(99,8) ways to choose the other eight albums (each with one song),
times 10^8 ways to choose one song from each of those eight albums.
b. There are C(100,2) ways to choose the two albums that will each
have two songs, times the C(10,2)^2 ways to choose two songs from each
of them, times C(98,6) ways to choose the other six albums, times 10^6
ways to choose one song from each of those six albums.
c. There are C(100,3) ways to choose the three albums that will each
have two songs, times C(10,2)^3 ways to choose the two songs from each
of them, times C(97,4) ways to choose the other four albums, times
10^4 ways to choose one song from each of those four albums.
d. There are C(100,4) ways to choose the four albums that will each
have two songs, times C(10,2)^4 ways to choose the two songs from each
of them, time C(96,2) ways to choose the other two albums, times 10^2
ways to choose one song from each of those two albums.
e. There are C(100,5) ways to choose the five albums that will each
have two songs, times C(10,2)^5 ways to choose the two songs from each
of them.
Add the counts of cases a.-e., divide by C(1000,10), and that gives:
Pr(2 songs from some album, no more than 2 from any album)
and if this were subtracted from the previously computed:
Pr(at least 2 songs from some album)
the difference would be:
Pr(at least 3 songs from some album)
The corresponding case analysis for the situation of at least 3 songs
from one album and no more than 3 songs from any album, would break
out like this:
i. 3 songs from one album, seven albums with exactly one song
ii. 3 songs from one album, 2 songs from one album, five albums with
exactly one song
iii. 3 songs from one album, 2 songs from each of two albums, three
albums with exactly one song
iv. 3 songs from one album, 2 songs from each of three albums, one
album with exactly one song
v. 3 songs apiece from two albums, four albums with exactly one song
vi. 3 songs apiece from two albums, 2 songs from one album, two albums
with exactly one song
vii. 3 songs apiece from two albums, 2 songs from each of two albums
viii. 3 songs apiece from three albums, one album with exactly one song
These "cases" correspond to what are called ordered partitions, in
this situation, ways to write 10 as the sum of positive integers. For
example, the eight cases just mention correspond to these (descending)
sums:
i. 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1
ii. 3 + 2 + 1 + 1 + 1 + 1 + 1
iii. 3 + 2 + 2 + 1 + 1 + 1
iv. 3 + 2 + 2 + 2 + 1
v. 3 + 3 + 1 + 1 + 1 + 1
vi. 3 + 3 + 2 + 1 + 1
vii. 3 + 3 + 2 + 2
viii. 3 + 3 + 3 + 1
Fortunately past this point, when we start to classify the ways some
album could have four songs (and no album more than four), the
branching reaches a kind of bottleneck and the computation doesn't get
much worse. We'd only have these partitions to contend with:
4 + 1 + 1 + 1 + 1 + 1 + 1
4 + 2 + 1 + 1 + 1 + 1
4 + 2 + 2 + 1 + 1
4 + 2 + 2 + 2
4 + 3 + 1 + 1 + 1
4 + 3 + 2 + 1
4 + 3 + 3
4 + 4 + 1 + 1
4 + 4 + 2
followed (if you wanted it carried further) by the ordered partitions
of 10 in which at least one summand is 5 but no summand is greater
than 5, etc.
regards, mathtalk-ga |
