Un enfoque más sencillo para resolver "¿cuántas k-permutaciones de aaabbccdef hay?"

Question

Dado un problema como el siguiente.

¿Cuántas permutaciones de "aaabbccdef" hay?

Intento

Dividir el problema en casos disjuntos:

• 4-permutación de $\{a,b,c,d,e,f\}$
• permutación de $\{2*x, y, z\}$
• permutación de $\{2*x, 2*y\}$
• permutación de $\{3*a, x\}$

El número de permutaciones para

• caso 1: $P^6_4=360$
• caso 2: $C^3_1\times C^5_2\times\frac{4!}{2!}=360$
• caso 3: $C^3_2\times \frac{4!}{2!\times 2!}=18$
• caso 4: $C^5_1\times \frac{4!}{3!}=20$

El número total de permutaciones es $758$ .

Pregunta

¿Existe algún enfoque más sencillo que sea muy útil para hacer palabras más largas?

Answer 1

Una forma de hacerlo es utilizar funciones generadoras exponenciales: tomar $4!$ veces el coeficiente de $x^4$ en $$\left(1 + x + x^2/2!+x^3/3!\right) \left(1+x + x^2/2!\right)^2\left(1+x\right)^3$$ que sale a $379/12 \cdot 24 = 758$ . Obtenemos este producto tomando un factor de $$1 +x + \cdots + x^k/k!$$ para cada letra distinta, donde $k$ es el número de veces que se utiliza la letra; por lo tanto $1+x + x^2/2! + x^3/3!$ para aaa , uno $1 + x + x^2/2!$ para cada uno de bb y cc y un $1+x$ para cada uno de $d,e,f$ . Véase mi respuesta a este pregunta por los detalles, pero puedo explicar más si no está claro. Esencialmente, esto es sólo otra forma de escribir que sumamos la fórmula multinomial para cada elección de conjunto múltiple de tamaño $4$ .