Calcolo combinatorio
Ti serve sapere quante cinquine diverse di carte puoi scegliere da un mazzo di 32 carte? È esattamente il tipo di problema che risolve il calcolo combinatorio. Esistono due regole combinatorie fondamentali: il principio della somma e il principio del prodotto. Tutti gli altri metodi sono soltanto un’estensione di questi principi di base.
Principio della somma
Il principio della somma è molto semplice: ci dice che, se abbiamo due insiemi A, B senza alcun elemento in comune, il numero di tutti i modi possibili di scegliere un elemento dall’unione A ∪ B è uguale a |A| + |B|, cioè alla somma del numero di elementi dei due insiemi.
Cominciamo con un esempio facile. Abbiamo 6 palline rosse e 8 palline blu. Mettiamo tutte le palline in un’unica urna. Quante possibilità abbiamo in tutto se estraiamo una pallina? All’inizio avevamo l’insieme delle palline rosse, che chiamiamo A, e poi l’insieme delle palline blu, che chiamiamo B. Questi insiemi sono disgiunti, cioè non hanno nessuna pallina in comune. Vogliamo estrarre una sola pallina, quindi abbiamo in tutto |A| + |B| = 6 + 8 = 14 possibilità. Ecco tutto.
Principio del prodotto
Abbiamo di nuovo due insiemi, D e U. L’insieme D contiene tre donne e l’insieme U quattro uomini. Ora ci chiediamo quante coppie diverse uomo—donna possiamo formare con questi insiemi. Che cosa cerchiamo di fare? Prendiamo sempre una donna e le abbiniamo un uomo. Il numero di tutte le coppie lo calcoliamo così: prendiamo una donna, Giulia, e le abbiniamo uno dopo l’altro tutti gli uomini. Otteniamo così 4 coppie diverse, perché a lei possiamo abbinare 4 uomini diversi. Facciamo lo stesso con le altre due donne, che formano anch’esse altre 4 coppie ciascuna. Ed è tutto: abbiamo in tutto 4 + 4 + 4 = 12 coppie.
Che cosa abbiamo fatto in realtà? Abbiamo moltiplicato tra loro i numeri di elementi dei due insiemi. Avevamo 3 donne e 4 uomini, quindi il numero totale di coppie è 3 · 4 = 12. Da qui il nome principio del prodotto. Se dunque abbiamo due insiemi con cui formiamo delle coppie, basta moltiplicare il numero di elementi del primo insieme per il numero di elementi del secondo.
Qui sotto puoi verificare che è proprio così. Ecco tutte le coppie che possiamo formare con 3 donne e 4 uomini. Ogni riga rappresenta le possibilità per una delle donne e ogni colonna le possibilità per uno degli uomini. Abbiamo così tre righe e quattro colonne, cioè in tutto righe · colonne possibilità.
Esercizi svolti
- Quanti numeri diversi di due cifre esistono? Che aspetto ha un numero di due cifre? Al primo posto compare una delle cifre 1, …, 9, mentre al secondo posto può comparire anche lo zero: 0, …, 9. Nel primo insieme abbiamo quindi 9 cifre, nel secondo 10. Applichiamo il principio del prodotto e otteniamo il risultato finale: 9 · 10 = 90.
- Quanti numeri diversi di tre cifre esistono, in cui nessuna cifra può comparire due volte? Al primo posto possono esserci di nuovo nove cifre, perché il numero non può iniziare con lo zero. Al secondo posto possono esserci tutte le cifre, zero compreso, ma non la cifra che compare in prima posizione, quindi dalle dieci cifre possibili sottraiamo uno (per esempio, se il nostro numero di tre cifre inizia proprio con un quattro, è chiaro che in seconda posizione non può più esserci un quattro, perché nel numero comparirebbe due volte). Al terzo posto possono esserci di nuovo tutte le cifre, ma non quelle che stanno al primo o al secondo posto. Il motivo è lo stesso. Se al primo posto c’è la cifra 4 e al secondo la cifra 7, al terzo posto possiamo mettere una cifra dell’insieme {0, …, 9} ∖ {4, 7}. Dal totale di dieci cifre dobbiamo sottrarre due. Ora non resta che moltiplicare 9 · 9 · 8 = 648. In tutto esistono dunque 648 numeri di questo tipo.
- Lanciamo un normale dado due volte di seguito. Quanti risultati diversi possiamo ottenere? Al primo lancio possono uscire 6 risultati diversi. Al secondo lancio anche, quindi il numero totale di possibilità è 6 · 6 = 36.
- Lanciamo un dado due volte di seguito. Quanti risultati diversi possiamo ottenere, se al primo lancio è uscito un numero pari? Al primo lancio è uscito un numero pari, cioè uno dei numeri 2, 4, 6, che sono in tutto 3 possibilità. Al secondo lancio può uscire qualsiasi numero, quindi in tutto abbiamo 3 · 6 = 18 possibilità.
Capitoli: Calcolo combinatorio, Disposizioni, Permutazioni, Combinazioni, Disposizioni con ripetizione, Combinazioni con ripetizione, Quanti PIN diversi esistono?
