Skip to main content
1 of 3
R B
  • 9.5k
  • 5
  • 35
  • 78

(More of an extended comment - it's not readable as a comment).

Are you sure a closed form for it exist?

This is solvable by the following recurrence formula: $$P[m,k]=P[m-1,k-1]*P_k + P[m-1,k]*(1-P_{k+1})$$ Where $$P_k = \frac{(N+1)^{k-2} (N + k )}{N^k}$$ and $$ P[0,0]=1, \forall k\neq 0: P[0,k]=0$$

The answer you're looking for (the probability of $t$ marked elements) is $P[s,t]$.

R B
  • 9.5k
  • 5
  • 35
  • 78