15. Calcolo combinatorio#
Il calcolo combinatorio si pone il problema di determinare il numero dei modi mediante i quali gli elementi di uno stesso insieme o di più insiemi possono essere associati, seguendo regole prestabilite. Alcuni dei problemi del calcolo delle probabilità per essere risolti richiedono l’utilizzo dei metodi del calcolo combinatorio.
In questo capitolo verranno discussi alcuni concetti del calcolo combinatorio. In particolare, verranno introdotti il principio del prodotto, il principio della somma e il modello dell’urna. Verranno inoltre descritte le nozioni di permutazione semplice, disposizione semplice e di combinazione semplice.
import numpy as np
import pandas as pd
import itertools as it
import math
import matplotlib.pyplot as plt
import seaborn as sns
from scipy.constants import golden
%matplotlib inline
sns.set_theme(
context="paper",
style="darkgrid",
palette="colorblind",
rc={'figure.figsize': (5.0, 5.0/golden)},
)
SEED = 123456
rng = np.random.default_rng(SEED)
15.1. Principio del prodotto#
I metodi di base del calcolo combinatorio applicano due principi: la regola del prodotto e la regola della somma. Consideriamo il principio del prodotto.
In generale, una scelta può essere effettuata in più fasi, ad esempio \(k\). Supponiamo che per ogni \(i = 1, \dots, k\) la scelta da compiere al \(i\)-esimo stadio possa essere effettuata in \(n_i\) modi. Secondo il principio del prodotto, il numero totale di possibili scelte è dato dal prodotto dei singoli numeri, ovvero:
Esempio 1. Ho a disposizione 2 paia di scarpe, 3 paia di pantaloni e 5 magliette. In quanti modi diversi mi posso vestire?
Esempio 2. In Minnesota le targhe delle automobili sono costituite da tre lettere (da A a Z) seguite da tre numeri (da 0 a 9). Qual è la proporzione di targhe che iniziano con GZN?
La soluzione è data dal numero di targhe che iniziano con GZN diviso per il numero totale di targhe possibili.
Il numero totale di targe è \(26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 = 17,576,000\). Per calcolare il numero di targhe che iniziano con GZN, consideriamo le targhe che hanno la forma GZN _ _ _. Per i tre simboli mancanti ci sono \(10 \cdot 10 \cdot 10\) possibilità. Dunque la proporzione cercata è
10**3 / (26**3 * 10**3)
5.689576695493855e-05
15.2. Principio della somma#
Il principio della somma afferma che se un insieme può essere suddiviso in due o più sottoinsiemi disgiunti, allora il numero totale di elementi nell’insieme è dato dalla somma dei numeri di elementi in ciascun sottoinsieme.
In altre parole, se si vuole determinare il numero totale di modi in cui è possibile realizzare un certo evento, e questo evento può essere realizzato in modo esclusivo in modo A oppure B, allora il numero totale di modi in cui è possibile realizzare l’evento è dato dalla somma dei modi in cui può essere realizzato in modo A e dei modi in cui può essere realizzato in modo B.
Ad esempio, se si vuole determinare il numero totale di modi in cui è possibile scegliere un dolce da una tavola con due tipi di dolci (ad esempio torta e biscotti), il principio della somma afferma che il numero totale di modi è dato dalla somma del numero di modi in cui è possibile scegliere la torta e del numero di modi in cui è possibile scegliere i biscotti.
Esempio 3. L’urna \(A\) contiene \(5\) palline numerate da \(1\) a \(5\), l’urna \(B\) contiene \(6\) palline numerate da \(6\) a \(11\), l’urna \(C\) contiene \(3\) palline numerate da \(12\) a \(14\) e l’urna \(D\) contiene \(2\) palline numerate \(15\) e \(16\). Quanti insiemi composti da due palline, ciascuna estratta da un’urna differente, si possono formare?
Il numero di insiemi di tipo \(AB\) è dato dal prodotto delle palline che possono essere estratte dall’urna \(A\) (5) e da quelle che possono essere estratte dall’urna \(B\) (6), ovvero \(5 \cdot 6 = 30\). In modo analogo, si ottengono 15 insiemi di tipo \(AC\), 10 di tipo \(AD\), 18 di tipo \(BC\), 12 di tipo \(BD\), 6 di tipo \(CD\). Quindi, per la regola della somma, il numero totale di insiemi distinti che si possono formare con due palline provenienti dalle quattro urne è dato dalla somma di questi valori, ovvero \(30 + 15 + 10 + 18 + 12 + 6 = 91\). Pertanto, ci sono 91 insiemi composti da due palline, ciascuna estratta da un’urna differente, che si possono formare.
In conclusione, il principio del prodotto e il principio della somma sono due concetti fondamentali del calcolo combinatorio. In generale, il principio del prodotto si applica quando si tratta di eventi indipendenti che si verificano in successione, mentre il principio della somma si applica quando si tratta di eventi mutuamente esclusivi (cioè non possono accadere contemporaneamente) e si cerca di calcolare il numero totale di possibili risultati.
15.3. Il modello dell’urna#
I problemi di combinatoria spesso coinvolgono l’estrazione di palline da urne, le quali rappresentano dei modelli delle corrispondenti situazioni considerate. Una procedura comune per rappresentare queste situazioni è il modello dell’urna, che consiste nell’estrazione di \(k\) palline da un’urna contenente \(n\) palline. Le palline possono essere tutte diverse, oppure alcune palline possono essere indistinguibili tra loro. Tra le possibili modalità di estrazione, sono particolarmente importanti:
L’estrazione Bernoulliana di \(k\) palline, che si ottiene estraendo una pallina alla volta e rimettendola nell’urna dopo ogni estrazione;
L’estrazione senza ripetizione di \(k\) palline, che si ottiene estraendo una pallina alla volta senza rimetterla nell’urna dopo l’estrazione;
L’estrazione in blocco di \(k\) palline, che si ottiene estraendo \(k\) palline contemporaneamente.
Per esempio, nel caso di campioni di ampiezza 2 estratti da un’urna con tre elementi \(\{1, 2, 3\}\), abbiamo i seguenti quattro casi:
campionamento con reimmissione tenendo conto dell’ordine di estrazione: \(\{1, 1\}, \{2, 1\}, \{3, 1\}, \{1, 2\}, \{2, 2\}, \{3, 2\}, \{1, 3\}, \{2, 3\}, \{3, 3\}\);
campionamento con reimmissione senza tenere conto dell’ordine di estrazione: \(\{1, 1\}, \{1, 2\}, \{1, 3\}, \{2, 2\}, \{2, 3\}, \{3, 3\}\);
campionamento senza reimmissione tenendo conto dell’ordine di estrazione: \(\{1, 2\}, \{2, 1\}, \{1, 3\}, \{3, 1\}, \{2, 3\}, \{3, 2\}\);
campionamento senza reimmissione e senza tenere conto dell’ordine di estrazione: \(\{1 , 2\}, \{1, 3\}, \{2, 3\}\).
15.4. Permutazioni semplici#
Le permutazioni semplici sono il risultato di uno scambio dell’ordine degli elementi di un insieme che contiene elementi distinti tra loro. Queste permutazioni sono indicate con il simbolo \(P_n\), e il numero di permutazioni semplici di \(n\) elementi distinti è pari al fattoriale di \(n\), cioè \(n!\), come espresso dall’eq. (15.1):
dove il simbolo \(n!\) si legge \(n\) fattoriale ed è uguale al prodotto di \(n\) numeri interi decrescenti da \(n\) fino a 1. Per definizione, il fattoriale di 0 è 1.
Il numero di permutazioni di \(n\) elementi distinti può essere visto come l’estrazione senza rimessa di \(n\) elementi diversi da un’urna contenente gli \(n\) oggetti. Questo ci consente di applicare il principio del prodotto, il quale afferma che il numero di modi in cui è possibile combinare o disporre un insieme di oggetti è dato dal prodotto del numero di scelte possibili per ciascuna categoria di oggetti. Nel caso delle permutazioni, il principio del prodotto si applica nel seguente modo: se abbiamo \(n\) oggetti distinti da disporre in un ordine particolare, il numero di permutazioni possibili è dato dal prodotto del numero di scelte possibili per la prima posizione, per la seconda posizione, per la terza posizione, e così via, fino alla \(n\)-esima posizione.
Esempio 4. Consideriamo l’insieme: \(A = \{a, b, c\}\). Calcoliamo il numero di permutazioni semplici.
Le permutazioni semplici di \(A\) sono: \(\{a, b, c\}\), \(\{a, c, b\}\), \(\{b, c, a\}\), \(\{b, a, c\}\), \(\{c, a, b\}\), \(\{c, b, a\}\), ovvero 6. Applichiamo l’eq. eq-permsem:
Lo strumento principale che usiamo in Python per trovare le permutazioni di un insieme è una libreria specificamente progettata per iterare sugli oggetti in modi diversi, ovvero itertools. Con itertools.permutations() generiamo le permutazioni.
A = {"A", "B", "C"}
print(A)
{'B', 'C', 'A'}
permutations = it.permutations(A)
Per visualizzare il risultato dobbiamo trasformarlo in una tupla:
tuple(permutations)
(('B', 'C', 'A'),
('B', 'A', 'C'),
('C', 'B', 'A'),
('C', 'A', 'B'),
('A', 'B', 'C'),
('A', 'C', 'B'))
Lo stesso risultato si ottiene con
permutations = it.permutations("ABC")
permutations = tuple(permutations)
permutations
(('A', 'B', 'C'),
('A', 'C', 'B'),
('B', 'A', 'C'),
('B', 'C', 'A'),
('C', 'A', 'B'),
('C', 'B', 'A'))
Possiamo ora contare quanti elementi ci sono nella tupla usando la funzione len():
len(permutations)
6
Oppure, possiamo appliare la formula (15.1) mediante la funzione factorial() contenuta nella libreria math di Numpy:
np.math.factorial(3)
6
Esempio 5. Gli anagrammi sono le permutazioni che si ottengono da una parola variando l’ordine delle lettere. Le permutazioni semplici si applicano al caso di parole costituite da lettere tutte diverse tra loro. Ad esempio, con la parola NUMERO si ottengono \(P_6 = 6! = 6\cdot5\cdot4\cdot3\cdot2\cdot1 = 720\) anagrammi.
permutations = it.permutations("NUMERO")
permutations = tuple(permutations)
permutations[1:10]
(('N', 'U', 'M', 'E', 'O', 'R'),
('N', 'U', 'M', 'R', 'E', 'O'),
('N', 'U', 'M', 'R', 'O', 'E'),
('N', 'U', 'M', 'O', 'E', 'R'),
('N', 'U', 'M', 'O', 'R', 'E'),
('N', 'U', 'E', 'M', 'R', 'O'),
('N', 'U', 'E', 'M', 'O', 'R'),
('N', 'U', 'E', 'R', 'M', 'O'),
('N', 'U', 'E', 'R', 'O', 'M'))
len(permutations)
720
np.math.factorial(6)
720
Esempio 6. Un altro esempio riguarda i giochi di carte. Ci sono 52! \(\approx 8 \times 10^{67}\) modi di ordinare un mazzo di carte da poker; questo numero è “quasi” grande come il numero di atomi dell’universo che si stima essere uguale a circa \(10^{80}\).
np.math.factorial(52)
80658175170943878571660636856403766975289505440883277824000000000000
print("{:.2e}".format(np.math.factorial(52)))
8.07e+67
Esempio 7. Le cifre 1, 2, 3, 4 e 5 sono disposte in ordine casuale per formare un numero di cinque cifre.
Quanti diversi numeri di cinque cifre possono essere formati?
Quanti diversi numeri di cinque cifre sono dispari?
Iniziamo a creare una tupla con le cinque cifre:
tuple(range(1, 6))
(1, 2, 3, 4, 5)
Come in precedenza, possiamo usare it.permutations():
permutations = it.permutations(range(1, 6))
permutations = tuple(permutations)
permutations[1:10]
((1, 2, 3, 5, 4),
(1, 2, 4, 3, 5),
(1, 2, 4, 5, 3),
(1, 2, 5, 3, 4),
(1, 2, 5, 4, 3),
(1, 3, 2, 4, 5),
(1, 3, 2, 5, 4),
(1, 3, 4, 2, 5),
(1, 3, 4, 5, 2))
Ci sono 120 permutazioni.
len(permutations)
120
Per trovare i numeri dispari tra queste 120 permutazioni utilizziamo la funzione sum() in Python abbinato alle espressioni for e in. Accediamo al quinto elemento di una permutazione utilizzando la notazione [4] (il primo elemento è indicato con 0, quindi il quinto è 4):
sum(permutation[4] % 2 for permutation in permutations)
72
Possiamo controllare questo teoricamente: nel caso presente, ci sono tre possibili cifre dispari per l’ultima posizione di un numero di cinque cifre: 1, 3 e 5. Dopo aver scelto una di queste, le cifre rimanenti nelle prime quattro posizioni possono essere formate in 4! modi. Pertanto:
math.factorial(4) * 3
72
15.5. Disposizioni semplici#
Le disposizioni semplici rappresentano tutti i modi in cui un insieme di oggetti può essere disposto in sequenza, tenendo conto dell’ordine in cui gli oggetti vengono scelti e senza permettere la scelta di un oggetto più di una volta.
Quindi, se abbiamo un insieme di \(n\) oggetti distinti e vogliamo selezionarne \(k\) per formare una sequenza, le disposizioni semplici rappresentano tutti i sottoinsiemi di \(k\) oggetti distinti che possono essere selezionati dall’insieme di \(n\) oggetti distinti in modo tale che l’ordine in cui vengono selezionati sia importante.
Ad esempio, se abbiamo l’insieme di oggetti \({a,b,c}\) e vogliamo selezionare due oggetti per formare una sequenza, le disposizioni semplici sarebbero: \(ab\), \(ba\), \(ac\), \(ca\), \(bc\), \(cb\). Nota che, in questo caso, l’ordine in cui gli oggetti vengono scelti è importante e ogni oggetto viene scelto una sola volta.
Il numero di disposizioni semplici di \(n\) elementi distinti della classe \(k\) è indicato con \(D_{n,k}\) e può essere calcolato dividendo il numero di permutazioni di \(n\) oggetti distinti per il numero di permutazioni dei restanti \(n-k\) oggetti distinti, poiché ogni disposizione semplice può essere ottenuta come una permutazione di un sottoinsieme di \(k\) oggetti distinti.
Quindi, il numero di disposizioni semplici di \(n\) elementi distinti della classe \(k\) è dato da
dove \(n!\) rappresenta il numero di permutazioni di \(n\) oggetti distinti e \((n-k)!\) rappresenta il numero di permutazioni dei restanti \(n-k\) oggetti distinti.
Esempio 8. Consideriamo l’insieme: \(A = \{a, b, c\}\). Qual è il numero di disposizioni semplici di classe 2? Come abbiamo visto sopra, le disposizioni semplici di classe 2 sono \(\{a, b\}\), \(\{b, a\}\), \(\{a, c\}\), \(\{c, a\}\), \(\{b, c\}\), \(\{c, b\}\), ovvero 6.
Applichiamo l’eq. (15.2):
In maniera equivalente possiamo trovare il risultato usando itertools.permutations(iterable, k). Tale istruzione ci consente di trovare il numero di permutazioni possibili di tutti i sottoinsiemi di \(k\) elementi distinti, ovvero il numero di diverse sequenze ordinate che possiamo ottenere scegliendo \(k\) oggetti dall’insieme.
tuple(it.permutations("ABC", 2))
(('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B'))
res = tuple(it.permutations("ABC", 2))
len(res)
6
Oppure possiamo implementare l’eq. (15.2):
def simple_disp(n, k):
return np.math.factorial(n) / np.math.factorial(n - k)
simple_disp(3, 2)
6.0
15.6. Combinazioni semplici#
Le combinazioni semplici rappresentano il numero di modi in cui \(k\) oggetti diversi possono essere scelti tra \(n\) oggetti distinti, ma a differenza delle disposizioni semplici, non tiene conto dell’ordine in cui vengono scelti. In altre parole, le combinazioni semplici rappresentano tutti i possibili sottoinsiemi di \(k\) elementi distinti scelti tra \(n\) elementi distinti, senza considerare l’ordine di estrazione.
Questo concetto può essere modellato attraverso l’estrazione senza reimmissione di \(k\) oggetti da un’urna contenente \(n\) oggetti differenti. Tuttavia, a differenza delle disposizioni semplici, le combinazioni semplici considerano distinti solo i raggruppamenti che differiscono almeno per un elemento.
Gli elementi di ciascuna combinazione di \(k\) oggetti possono essere ordinati tra loro in \(k!\) modi diversi. Pertanto, il numero di combinazioni semplici è dato dal numero di disposizioni semplici \(D_{n,k}\) diviso per il numero di permutazioni \(P_k\) dei \(k\) elementi.
Il numero di combinazioni semplici \(C_{n,k}\) è espresso dall’equazione
che è spesso indicata con il simbolo \(\binom{n}{k}\) e viene chiamato “coefficiente binomiale”. In sintesi, le combinazioni semplici rappresentano il numero di sottoinsiemi di \(k\) elementi distinti scelti da un insieme di \(n\) elementi distinti senza considerare l’ordine di estrazione, e il numero di combinazioni semplici è dato dalla formula \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\).
Esempio 9. Per l’insieme \(A = \{a, b, c\}\) si trovino le combinazioni semplici di classe 2.
Le combinazioni semplici dell’insieme \(A\) sono \(\{a, b\}\), \(\{a, c\}\), \(\{b, c\}\), ovvero 3. Applichiamo l’eq. (15.3):
Usiamo itertools:
c_nk = tuple(it.combinations("ABC", 2))
c_nk
(('A', 'B'), ('A', 'C'), ('B', 'C'))
len(c_nk)
3
La soluzione si trova anche usando la funzione comb() della libreria math.
math.comb(3, 2)
3
Oppure usando la funzione comb() della libreria scipy.special.
import scipy.special as sp
sp.comb(3, 2)
3.0
Esempio 10. Quanti gruppi di 2 si possono formare con 5 individui?
c_nk = tuple(it.combinations(range(5), 2))
c_nk
((0, 1),
(0, 2),
(0, 3),
(0, 4),
(1, 2),
(1, 3),
(1, 4),
(2, 3),
(2, 4),
(3, 4))
len(c_nk)
10
ovvero
math.comb(5, 2)
10
Esempio 11. Ho un’associazione con 50 soci. Devo scegliere 5 membri che compongano il comitato direttivo. Quante possibili scelte?
math.comb(50, 5)
2118760
Esempio 12. Una gelateria offre 15 gusti di gelato differenti. Quante coppe diverse posso formare se ognuna contiene 3 gusti di gelato differenti tra loro?
math.comb(15, 3)
455
Esempio 13. Uno studente deve rispondere a 5 domande su 10. Solo 5 su 10. Quante possibili scelte ha?
math.comb(10, 5)
252
15.7. Watermark#
%load_ext watermark
%watermark -n -u -v -iv -w
Last updated: Sat Jun 17 2023
Python implementation: CPython
Python version : 3.11.3
IPython version : 8.12.0
pandas : 1.5.3
seaborn : 0.12.2
scipy : 1.10.1
numpy : 1.24.3
matplotlib: 3.7.1
Watermark: 2.3.1