0
$\begingroup$

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.

Thanks.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
2
  • $\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
    Commented Dec 11, 2011 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
    Commented Dec 11, 2011 at 15:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .