How do I compute multinomials efficiently?

I'm trying to reproduce Excel's MULTINOMIAL function in C# so

$${MULTINOMIAL(a,b,..,n)} = \frac{(a+b +\cdots +n)!}{a!b! \cdots n!}$$

How can I do this without causing an overflow due to the factorials?

Another, more efficient way of computing the coefficients exactly that generally shouldn't overflow unless the result does is by using the characterization of the multinomial coefficient as a product of binomial coefficients: $${a+b+c+\cdots+n\choose a\;b\;c\cdots\;n} = {a+b\choose b}{a+b+c\choose c}\cdots{a+b+c+\cdots +n\choose n}$$ This is easy to prove by multiplying out the right hand side and noting that factors of $(a+b)!,\;(a+b+c)!,\;\ldots$ cancel out. This simplifies the problem of computing a multinomial coefficient to just computing a binary one - and there are several straightforward ways of doing that without overflow. The easiest may be use the recursive formula ${n+1\choose k+1} = \frac{n+1}{k+1}{n\choose k}$ along with some careful manipulation of the (exact) results to make sure you're always dividing out GCDs; for more information on this approach, see http://blog.plover.com/math/choose.html . Alternately, you can use Kummer's theorem that the power of a prime $p$ dividing ${a+b\choose b}$ is the number of carries when $a$ and $b$ are written as base-$p$ numbers and added. By doing this for a suitable range of primes, you can find the prime factorization of the result and thus the result itself (indeed, you could just accumulate the result by finding the dividing exponent for all the primes less than the top of your binomial coefficient in turn).

If your computer can handle \logarithms and exponentials of numbers, you could calculate the following: $$\log(\frac{(a+b +\cdots +n)!}{a!b! \cdots n!})=\log(a+b +\cdots +n)!)-\log(a!b! \cdots n!)=$$ $$\log(2)+\log(3)+\dots+\log(a+b +\cdots +n)-\log(a!)-\log(b!)-\ldots -\log(x!)=$$ $$\log(2)+\log(3)+\dots+\log(a+b +\cdots +n)-\log(2)-\ldots-\log(a)-\log(2)\ldots-\log(b)\ldots \log(2)-\ldots \log(x)$$

When you do all of these additions, you exponentiate the result using whatever base you started with (as written the base is ten, but you could choose another base).

As a historical note, this is essentially what people did before computers. They used $\log$ tables. I am not a computer programer, so I do not really know how feasible this is in practice or if their are better methods. You can also multiply huge numbers more quickly with a fast fourier transform, but that might be overkill.