Problème de combinatoire - $5$-digit code avec $3,4,5$ présent

Question

J'ai un problème de combinatoire avec lequel je lutte. Le voici: "Combien de codes à 5 chiffres ont parmi leurs chiffres chacun des$3,4,5$? "

Je comprends la stratégie générale, où nous voyons d'abord comment nous pouvons permuter $3,4,5$ avec les autres emplacements vides ($\frac{5!}{2} = 60$ manières) et ensuite nous multiplions par $10^2$ (les deux autres emplacements peuvent avoir l'un des $10$chiffres). Cependant, maintenant, nous finissons par compter deux fois, car certains de ces deux autres chiffres seront$3,4,5$et entraînera la duplication des combinaisons entre elles. J'ai du mal à trouver une formule pour les exclure.

Answer 1

Il y a quelques stratégies que nous pourrions employer ici.

Méthode 1: Nous considérons les cas en fonction de la fréquence d'apparition de chaque chiffre.

Cas 1 : les chiffres$3$, $4$, $5$ chacun apparaît exactement une fois.

Choisissez l'une des positions pour $3$, l'une des quatre positions restantes pour le $4$, et l'un des trois autres postes pour le $5$. Ensuite, chacun des deux postes restants peut être pourvu avec l'un des$10 - 3 = 7$chiffres. Par conséquent, il y a

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

ces codes.

Cas 2 : Exactement l'un des chiffres$3$, $4$, $5$ apparaît deux fois et chacun des autres apparaît exactement une fois.

Choisissez lequel des chiffres $3$, $4$, $5$apparaît deux fois. Choisissez deux des positions pour ce chiffre. Choisissez l'une des trois positions restantes pour le plus petit des deux chiffres restants de l'ensemble$\{3, 4, 5\}$ et l'une des deux positions restantes pour le chiffre restant de l'ensemble $\{3, 4, 5\}$. Choisissez lequel des sept chiffres restants remplit la position restante. Il y a

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

ces codes.

Cas 3 : Exactement deux des chiffres$3, 4, 5$ apparaît deux fois et l'autre apparaît une fois.

Choisissez lequel des trois chiffres $3, 4, 5$apparaît exactement une fois. Choisissez laquelle des cinq positions remplies par le chiffre. Choisissez deux des quatre positions restantes pour le plus petit des deux chiffres restants de l'ensemble$\{3, 4, 5\}$, puis remplissez les deux positions restantes avec le chiffre restant de l'ensemble $\{3, 4, 5\}$. Il y a

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

ces codes.

Cas 4 : Exactement l'un des trois chiffres$3, 4, 5$apparaît trois fois et chacun des autres apparaît une fois. Choisissez lequel des trois chiffres apparaît trois fois, puis choisissez trois des cinq positions pour ce chiffre. Choisissez l'une des deux positions restantes pour le plus petit des chiffres restants de l'ensemble$\{3, 4, 5\}$, puis remplissez la position finale avec l'autre chiffre. Il y a

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

ces codes.

Total : Puisque ces positions sont mutuellement exclusives et exhaustives, ajoutez les cas ci-dessus.

Méthode 2: Nous utilisons le principe d'inclusion-exclusion.

Il y a $10^5$codes. Nous souhaitons en exclure ceux dans lesquels au moins un des chiffres$3, 4, 5$ est manquant.

Nous choisissons lequel des trois chiffres $3, 4, 5$à exclure, ce qui laisse neuf façons de remplir chacun des cinq postes. Ainsi, nous soustrayons

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

du total.

Cependant, si nous le faisons, nous aurons soustrait chaque cas dans lequel deux des chiffres $3, 4, 5$manquent deux fois, une fois pour chaque manière, nous aurions pu désigner l'un de ces chiffres comme chiffre manquant. Nous ne voulons soustraire ces cas qu'une seule fois, nous devons donc les ajouter au total.

Nous choisissons lequel des trois chiffres $3, 4, 5$à exclure, ce qui nous laisse huit façons de pourvoir chacun des cinq postes. Ainsi, nous ajoutons

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

à notre total cumulé.

Cependant, si nous soustrayons d'abord les cas dans lesquels l'un des chiffres $3, 4, 5$ est exclu, puis ajoutez les cas dans lesquels deux des chiffres $3, 4, 5$ sont exclus, nous n'aurons pas exclu les cas dans lesquels les trois chiffres $3, 4, 5$sont exclus du tout. C'est parce que nous les avons d'abord soustraits trois fois, une fois pour chaque manière, nous aurions pu désigner l'un de ces trois chiffres comme chiffre exclu. Nous avons ensuite ajouté ces cas trois fois, une fois pour chacun des$\binom{3}{2}$nous aurions pu désigner deux de ces trois chiffres comme chiffres exclus. Ainsi, nous devons les faire du total.

Si les trois chiffres $3, 4, 5$sont exclus, alors nous avons sept choix pour chacun des cinq postes. Ainsi, il y a

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

cas dans lesquels tous les chiffres $3, 4, 5$ sont exclus.

Selon le principe d'inclusion-exclusion, il y a

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

codes admissibles.

Comme vous pouvez le vérifier, les deux méthodes donnent la même réponse.