Binomial expansions and factorials

Question

How to calculate $$\frac{n!}{n_1! n_2! n_3!}$$ where $n= n_1+n_2+n_3$ for higher numbers $n_1,n_2,n_3 \ge 100$? This problem raised while calculating the possible number of permutations to a given string?

Answer 1

These are called multinomial coefficients. There are a few identities that might help with computations. Here are a few: http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients

Answer 2

$$\frac{(n_1+n_2+n_3)!}{(n_1)!(n_2)!(n_3)!}=\frac{(n_1+n_2+n_3)!}{(n_1)!(n_2+n_3)!}\frac{(n_2+n_3)!}{(n_2)!(n_3)!}=\binom{n_1+n_2+n_3}{n_1}\cdot\binom{n_2+n_3}{n_2}$$

Answer 3

If your question is on how to avoid too large numbers in the actual computation: First assume that $n_3$ is the largest number and cancel $n_3!$. It remains

$$\frac{n(n-1)(n-2)\dots(n_3+1)}{n_1!n_2!}$$

Then proceed from lowest to largest:

• $p=n_3+1$,
• for $k$ from $2$ to $n_2$ do
  • $p:=(p\cdot(n_3+k))/k$.
• Then $p:=p\cdot(n_2+n_3+1)$ and
• from $k=2$ to $n_1$ do
  • $p:=(p\cdot(n_2+n_3+k))/k$.
• $p$ now contains the result.

The divisions are all exact integer divisions.

Answer 4

If $n$ is large, you will have trouble even representing $$\frac{n!}{n_1! n_2! n_3!}$$ in floating point on a calculator or computer, regardless of the method of computation, because the exponent is simply too large.
An alternative is to compute its logarithm $$\ln \left( \frac{n!}{n_1! n_2! n_3!} \right) = \ln(n!) - \ln(n_1!) - \ln(n_2!) - \ln(n_3!)$$ and use Stirling's approximation of $x!$ to compute the logarithms of the factorials: $$x! \approx x^x e^{-x} \sqrt{2 \pi x}$$ so $$\ln(x!) \approx x \ln(x) - x + \frac{1}{2} \ln(2 \pi x)$$