- There are P people playing a game.
- They choose a number between 1 and K randomly.
(Each number has the same probability of being chosen, 1/K)
Given a number N, what is the probability that nobody chose it and at least two people chose every number below it?
I worked out manually the probabilities up to 4, but I can't go further, because of all the probabilities counted twice and I get confused.
For example, for N=1 we just need that nobody chooses 1 and that's it, since there are no numbers below it. The probability of it happening is $$\frac{(K-1)^P}{K^P}$$
For N=2 we need that nobody chooses 2 and at least two people choose 1, so I subtracted the cases where nobody chose 1 or 2 and 1 peoson chose 1 and nobody chose 2, so I got: $$\frac{(K-1)^P-(K-2)^P-P(K-2)^{P-1}}{K^P}$$
For N=3 I got this:
$$\frac{(K-1)^P-2(K-2)^P+(K-3)^P-2P(K-2)^{P-1}+2P(K-3)^{P-1}+P(P-1)(K-3)^{P-2}}{K^P}$$
- For N=4 I got this:
$$\frac{(K-1)^P-3P(K-2)^{P-1}+3P(P-1)(K-3)^{P-2}-P(P-1)(P-2)(K-4)^{P-3}-3(K-2)^P+3(K-3)^P-(K-4)^P+6P(K-3)^{P-1}-3P(K-4)^{P-1}-3P(P-1)(K-4)^{P-2}}{K^P}$$
I think it is correct, but it was done by hand and took forever.
Is there an easy way to calculate this for any given N?
Also, the probability should be zero if the players are not enough, i.e. if P<2(N-1).
Thank you in advance!