0
$\begingroup$

We have $M$ boxes $i\in\{1,\dots,M\}$ with each box containing $N$ balls of color $i$. Given $T<\min(M,N)$, how many ways can we choose $T$ balls such that atleast $2$ of them have same color and how many ways can we choose $T$ balls such that no $2$ of them have same color (same ball can be chosen more than once)? Can former be much smaller than latter?

$\endgroup$
0
$\begingroup$

The number of balls is irrelevant (if we have enough of them).

The first question can be reformulated as follows. Point at the boxes randomly. How many ways of pointing are there such that there is at least one box that you point at at least twice? So first you can choose one box that will be pointed at twice. There are $M$ such possibilities. By this, you have used up two possibilities of pointing. There are $T-2$ further opportunities to freely point at the $M$ boxes. The total is: $$MM^{T-2}=M^{T-1}.$$

In the second case you have to point at the boxes $T$ times such that no two boxes will be pointed at twice. First you can pick $M$ boxes then you can pick only $M-1$ boxes, and so on, finally the number of remaining possibilities is $M-T+1$. The total is this time $$M(M-1)(M-2)...(M-T+1).$$

The relationship between the results is not unique. For example if we have $5$ boxes and $3$ choices then $$5^2<5.4.3.$$ However, if we have $5$ boxes and $4$ choices then $$5^3>5.4.3.2.$$ If the number of boxes, $M$, is growing, and $T$ remains, say, $2$ then $$\lim_{M\rightarrow\infty}\frac{M}{M(M-1)}=0.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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