Funciones generadoras · Definición

Coeficiente multinomial

combinatoria enumerativafunciones generadoras

Antes de empezar necesitas conocer

Surge al desarrollar \((x_1+\cdots+x_m)^n\) y al contar anagramas con letras repetidas. Conviene dominar antes el coeficiente binomial, que es su caso con dos grupos.

Definición

Coeficiente \(\binom{n}{k_1,\dots,k_m}\): número de formas de repartir \(n\) objetos distintos en \(m\) grupos etiquetados de tamaños \(k_1,\dots,k_m\), con \(k_1+\cdots+k_m=n\).

\[\binom{n}{k_1,\dots,k_m}=\frac{n!}{k_1!\,k_2!\cdots k_m!}\]

Con \(m=2\) se reduce a \(\binom{n}{k}\), y se puede descomponer como \(\binom{n}{k_1,\dots,k_m}=\binom{n}{k_1}\binom{n-k_1}{k_2,\dots,k_m}\). El teorema multinomial afirma que \((x_1+\cdots+x_m)^n=\sum \binom{n}{k_1,\dots,k_m}x_1^{k_1}\cdots x_m^{k_m}\), con la suma sobre todas las \(m\)-uplas de enteros no negativos de suma \(n\).

Para la palabra PEPPER, si todas las letras fueran distintas habría \(6!\) ordenaciones. Como la P aparece 3 veces y la E 2, el total es \(\frac{6!}{3!\,2!\,1!}=\frac{720}{12}=60\).

El error típico es olvidar que los grupos son etiquetados o que la suma de los \(k_i\) debe ser exactamente \(n\). Si los grupos no están etiquetados, hay que dividir además entre el factorial del número de grupos de igual tamaño.

Para pensar

¿Qué pasa con el coeficiente si intercambiamos \(k_1\) y \(k_2\) entre sí?

Nada: el coeficiente es simétrico en los \(k_i\), porque el denominador \(k_1!\,k_2!\cdots k_m!\) no cambia al reordenarlos.

Ejercicios 10

  1. Calcula \(\binom{3}{1,1,1}\).
  2. Calcula \(\binom{4}{2,2}\).
  3. Calcula \(\binom{5}{2,3}\).
  4. Calcula \(\binom{6}{2,2,2}\).
  5. ¿Cuántos anagramas distintos tiene la palabra AAB?
  6. Halla el coeficiente de \(x^2yz\) en \((x+y+z)^4\).
  7. Se reparten 7 personas distintas en grupos etiquetados A, B y C, de tamaños 3, 2 y 2. ¿Cuántas formas hay?
  8. ¿Cuántos anagramas distintos tiene la palabra PEPPER?
  9. Se reparten 9 libros distintos en 3 estantes idénticos, con 3 libros por estante. ¿Cuántas distribuciones distintas hay?
  10. Sea \(a\) un objeto fijo. ¿De cuántas formas se reparten 6 objetos distintos, incluido \(a\), en tres cajas etiquetadas de 2 objetos cada una, con \(a\) en la caja 1?

Referencias

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.