# Probability using C(n,k)

Given the following problem :

A group of students got homework assignment where they need to pick a group of

functions and sort them .The students need to pick 5 pairs of functions and prove

some relation between them.


1.Given that there are 16 function in the group , how many pairs can we have ?

Answer : Using C(n,k) , we have C(16,2) = 16 above 2 = 120 , hence , we have 120 options for pairs .

2.Assuming that each student chose randomly the 5 pairs independently , what's the

probability that two students chose the exact same 5 pairs of functions ?

Answer : probability for choosing 5 function is : $5/120$ , where $120$ was calculated

in the previous exercise . Hence , the probability for two students to choose the exact

same functions is : $$(5/120)^2$$ .

3.Assume that we have 100 students , find the upper bound to the probability that there

are two students with the exact same 5 functions

Answer : $$C(100,2)∙(5/120)^2$$ = $$4950 ∙ (5/120)^2$$

I'd appreciate any feedback and/or corrections regarding this exercise

Regards

EDIT :

Trying to fix part (3) :

Answer : $${\binom{100}2} ∙ \frac1{\binom{120}5}$$

-

Your calculation that there are $\binom{16}2=120$ possible pairs of functions is correct, but after that you go astray. By the same reasoning that you used in (1), there are $\binom{120}5$ different sets of $5$ pairs that a student could choose. Now consider the probability that students $A$ and $B$ choose the same $5$ pairs. Whichever $5$ pairs $A$ chooses, $B$ has $1$ chance in $\binom{120}5$ of choosing the same set of $5$ pairs, so the answer to (2) is $$\frac1{\binom{120}5}=\frac1{190,578,024}\;.$$
I’m not sure just what sort of calculation they’re looking for in (3). Suppose that no two students pick the same $5$ pairs. Then altogether they’ve chosen $100$ of the $\binom{120}5$ possible sets of $5$ pairs; there are $$\binom{\binom{120}5}{100}$$ ways to do this. They can choose a collection of $100$ sets of $5$ pairs in $100!$ different orders, so there are $$\binom{\binom{120}5}{100}100!$$ different ways in which they could end up all having different sets of pairs. Since there are $100^{\binom{120}5}$ ways for them to choose pairs, the probability that no two choose the same $5$ pairs is $$\frac{\binom{\binom{120}5}{100}100!}{100^{\binom{120}5}}\;,$$ and the probability that some two of them choose the same set of pairs is $$1-\frac{\binom{\binom{120}5}{100}100!}{100^{\binom{120}5}}\;.$$ Abbreviating $\binom{120}5$ as $n$, we can write this as $$1-\frac{\binom{n}{100}100!}{100^n}=1-\frac{n!}{(n-100)!100^n}\;.$$ For a very crude estimate we can note that $$\frac{n!}{(n-100)!}>1\;,\tag{1}$$ so $$\frac{n!}{(n-100)!100^n}>\frac1{100^n}\;,$$ and $$1-\frac{n!}{(n-100)!100^n}<1-\frac1{100^n}\;.$$
Of course the estimate in $(1)$ can easily be improved to give a better upper bound. For example, $$\frac{n!}{(n-100)!}>(n-99)^{100}\;,$$ so $$1-\frac{n!}{(n-100)!100^n}<1-\frac{(n-99)^{100}}{100^n}\;.$$
@ron: The reasoning used in your update to (3) doesn’t work. If there were $5$ functions instead of $16$, and $3$ students instead of $100$, the probability of a given pair of students picking the same $5$ pairs of functions would be $1/\binom{10}5=1/252$, and your reasoning would give an upper bound of $\binom32\frac1{252}\approx 0.012$, but the actual probability for which this is supposed to be an upper bound is more than $1-10^{-113}$. – Brian M. Scott Apr 11 '12 at 10:10