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

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.


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

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

share|cite|improve this answer
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$. – wxu Dec 11 '11 at 15:41
@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. – joriki Dec 11 '11 at 15:43

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.