Appendice J — 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
import arviz as az

RANDOM_SEED = 42
rng = np.random.default_rng(RANDOM_SEED)
az.style.use("arviz-darkgrid")
sns.set_theme(palette="colorblind")
%config InlineBackend.figure_format = 'retina'

J.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:

\[ n_{\text{tot}} = n_1 \cdot n_2 \cdots n_{k-1} \cdot n_k. \]

Esempio 1. Ho a disposizione 2 paia di scarpe, 3 paia di pantaloni e 5 magliette. In quanti modi diversi mi posso vestire?

\[ 2 \cdot 3 \cdot 5 = 30 \]

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 \cdot 10^3) = 1/26^3 = 0.0000569. \]

10**3 / (26**3 * 10**3)

5.689576695493855e-05

J.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.

J.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\}\).

J.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. {eq}eq-permsem:

\[ P_n = n! \] (eq-permsem)

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.

Per esempio, consideriamo il caso di disporre tre oggetti, A, B e C. Ci sono tre modi per scegliere il primo oggetto: A, B o C. Una volta scelto il primo oggetto, ci sono due modi per scegliere il secondo oggetto. Infine, rimane un solo modo per scegliere l’ultimo oggetto. Possiamo concettualizzare questo processo come un albero, dove il numero totale di foglie è uguale al numero di permutazioni. Per calcolare il numero di foglie, basta moltiplicare sequenzialmente il numero di rami a ogni livello, cioè \(3 \times 2 \times 1\).

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. {ref}eq-permsem:

\[ P_n = P_3 = 3! = 3 \cdot 2 \cdot 1 = 6. \]

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)

{'A', 'B', 'C'}

permutations = it.permutations(A)

Per visualizzare il risultato dobbiamo trasformarlo in una tupla:

tuple(permutations)

(('A', 'B', 'C'),
 ('A', 'C', 'B'),
 ('B', 'A', 'C'),
 ('B', 'C', 'A'),
 ('C', 'A', 'B'),
 ('C', 'B', 'A'))

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)

Oppure, possiamo appliare la formula {eq}eq-permsem mediante la funzione factorial() contenuta nella libreria math di Numpy:

math.factorial(3)

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)

math.factorial(6)

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}\).

math.factorial(52)

80658175170943878571660636856403766975289505440883277824000000000000

print("{:.2e}".format(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)

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)

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

J.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

\[ D_{n,k} = \frac{n!}{(n-k)!}, \] (eq_disp_simple)

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. {eq}eq_disp_simple:

\[ D_{n,k} = \frac{n!}{(n-k)!} = 3 \cdot 2 = 6. \]

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)

Oppure possiamo implementare l’eq. {eq}eq_disp_simple:

def simple_disp(n, k):
    return math.factorial(n) / math.factorial(n - k)


simple_disp(3, 2)

6.0

J.6 Combinazioni semplici

Le combinazioni sono simili alle permutazioni, ma ignorano l’ordine degli elementi. In altre parole, le combinazioni rappresentano i modi di scegliere \(k\) elementi distinti da\(n\)elementi senza considerare l’ordine. Ad esempio, scegliendo 2 elementi da 3 (A, B e C), le permutazioni sono 6 (AB, BA, AC, CA, BC, CB), mentre le combinazioni sono 3 (AB, AC, BC).

Per calcolare le combinazioni, prima calcoliamo le permutazioni \(D_{n,k}\) e poi dividiamo per \(k!\). Questo perché ci sono \(k!\) modi per disporre \(k\) elementi in ordine diverso, ma tutte queste disposizioni contano come una singola combinazione. La formula generale per le combinazioni è:

\[ C_{n,k} = \binom{n}{k} = \frac{D_{n,k}}{P_k} = \frac{n!}{k!(n-k)!}, \] (eq_combsemp)

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.

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. {eq}eq_combsemp:

\[ C_{n,k} = \binom{n}{k} = \binom{3}{2} = 3. \]

Usiamo itertools:

c_nk = tuple(it.combinations("ABC", 2))
c_nk

(('A', 'B'), ('A', 'C'), ('B', 'C'))

len(c_nk)

La soluzione si trova anche usando la funzione comb() della libreria math.

math.comb(3, 2)

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)

ovvero

math.comb(5, 2)

Esempio 11. Ho un’associazione con 50 soci. Devo scegliere 5 membri che compongano il comitato direttivo. Quante possibili scelte?

math.comb(50, 5)

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)

Esempio 13. Uno studente deve rispondere a 5 domande su 10. Solo 5 su 10. Quante possibili scelte ha?

math.comb(10, 5)

Esempio 14. Consideriamo un incidente del 2009 quando il Governatore della California Arnold Schwarzenegger inviò un messaggio all’assemblea statale riguardo il veto al disegno di legge 1176. Questo messaggio formava un acrostico volgare con le prime lettere di ogni riga.

Ci possiamo chiedere quale sia la probabilità che questo acrostico sia stato casuale. Per rispondere a questa domanda, calcoliamo le combinazioni di due diversi eventi.

Il messaggio di Arnold Schwarzenegger è composto da 85 parole. Supponiamo che il messaggio sia stato diviso in 7 righe in modo casuale. Per creare 7 righe, dobbiamo inserire 6 interruzioni di riga. Queste interruzioni di riga possono essere inserite in qualsiasi posizione tra le parole.

Poiché ci sono 85 parole, ci sono 84 spazi tra le parole (prima della seconda parola, terza parola, e così via). Il numero di modi in cui possiamo inserire 6 interruzioni di riga in 84 spazi è dato dalla combinazione:

\[ \binom{84}{6} = \frac{84!}{6!(78!)} \approx 406,481,544. \]

Calcoliamo ora il numero di modi in cui questo particolare acrostico può essere ottenuto.

Supponiamo che l’acrostico “FUCKYOU” possa essere formato solo in un numero limitato di combinazioni specifiche. Per calcolare queste combinazioni, dobbiamo considerare le parole che iniziano con ciascuna delle lettere dell’acrostico e le posizioni in cui possono essere inserite le interruzioni di riga.

Identificazione delle parole chiave:
- F: “For”
- U: “unnecessary”
- C: “conversation”
- K: “keeping”
- Y: “you”
- O: “over”
- U: “until”
Determinazione delle possibili interruzioni di riga: Per formare l’acrostico, dobbiamo posizionare le interruzioni di riga in modo che le parole chiave siano all’inizio delle righe. Le interruzioni possono essere inserite tra le parole chiave, con un certo numero di parole tra di esse.
Conteggio delle combinazioni:
- Tra “For” e “unnecessary”: 11 possibilità
- Tra “unnecessary” e “conversation”: 3 possibilità
- Tra “conversation” e “keeping”: 9 possibilità
- Tra “keeping” e “you”: 2 possibilità
- Tra “you” e “over”: 2 possibilità
- Tra “over” e “until”: 1 possibilità
Quindi, il numero totale di combinazioni è:

\[ 11 \times 3 \times 9 \times 2 \times 2 \times 1 = 1,188. \]

In conclusione, la probabilità che l’acrostico volgare si verifichi casualmente è data dal rapporto tra il numero di combinazioni specifiche che formano l’acrostico (1,188) e il numero totale di modi per inserire 6 interruzioni di riga in 84 spazi (406,481,544):

\[ \frac{1,188}{406,481,544} \approx 2.92 \times 10^{-6} \approx 1 \text{ su } 342,000. \]

Questa analisi ci mostra che è estremamente improbabile che l’acrostico volgare sia stato il risultato di una divisione casuale delle righe del messaggio. In altre parole, la probabilità che questo acrostico sia stato generato casualmente è trascurabile.