Problema de combinatoria - $5$-código de dígitos con $3,4,5$ presente

Question

Tengo un problema de combinatoria con el que estoy luchando. Aquí está: "¿Cuántos códigos de 5 dígitos tiene entre sus dígitos cada uno de$3,4,5$? "

Entiendo la estrategia general, donde primero vemos cómo podemos permutar $3,4,5$ con las otras ranuras vacías ($\frac{5!}{2} = 60$ formas) y luego multiplicamos por $10^2$ (las otras dos ranuras pueden tener cualquiera de las $10$dígitos). Sin embargo, ahora terminamos contando dos veces, ya que algunos de esos otros dos dígitos serán$3,4,5$y resultará en combinaciones duplicadas entre sí. Estoy luchando por encontrar una fórmula para excluirlos.

Answer 1

Hay un par de estrategias que podríamos emplear aquí.

Método 1: Consideramos los casos según la frecuencia con la que aparece cada dígito.

Caso 1 : Los dígitos$3$, $4$, $5$ cada uno aparece exactamente una vez.

Elija una de las posiciones para el $3$, una de las cuatro posiciones restantes para el $4$, y una de las tres posiciones restantes para el $5$. Luego, cada una de las dos posiciones restantes se puede llenar con una de las restantes$10 - 3 = 7$dígitos. Por lo tanto, hay

$$5 \cdot 4 \cdot 3 \cdot 7^2$$

tales códigos.

Caso 2 : Exactamente uno de los dígitos$3$, $4$, $5$ aparece dos veces y cada uno de los demás aparece exactamente una vez.

Elige cuál de los dígitos $3$, $4$, $5$aparece dos veces. Elija dos de las posiciones para ese dígito. Elija una de las tres posiciones restantes para el menor de los dos dígitos restantes del conjunto$\{3, 4, 5\}$ y una de las dos posiciones restantes para el dígito restante del conjunto $\{3, 4, 5\}$. Elija cuál de los siete dígitos restantes ocupa la posición restante. Existen

$$\binom{3}{1}\binom{5}{2}\cdot 3 \cdot 2 \cdot 7$$

tales códigos.

Caso 3 : Exactamente dos de los dígitos$3, 4, 5$ aparecen dos veces y el otro aparece una vez.

Elija cuál de los tres dígitos $3, 4, 5$aparece exactamente una vez. Elija cuál de las cinco posiciones ocupa ese dígito. Elija dos de las cuatro posiciones restantes para el menor de los dos dígitos restantes del conjunto$\{3, 4, 5\}$, luego llene las dos posiciones restantes con el dígito restante del conjunto $\{3, 4, 5\}$. Existen

$$\binom{3}{1}\binom{5}{1}\binom{4}{2}$$

tales códigos.

Caso 4 : Exactamente uno de los tres dígitos$3, 4, 5$aparece tres veces y cada uno de los demás aparece una vez. Elija cuál de los tres dígitos aparece tres veces, luego elija tres de las cinco posiciones para ese dígito. Elija una de las dos posiciones restantes para el menor de los dígitos restantes del conjunto$\{3, 4, 5\}$, luego llene la posición final con el otro dígito. Existen

$$\binom{3}{1}\binom{5}{3}\binom{2}{1}$$

tales códigos.

Total : Dado que estas posiciones son mutuamente excluyentes y exhaustivas, agregue los casos anteriores.

Método 2: utilizamos el principio de inclusión-exclusión.

Existen $10^5$códigos. Deseamos excluir de estos aquellos en los que al menos uno de los dígitos$3, 4, 5$ Está perdido.

Elegimos cuál de los tres dígitos $3, 4, 5$para excluir, lo que deja nueve formas de cubrir cada uno de los cinco puestos. Por lo tanto, restamos

$$\binom{3}{1}9^5$$

del total.

Sin embargo, si lo hacemos, habremos restado cada caso en el que dos de los dígitos $3, 4, 5$faltan dos veces, una por cada forma, podríamos haber designado uno de esos dígitos como el dígito faltante. Solo queremos restar estos casos una vez, por lo que debemos sumarlos al total.

Elegimos cuáles de los tres dígitos $3, 4, 5$para excluir, lo que nos deja ocho formas de cubrir cada uno de los cinco puestos. Por lo tanto, agregamos

$$\binom{3}{2}8^5$$

a nuestro total acumulado.

Sin embargo, si primero restamos aquellos casos en los que uno de los dígitos $3, 4, 5$ se excluye y luego agregue aquellos casos en los que dos de los dígitos $3, 4, 5$ están excluidos, no habremos excluido aquellos casos en los que los tres dígitos $3, 4, 5$están excluidos en absoluto. Esto se debe a que primero los restamos tres veces, una por cada forma en que podríamos haber designado uno de esos tres dígitos como el dígito excluido. Luego agregamos estos casos tres veces, una para cada uno de los$\binom{3}{2}$formas en las que podríamos haber designado dos de esos tres dígitos como dígitos excluidos. Por lo tanto, los debemos del total.

Si los tres dígitos $3, 4, 5$están excluidos, entonces tenemos siete opciones para cada una de las cinco posiciones. Por lo tanto, hay

$$\binom{3}{3}7^5$$

casos en los que todos los dígitos $3, 4, 5$ están excluidos.

Según el principio de inclusión-exclusión, hay

$$10^5 - \binom{3}{1}9^5 + \binom{3}{2}8^5 - \binom{3}{3}7^5$$

códigos admisibles.

Como puede verificar, los dos métodos dan la misma respuesta.