Permutación del multiconjunto

Question

¿Cuántos 8-permutaciones hay de las letras de la palabra 'DIRECCIONES'?

Mi libro de texto sugiere que deberíamos dividir la situación en casos en los que se elimina una letra diferente. En otras palabras, para el conjunto múltiple $\{1 \cdot A, 2 \cdot D, 1 \cdot R, 2 \cdot E, 3 \cdot S\}$ contamos el número de permutaciones del conjunto siguiente:

1. $\{0 \cdot A, 2 \cdot D, 1 \cdot R, 2 \cdot E, 3 \cdot S\}$
2. $\{1 \cdot A, 1 \cdot D, 1 \cdot R, 2 \cdot E, 3 \cdot S\}$
3. $\{1 \cdot A, 2 \cdot D, 0 \cdot R, 2 \cdot E, 3 \cdot S\}$
4. $\{1 \cdot A, 2 \cdot D, 1 \cdot R, 1 \cdot E, 3 \cdot S\}$
5. $\{1 \cdot A, 2 \cdot D, 1 \cdot R, 2 \cdot E, 2 \cdot S\}$

Es fácil demostrar que el número total de 8-permutaciones es $15120$ . No estoy contento con este cálculo de división de casos y quiero tener un cálculo directo del resultado. Accidentalmente, encuentro que $$C_8^9\frac{8!}{2!2!3!}=15120.$$ Además, pruebo esta fórmula, por ejemplo, la 3ª permutación de un multiconjunto con 4 elementos, y realmente funciona. Así que creo que debería haber una buena explicación de por qué la fórmula funciona. ¿Puede alguien explicármelo?

Answer 1

Una solución algebraica

Las permutaciones de las 9 letras tomadas en conjunto = $\dfrac{9!}{1!2!1!2!3!}=\dfrac{9!}{a!b!c!d!e!}$ , digamos que

Dejando 1 letra a la vez, obtenemos $8!\left[\dfrac{1}{(a-1)!b!c!d!e!} + \dfrac{1}{a!(b-1)!c!d!e!} . . . +\dfrac{1}{a!b!c!d!(e-1)!}\right]$

Poniendo bajo un denominador común, obtenemos $8!\left[\dfrac{a+b+c+d+e}{a!b!c!d!e!} \right]$

Pero $a+b+c+d+e = 9$ , así que ...... debería ser capaz de ver el final.

Para simplificar, podemos dejar el factor de multiplicación en 9 en lugar de ${9\choose 8}$

Answer 2

Una solución combinatoria

Imagina $9$ distinto tipos de caramelos etiquetados $1$ a $9$ que se distribuye a $5$ niños, números dados a un niño $(1-1-2-2-3)$ basado en (digamos) la edad, tipo(s) dado(s) a un niño en particular al azar.

Distribuimos los caramelos uno por uno. Cuando hayamos repartido $8$ caramelos, sólo hay una forma de distribuir la última.

Así que, tanto si distribuimos el último como si no, el número total de formas de distribución sigue siendo el mismo, $\dfrac{9!}{1!1!2!2!3!}$

Answer 3

Como has observado (en un comentario sobre otra respuesta), el número de 8-permutaciones de este conjunto es igual al número de 9-permutaciones. Como se indica en otra respuesta, podemos demostrar que esto es cierto observando que cada 9-permutación puede ser mapeada a una 8-permutación por eliminando la última letra; y la inversa de este mapeo existe (basta con añadir la letra que se ha eliminado; sólo hay una forma posible de hacerlo). manera de hacerlo), por lo que es uno a uno y en y los dos conjuntos de combinaciones tienen el mismo tamaño.

Esta es una observación general que se aplica a cualquier palabra de 9 letras.

La razón para no ignorar el método del libro es que el método de "un caso" funciona en general sólo para $(n-1)$ -permutaciones (y por supuesto $n$ -permutaciones) de un $n$ -palabra de letras. Si usted está buscando 7-permutaciones de 'Direcciones' entonces podría tener que considerar los diferentes casos dependiendo de qué las letras que se hayan eliminado. Ciertamente, no habrá una correspondencia unívoca con las 9 permutaciones.

Answer 4

Hay nueve letras en DIRECCIONES, pero tenemos ocho puestos que cubrir. Por lo tanto, debemos omitir una de las letras. Si omitimos la A, podemos llenar dos de las ocho posiciones en $\binom{8}{2}$ maneras. Podemos entonces llenar una de las seis posiciones restantes con una R en $\binom{6}{1}$ formas. Podemos llenar dos de las posiciones restantes con E en $\binom{5}{2}$ formas. Por último, llenamos las tres posiciones restantes con S en $\binom{3}{3}$ formas. Por lo tanto, hay $$\binom{8}{2}\binom{6}{1}\binom{5}{2}\binom{3}{3} = \frac{8!}{2!6!} \cdot \frac{6!}{1!5!} \cdot \frac{5!}{2!3!} \cdot \frac{3!}{0!3!} = \frac{8!}{2!1!2!0!3!} = \frac{8!}{2!2!3!}$$ $8$ permutaciones de las letras de DIRECCIONES en las que se omite la A. Como sólo hay una A y una R en DIRECCIONES, hay el mismo número de $8$ permutaciones en las que se omite una R (intercambiar los papeles de A y R en el argumento anterior).

Con un argumento similar, el número de $8$ permutaciones en las que se omite una D es $$\binom{8}{1}\binom{7}{1}\binom{6}{1}\binom{5}{2}\binom{3}{3} = \frac{8!}{2!3!}$$ Como hay dos D y dos E en las direcciones, hay el mismo número de permutaciones en las que se omite una E.

El número de $8$ permutaciones en las que se omite una S es $$\binom{8}{1}\binom{7}{2}\binom{5}{1}\binom{4}{2}\binom{2}{2} = \frac{8!}{2!2!2!}$$

Sumando los casos anteriores se obtiene \begin {align*} \frac {8!}{2!2!3!} + \frac {8!}{2!2!3!} + \frac {8!}{2!3!} + \frac {8!}{2!3!} + \frac {8!}{2!2!2!} & = \frac {8!}{2!2!3!}(1 + 1 + 2 + 2 + 3) \\ & = 9 \cdot \frac {8!}{2!2!3!} \\ & = \frac {9!}{2!2!3!} \end {align*}