I decided to take apart the relevant information for people who want to try this problem:
- $200$ songs
- $13$ people, everyone able to choose $5$ (distinct) songs
What is the probability that at least 16 songs will be represented twice?
======
The Implausible Assumption Approach:
Suppose that $200$ is a suitable number to imply that the occurrence of one song being represented twice is independent from other songs being represented twice. Also, assume that $13$ is a suitable number to imply that one person's choice of a song is independent from another person's of a song. (The second assumption is not at all realistic.)
The probability that a (single) song is represented (exactly) twice is the probability that exactly two people choose the song, or
$$\dfrac{13!}{2!\text{ }11!}\left(\dfrac{1}{200}\right)^{2}\left(\dfrac{199}{200}\right)^{11} \approx 0.002 \text{.}$$
Furthermore, if $X$ is the number of songs represented exactly twice, we wish to find
$$\mathbb{P}\left(X \geq 16\right) = \sum\limits_{k=16}^{200}{200 \choose k}(0.002)^{k}(0.998)^{200-k}\approx7.83\times10^{-21}\text{,}$$
a very small number (for your purposes, pretty much $0$).
What I would do:
I would do some sort of Monte Carlo estimation of the probability. (I am by no means an expert on Monte Carlo.)
I ran the following code via Python:
from itertools import groupby
import random
geq_16_counter = 0
for j in range(--insert # of trials -- + 1):
songlst = []
for i in range(14):
songlst = songlst + random.sample(range(201), 5)
songlst = sorted(songlst)
songlst_freq = [len(list(group)) for key, group in groupby(songlst)]
if songlst_freq.count(2) >= 16:
geq_16_counter += 1
print geq_16_counter
What is this code doing? It looks at some number of 13 people (the "trials"), generates a unique number from 1 to 200 of size 5 for each person, throws all of these numbers into a list, and creates another list consisting of how frequently each song (numbers 1 to 200, that is) occurs. If the number of 2s is greater than or equal to 16, it adds one to a counter which counts how often the $\geq 16$ condition occurs. (There is a good chance my code is wrong somewhere... I'm a beginner at Python.)
Setting the number of groups of 13 people equal to 100 tended to give a number of 0. When increased to 1000, I saw numbers mostly from 1 through 5. At 10000, I saw numbers mostly in the 11-16 range. At 100000, I saw numbers in the 125-127 range.
This is by no means a good way to estimate the probability with a few iterations of the program, but my estimate would be
$$\dfrac{126}{100000} \approx 1.26\%\text{.}$$
I am currently running $1000000$ trials to see what I get and will post that up as well.
Edit: 1,000,000 trials gave me 1295, or
$$\dfrac{1295}{1000000} \approx 0.0013 = 0.13\%\text{.}$$
So it looks like the probability drops quite a bit.