Problema combinatorio - $5$-digit codice con $3,4,5$ presente

Question

Ho un problema di calcolo combinatorio con cui sto lottando. Eccolo: "Quanti codici a 5 cifre hanno tra le loro cifre ciascuno di$3,4,5$? "

Capisco la strategia generale, in cui vediamo prima come possiamo permutare $3,4,5$ con gli altri slot vuoti ($\frac{5!}{2} = 60$ modi) e poi moltiplichiamo per $10^2$ (entrambi gli altri due slot possono avere uno qualsiasi dei file $10$cifre). Tuttavia ora finiamo per fare il doppio conteggio, come lo saranno alcune di quelle altre due cifre$3,4,5$e comporterà la duplicazione di combinazioni tra loro. Sto lottando per trovare una formula per escluderli.

Answer 1

Ci sono un paio di strategie che potremmo utilizzare qui.

Metodo 1: consideriamo i casi in base alla frequenza di visualizzazione di ciascuna cifra.

Caso 1 : le cifre$3$, $4$, $5$ ognuno appare esattamente una volta.

Scegli una delle posizioni per il $3$, una delle quattro posizioni rimanenti per $4$e una delle tre posizioni rimanenti per $5$. Quindi ciascuna delle due posizioni rimanenti può essere riempita con una delle rimanenti$10 - 3 = 7$cifre. Quindi, ci sono

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

tali codici.

Caso 2 : esattamente una delle cifre$3$, $4$, $5$ appare due volte e ciascuno degli altri appare esattamente una volta.

Scegli quale delle cifre $3$, $4$, $5$appare due volte. Scegli due delle posizioni per quella cifra. Scegli una delle tre posizioni rimanenti per la più piccola delle due cifre rimanenti dal set$\{3, 4, 5\}$ e una delle due posizioni rimanenti per la cifra rimanente dal set $\{3, 4, 5\}$. Scegli quale delle sette cifre rimanenti riempie la posizione rimanente. Ci sono

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

tali codici.

Caso 3 : esattamente due delle cifre$3, 4, 5$ appare due volte e l'altro appare una volta.

Scegli quale delle tre cifre $3, 4, 5$appare esattamente una volta. Scegli quale delle cinque posizioni viene riempita da quella cifra. Scegli due delle restanti quattro posizioni rimanenti per la più piccola delle due cifre rimanenti dal set$\{3, 4, 5\}$, quindi riempire le restanti due posizioni con la cifra rimanente dal set $\{3, 4, 5\}$. Ci sono

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

tali codici.

Caso 4 : esattamente una delle tre cifre$3, 4, 5$appare tre volte e ciascuno degli altri appare una volta. Scegli quale delle tre cifre appare tre volte, quindi scegli tre delle cinque posizioni per quella cifra. Scegli una delle due posizioni rimanenti per la più piccola delle cifre rimanenti dal set$\{3, 4, 5\}$, quindi riempire la posizione finale con l'altra cifra. Ci sono

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

tali codici.

Totale : poiché queste posizioni si escludono a vicenda ed esaustive, aggiungere i casi precedenti.

Metodo 2: utilizziamo il principio di inclusione-esclusione.

Ci sono $10^5$codici. Vogliamo escludere da questi quelli in cui almeno una delle cifre$3, 4, 5$ manca.

Scegliamo quale delle tre cifre $3, 4, 5$escludere, che lascia nove modi per riempire ciascuna delle cinque posizioni. Quindi, sottraiamo

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

dal totale.

Tuttavia, se lo facciamo, avremo sottratto ogni caso in cui due delle cifre $3, 4, 5$mancano due volte, una per ogni modo avremmo potuto designare una di quelle cifre come cifra mancante. Vogliamo solo sottrarre tali casi una volta, quindi dobbiamo aggiungerli al totale.

Scegliamo quali due delle tre cifre $3, 4, 5$escludere, il che ci lascia otto modi per riempire ciascuna delle cinque posizioni. Quindi, aggiungiamo

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

al nostro totale parziale.

Tuttavia, se prima sottraiamo quei casi in cui una delle cifre $3, 4, 5$ è escluso e quindi aggiungi quei casi in cui due delle cifre $3, 4, 5$ sono esclusi, non avremo esclusi quei casi in cui tutte e tre le cifre $3, 4, 5$sono esclusi del tutto. Questo perché le abbiamo prima sottratte tre volte, una per ogni modo avremmo potuto designare una di quelle tre cifre come cifra esclusa. Abbiamo quindi aggiunto questi casi tre volte, una per ciascuno dei$\binom{3}{2}$modi in cui avremmo potuto designare due di queste tre cifre come cifre escluse. Quindi, dobbiamo loro dal totale.

Se tutte e tre le cifre $3, 4, 5$sono escluse, quindi abbiamo sette scelte per ciascuna delle cinque posizioni. Quindi, ci sono

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

casi in cui tutte le cifre $3, 4, 5$ sono esclusi.

Secondo il principio di inclusione-esclusione, ci sono

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

codici ammissibili.

Come puoi verificare, i due metodi danno la stessa risposta.