Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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



Trying to fix part (3) :

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

share|cite|improve this question
up vote 2 down vote accepted

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}\;.$$

share|cite|improve this answer
Got it , thanks . So this means that my answer for (3) is also wrong , so I guess it should be something like my edited version ,can you please check ? thanks ! – ron Apr 11 '12 at 9:34
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.