View Question
 Question
 Subject: Random, probability, statistics. Yum! Category: Science > Math Asked by: alexander-ga List Price: \$5.00 Posted: 27 Jun 2004 13:20 PDT Expires: 27 Jul 2004 13:20 PDT Question ID: 366992
 ```iPod with 100 albums, each with 10 songs. Given a random run of 10 songs where songs do not repeat, what is the probability that two songs of the ten will be from the same album? Three? Four? Explain.```
 Subject: Re: Random, probability, statistics. Yum! Answered By: mathtalk-ga on 28 Jun 2004 05:40 PDT Rated:
 ```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``` Clarification of Answer by mathtalk-ga on 28 Jun 2004 05:50 PDT ```Technically my terminology "ordered partitions" used above is incorrect. While I was alluding to the "descending order" of the summands, the mathematical usage is for a partition in which the order of the summands "makes a difference". If two partitions are "the same" up to reordering of the summands, as we have here, it is actually called an "unordered partition". [PlanetMath: integer partition] http://planetmath.org/encyclopedia/UnorderedPartition.html regards, mathtalk-ga```
 alexander-ga rated this answer: and gave an additional tip of: \$10.00 `mathtalk-ga is awesome. :D`

 ```HI,Alexander: By saying" two songs of the ten will be from the same album", do you mean that only two songs are from the same album but no other two songs are from another ablum and there could not be 3 or more songs from the same album? or do you mean that as long as there are two songs from same album? THanks Peter Jiang```
 ```I mean as long as there are at least two songs from the same album. Should have stated it more clearly.```