Here is the question: Let $k,m,n$ be positive integers and $k\leq m\leq n$.

Compute $$\sum_{\substack{a_1+\dots+a_n=m,\\ 0\leq a_i<k, \text{for } i=1,2,\ldots,n}}\frac{m!}{a_1!a_2!\cdots a_n!}$$

The original question is to count the probability of the following event. Choose $m$ numbers $\{y_{i_1}, \ldots y_{i_m}\}$ from $n$ distinct numbers $\{y_1,\ldots,y_n\}$, we are allowed $y_{i_k}=y_{i_j}$.

What is the probability of the choice which has at least $k$ same numbers ?

If I am right, I think it only needs to compute the sum given above.



The probability is undefined because you haven't specified a distribution. However, from your first formulation of the problem, it seems that you have in mind that each of the $m$ numbers is chosen independently with uniform distribution over the $n$ distinct numbers.

In that case, this is a somewhat unusual statement of the generalized birthday "paradox": There are $n$ days of the year and $m$ people in a room; what's the probability that $k$ of them have the same birthday?

Apparently no closed form is known for this. Here are some related questions:

Extending the birthday paradox to more than 2 people

Birthday paradox with M shared birthdays (closed but has a relevant link in a comment)

Probability of 3 people in a room of 30 having the same birthday

Birthday Probability

  • $\begingroup$ Thank you very much! But I do not understand why it is undefined. Take an example, let $n=3, m=2 ,k=2$, then the propability is $3/3^2=1/3$. $\endgroup$ – wxu Dec 11 '11 at 15:41
  • $\begingroup$ @wxu: As I said, that's the probability if you assume that each of the $m$ numbers is chosen independently with uniform distribution over the $n$ distinct numbers. You didn't specify that, I merely inferred it from your solution attempt. Usually I just point this out to make people aware that they're assuming uniform distribution without specifying it, but in this case it's actually relevant, since even assuming that some form of uniform distribution is intended one could take the distribution to be uniform over all possible resulting counts, without distinguishing between the $m$ numbers. $\endgroup$ – joriki Dec 11 '11 at 15:43

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.