Expansiones binomiales y factoriales

Question

Cómo calcular $$\frac{n!}{n_1! n_2! n_3!}$$ donde $n= n_1+n_2+n_3$ para números más altos $n_1,n_2,n_3 \ge 100$ ? Este problema se planteó al calcular el número posible de permutaciones de una cadena dada?

Answer 1

Si tu pregunta es sobre cómo evitar números demasiado grandes en el cálculo real: Primero supongamos que $n_3$ es el número mayor y cancelar $n_3!$ . Queda

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

A continuación, proceda de menor a mayor:

• $p=n_3+1$ ,
• para $k$ de $2$ a $n_2$ do
  • $p:=(p\cdot(n_3+k))/k$ .
• Entonces $p:=p\cdot(n_2+n_3+1)$ y
• de $k=2$ a $n_1$ do
  • $p:=(p\cdot(n_2+n_3+k))/k$ .
• $p$ contiene ahora el resultado.

Las divisiones son todas divisiones enteras exactas.

Answer 2

Se denominan coeficientes multinomiales. Hay algunas identidades que pueden ayudar en los cálculos. Aquí están algunas: http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients

Answer 3

$$\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 4

Si $n$ es grande, tendrá problemas incluso para representar $$\frac{n!}{n_1! n_2! n_3!}$$ en coma flotante en una calculadora u ordenador, independientemente del método de cálculo, porque el exponente es simplemente demasiado grande.
Una alternativa es calcular su logaritmo $$\ln \left( \frac{n!}{n_1! n_2! n_3!} \right) = \ln(n!) - \ln(n_1!) - \ln(n_2!) - \ln(n_3!)$$ y utilizar la aproximación de Stirling de $x!$ para calcular los logaritmos de los factoriales: $$x! \approx x^x e^{-x} \sqrt{2 \pi x}$$ así que $$\ln(x!) \approx x \ln(x) - x + \frac{1}{2} \ln(2 \pi x)$$