Problema de combinação - $5$código de dígitos com $3,4,5$ presente

Question

Eu tenho um problema de combinatória com o qual estou lutando. Aqui está: "Quantos códigos de 5 dígitos têm entre seus dígitos cada um$3,4,5$? "

Eu entendo a estratégia geral, onde primeiro vemos como podemos permutar $3,4,5$ com os outros slots vazios ($\frac{5!}{2} = 60$ maneiras) e então multiplicamos por $10^2$ (os outros dois slots podem ter qualquer um dos $10$dígitos). No entanto, agora acabamos contando em dobro, pois alguns desses outros dois dígitos serão$3,4,5$e resultará na duplicação de combinações entre si. Estou lutando para encontrar uma fórmula para excluí-los.

Answer 1

Existem algumas estratégias que podemos empregar aqui.

Método 1: consideramos os casos, dependendo da frequência com que cada dígito aparece.

Caso 1 : os dígitos$3$, $4$, $5$ cada um aparece exatamente uma vez.

Escolha uma das posições para o $3$, uma das quatro posições restantes para o $4$, e uma das três posições restantes para o $5$. Em seguida, cada uma das duas posições restantes pode ser preenchida com uma das demais$10 - 3 = 7$dígitos. Portanto, existem

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

tais códigos.

Caso 2 : exatamente um dos dígitos$3$, $4$, $5$ aparece duas vezes e cada um dos outros aparece exatamente uma vez.

Escolha qual dos dígitos $3$, $4$, $5$aparece duas vezes. Escolha duas das posições para esse dígito. Escolha uma das três posições restantes para o menor dos dois dígitos restantes do conjunto$\{3, 4, 5\}$ e uma das duas posições restantes para o dígito restante do conjunto $\{3, 4, 5\}$. Escolha qual dos sete dígitos restantes preenche a posição restante. tem

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

tais códigos.

Caso 3 : exatamente dois dos dígitos$3, 4, 5$ aparecem duas vezes e o outro aparece uma vez.

Escolha qual dos três dígitos $3, 4, 5$aparece exatamente uma vez. Escolha qual das cinco posições esse dígito preenche. Escolha duas das quatro posições restantes para o menor dos dois dígitos restantes do conjunto$\{3, 4, 5\}$, em seguida, preencha as duas posições restantes com o dígito restante do conjunto $\{3, 4, 5\}$. tem

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

tais códigos.

Caso 4 : exatamente um dos três dígitos$3, 4, 5$aparece três vezes e cada um dos outros aparece uma vez. Escolha qual dos três dígitos aparece três vezes e, em seguida, escolha três das cinco posições para esse dígito. Escolha uma das duas posições restantes para o menor dos dígitos restantes do conjunto$\{3, 4, 5\}$e preencha a posição final com o outro dígito. tem

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

tais códigos.

Total : como essas posições são mutuamente exclusivas e exaustivas, adicione os casos acima.

Método 2: Usamos o Princípio de Inclusão-Exclusão.

tem $10^5$códigos. Queremos excluir daqueles em que pelo menos um dos dígitos$3, 4, 5$ está desaparecido.

Nós escolhemos qual dos três dígitos $3, 4, 5$para excluir, o que deixa nove maneiras de preencher cada uma das cinco posições. Assim, subtraímos

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

do total.

No entanto, se o fizermos, teremos subtraído cada caso em que dois dos dígitos $3, 4, 5$estão faltando duas vezes, uma para cada forma, poderíamos ter designado um desses dígitos como o dígito ausente. Queremos subtrair esses casos apenas uma vez, portanto, devemos adicioná-los ao total.

Nós escolhemos quais dois dos três dígitos $3, 4, 5$para excluir, o que nos deixa oito maneiras de preencher cada uma das cinco posições. Assim, adicionamos

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

ao nosso total em execução.

No entanto, se primeiro subtrairmos os casos em que um dos dígitos $3, 4, 5$ é excluído e, em seguida, adicione os casos em que dois dos dígitos $3, 4, 5$ são excluídos, não teremos excluído os casos em que todos os três dígitos $3, 4, 5$são excluídos de todo. Isso ocorre porque primeiro os subtraímos três vezes, uma vez para cada forma poderíamos ter designado um desses três dígitos como o dígito excluído. Em seguida, adicionamos esses casos três vezes, uma para cada um dos$\binom{3}{2}$maneiras que poderíamos ter designado dois desses três dígitos como os dígitos excluídos. Assim, devemos eles do total.

Se todos os três dígitos $3, 4, 5$são excluídos, então temos sete opções para cada uma das cinco posições. Assim, existem

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

casos em que todos os dígitos $3, 4, 5$ estão excluídos.

Pelo Princípio de Inclusão-Exclusão, existem

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

códigos admissíveis.

Como você pode verificar, os dois métodos produzem a mesma resposta.