Calculating some probability of buying different cards

Question

This problem was recently featured in an ICPC contest. The problem stated, without taking the story into account and as well as I recall:

Peter likes a fad card game. This game has various cards, and all of them are equally likely to be bought, always individually, in an envelope. Like the Pokemon TCG, but always single cards. Also, this set has the interesting distribution of printing every card in the game with equal probability.

Peter is a very fervent player and has saved up some money to buy some cards for his deck. He is well-informed and knows exactly how many cards are currently in circulation: $N$. He has saved up enough money to buy $m$ cards and (somehow) expects to acquire $k$ different cards. We want to tell him what's the probability that he will buy exactly $k$ different cards in his purchase of $m$ cards from the currently $N$ in circulation.

I thought of this as looking for:

$$ P(X=\mu_X) $$

where $X$ is distributed as:

$$ X \sim \text{Bi}(m,\textstyle{\frac{1}{N}}) $$

So we need to calculate

$$ P(X=\mu_X)= \binom{m}{k} \left( \frac{1}{N} \right)^k \left( \frac{N-1}{N} \right)^{m-k} $$

Which goes to

$$ P(X=\mu_X)=\frac{m!}{k!(m-k)!} \frac{\left( N-1 \right)^{m-k}}{N^m} $$

Trying $N=10,m=1,k=1$:

$$ \frac{1!}{1!(1-1)!} \frac{\left( 10-1 \right)^{1-1}}{10^1}=1/10 $$

But if we try $N=120,m=43,k=15$:

$$ \frac{43!}{15!(43-15)!} \frac{\left( 120-1 \right)^{43-15}}{120^{43}}=\frac{247019460815784070763444954675120550840385420833704211278967364992167}{31747065868132267332587519988324920434265948160000000000000000000000000000000000000000000} $$

Which is computationally hell. Doing the operations to get to that point is difficult as for getting the number in the form $\textstyle{\frac{p}{q}}$. Do you see a way around doing the calculation and then simplifying?

Answer 1

The probability is going to be:

$\frac{\binom{N}{k}{m\brace k}k!}{N^k}$.

Where $\binom{N}{k}$ is a binomial coefficient, $n\brace k $ is a stirling coefficient of the second kind and $k!$ is a factorial.

You can compute each of these using their own recursions in a $100\times 100$ matrix and a $100$ array for the factorial.

I recommend java BigIntegers.

So you have to simplify the fraction $\frac{\binom{N}{k}{m\brace k}k!}{N^k}$. To do this you should run the following for cycle, let $X$ be the numerator and $Y$ be the denominator.

for(counter=0;counter<k;counter++){
Y/=gcd(X,N);
X/=gcd(X,N);
}

after doing that you are going to have $X$ and $Y$ relatively prime and ready to print. Calculating the greatest common divisor with N is easy since N is small, you can use the euclidean algorithm.