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
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 è
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
Il numero di insiemi di tipo
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
L’estrazione Bernoulliana di
palline, che si ottiene estraendo una pallina alla volta e rimettendola nell’urna dopo ogni estrazione;L’estrazione senza ripetizione di
palline, che si ottiene estraendo una pallina alla volta senza rimetterla nell’urna dopo l’estrazione;L’estrazione in blocco di
palline, che si ottiene estraendo palline contemporaneamente.
Per esempio, nel caso di campioni di ampiezza 2 estratti da un’urna con tre elementi
campionamento con reimmissione tenendo conto dell’ordine di estrazione:
;campionamento con reimmissione senza tenere conto dell’ordine di estrazione:
;campionamento senza reimmissione tenendo conto dell’ordine di estrazione:
;campionamento senza reimmissione e senza tenere conto dell’ordine di estrazione:
.
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
dove il simbolo
Il numero di permutazioni di
Esempio 4. Consideriamo l’insieme:
Le permutazioni semplici di
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
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!
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
Ad esempio, se abbiamo l’insieme di oggetti
Il numero di disposizioni semplici di
Quindi, il numero di disposizioni semplici di
dove
Esempio 8. Consideriamo l’insieme:
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
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
Questo concetto può essere modellato attraverso l’estrazione senza reimmissione di
Gli elementi di ciascuna combinazione di
Il numero di combinazioni semplici
che è spesso indicata con il simbolo
Esempio 9. Per l’insieme
Le combinazioni semplici dell’insieme
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