Uso de funciones de generación exponencial en problemas de conteo

Question

Es posible el uso exponencial de la generación de funciones para resolver problemas en los que la repetición es querido?

Por ejemplo, si quería resolver el siguiente problema que se quiere distintas posibilidades...

Cuántos diferentes 5-letra de las palabras se pueden formar con las letras de la palabra ABRACADABRA si se duplican las letras, pero se les permite ninguna carta puede ser utilizado más veces de lo que ocurre en la palabra ABRACADABRA ?

5 diferentes letras, Un repitió cinco veces, dos veces B, C, D una vez, R dos veces.

Entonces, la función sería $$ F(x) = (1 + \frac {x}{1!} + \frac {x^2}{2!} + \frac {x^3}{3!} + \frac {x^4}{4!} + \frac {x^5}{5!}) (1 + \frac {x}{1!} + \frac {x^2}{2!})^2 (1 + \frac {x}{1!})^2 $$ $$ F(x) = \frac {x^{11}}{120} + \frac {3 x^{10}}{40} + \frac {2 x^9}{5} + \frac {19 x^8}{12}+ \frac{289 x^7}{60}+\frac{331 x^6}{30}+\frac{2221 x^5}{120}+\frac {545 x^4}{24} + \frac{121 x^3}{6}+\frac{25 x^2}{2}+5 x+1 $$

Por lo tanto, la respuesta sería la $5!(\frac {1271}{120})$

Sin embargo, ¿cómo iba a ser capaz de aplicar para el siguiente problema?

Cuántos de 5 cartas de las manos (de ordinario cubierta) tener al menos una carta de cada palo?

4 palos, que se repite 13 veces

$ 52*51*50*49*48 = 311,875,200 $ total de posibilidades

$$ G(x) = (\frac {x^{13}}{13!} + \frac{x^{12}}{12!}+ \frac{x^{11}}{11!} + \frac{x^{10}}{10!} + \frac{x^9}{9!} + \frac{x^8}{8!} + \frac{x^7}{7!} + \frac{x^6}{6!} + \frac{x^5}{5!} + \frac{x^4}{4!} + \frac{x^3}{3!} + \frac{x^2}{2!} + \frac{x}{1!} + 1)^4 $$

Por supuesto, esto me acaba de dar combinaciones únicas, por lo que no funciona. Hay un método real para resolver el uso de exponenciales funciones de generación? Es posible o recomendable?

Answer 1

"¿Cuántos de 5 cartas de las manos (de ordinario cubierta) tener al menos una carta de cada palo?"

En primer lugar, como una comprobación de validez, un no-GF solución. Debe haber dos cartas del mismo palo y cada uno de los restantes tres palos. Hay 4 maneras de escoger el traje especial, $\binom{13}{2}$ formas de elegir a sus dos cartas, y 13 de las formas para elegir la tarjeta de cada uno de los restantes tres palos. Por lo que el número de manos es $$4 \cdot \binom{13}{2} \cdot 13^3 = 685,464$$

Ahora vamos a probar una solución con el uso de una potestad ordinaria de la serie de generación de función. Cada traje puede contribuir de 1 a 13 cartas, y $n$ tarjetas pueden ser seleccionados a partir de una demanda en $\binom{13}{n}$ formas, por lo que el OPSGF es $$f(x) = \left[ \binom{13}{1}x + \binom{13}{2} x^2 + \binom{13}{3}x^3 + \dots + \binom{13}{13} x^{13} \right]^4$$ El coeficiente de $x^n$ es el número de n-tarjeta de las manos. Si todo lo que nos interesa es el coeficiente de $x^5$, podemos escribir $$f(x) = x^4 \left[ \binom{13}{1} + \binom{13}{2} x + O(x^2) \right]^4 = x^4 \left[ \binom{13}{1}^4 + \binom{4}{1} \binom{13}{1}^3 \binom{13}{2} x +O(x^2) \right]$$ por lo que el coeficiente de $x^5$$\binom{4}{1} \binom{13}{1}^3 \binom{13}{2}$, de acuerdo con la respuesta anterior.

Ahora la pregunta original: el correspondiente exponencial de la generación de la función es $$g(x) = \left[ \binom{13}{1}x + \frac{1}{2!} 2! \binom{13}{2} x^2 + \frac{1}{3!} 3! \binom{13}{3}x^3 + \dots + \frac{1}{13!} 13! \binom{13}{13} x^{13} \right]^4$$ which is the same as our OPSGF, because now we are considering the order of the cards in the hand to be significant, and $n$ cards can be selected from 13 in $n! \binom{13}{n}$ maneras el fin de tomar en cuenta. El número de n-tarjeta de las manos, teniendo en cuenta el orden de las cartas para ser significativo, es el coeficiente de $\frac{1}{n!} x^n$. Si expande g(x) en la misma manera como lo hicimos para el OPSGF, el coeficiente de $\frac{1}{5!} x^5$$5! \binom{4}{1} \binom{13}{1}^3 \binom{13}{2}$. Pero entonces, si usted no desea considerar el orden de las cartas para ser significativo, tenemos más de contado, y debemos dividir por 5! para compensar, nos conducen de vuelta a nuestra respuesta original. La conclusión es que realmente no hay mucha diferencia entre los dos enfoques, el uso de un OPSGF o una EGF.

Answer 2

La generación de la función para el segundo problema le proporcionará toda posible de 5 cartas de las manos. Pero estamos interesados en el caso cuando tenemos al menos un cable de cada palo. Así que tenemos que hacer algunas restricciones. Ya sabemos que el traje de las 4 cartas (porque la condición de los estados son diferentes) y hay 4 opciones para la quinta tarjeta, por lo que hay 4 combinaciones diferentes si las cartas fueron undistiguishable. Pero debido a que no son, necesitamos multilply ese número por la multinomial:

$$\binom{5}{2,1,1,1} = \frac{5!}{2!\cdot 1! \cdot 1! \cdot 1!} = 60$$

Por lo que el número total de combinaciones es:

$$60 \cdot 4 = 240 \text{ combinations}$$

Este es en realidad el número de combinaciones posibles con un par de cartas del mismo palo. Podemos obtener el mismo resultado mediante la exponencial de generación de función. En realidad, la exponencial de generación de función se basa en el mismo principio. Usted puede leer más acerca de esto aquí, especialmente en el $7^{th}$ página.

Pero antes de aplicar la exponencial de generación de función, tenemos que limitar el número de cartas del mismo palo. A partir de la condición de que podemos conseguir que el máximo número de cartas de cada palo es de 2 y el mínimo número de cartas de cada palo es 1. Así que el GF será:

$$G(x) = \left(x + \frac {x^2}{2!}\right)^4 = x^4+2 x^5+\frac{3 x^6}{2}+\frac{x^7}{2}+\frac{x^8}{16}$$

El coeficiente de ante a $x^5$ es de 2. Por lo que el número total de combinaciones es:

$$2 \cdot 5! = 2 \cdot 120 = 240 \text{ combinations}$$

Y podemos ver que hemos obtenido los mismos resultados utilizando ambos métodos. Esto es debido a que el exponetnial de generación de función es una de las más elegantes, oculto y más simple versión de la multinomial método.