[Appendice H — Calcolo combinatorio]{#sec-apx-combinatorics .quarto-section-identifier}

Appendice H — Calcolo combinatorio

Il calcolo combinatorio studia le tecniche per contare il numero di configurazioni possibili che si possono ottenere selezionando e organizzando elementi secondo regole prestabilite. Questi strumenti sono indispensabili in probabilità per determinare lo spazio campionario di esperimenti complessi e per calcolare probabilità classiche. In questa appendice, presenteremo i concetti fondamentali attraverso il modello intuitivo del campionamento da un’urna, introducendo prima i principi basilari del conteggio e poi esaminando le principali strutture combinatorie: permutazioni, disposizioni e combinazioni.

H.1 Principio della somma

Il principio della somma (o principio additivo) afferma che se un insieme può essere suddiviso in sottoinsiemi mutuamente esclusivi, la cardinalità dell’insieme è data dalla somma delle cardinalità dei sottoinsiemi.

Formalmente, se \(A_1, A_2, \dots, A_k\) sono insiemi tali che \(A_i \cap A_j = \emptyset\) per ogni \(i \neq j\), allora:

\[ \left| \bigcup_{i=1}^k A_i \right| = \sum_{i=1}^k |A_i|. \]

Esempio.
Un distributore automatico contiene tre scomparti indipendenti:

scomparto A: 10 caramelle alla menta,
scomparto B: 8 caramelle alla frutta,
scomparto C: 12 caramelle al cioccolato.

Poiché i scomparti sono distinti e non sovrapposti, il numero totale di caramelle è:

\[ n_{\text{tot}} = 10 + 8 + 12 = 30. \]

# Calcolo mediante principio della somma
A <- 10; B <- 8; C <- 12
totale_caramelle <- A + B + C
totale_caramelle
#> [1] 30

Risultato: Il distributore contiene 30 caramelle.

H.2 Principio del prodotto

Il principio del prodotto (o principio moltiplicativo) stabilisce che se un’operazione è costituita da \(k\) fasi successive e indipendenti, e se la fase \(i\)-esima può essere compiuta in \(n_i\) modi distinti, allora il numero totale di risultati possibili è dato dal prodotto delle scelte individuali.

Formalmente:

\[ n_{\text{tot}} = \prod_{i=1}^k n_i = n_1 \cdot n_2 \cdot \dots \cdot n_k. \]

Esempio.
Consideriamo quattro urne contenenti palline colorate:

Urna A: 5 palline,
Urna B: 6 palline,
Urna C: 3 palline,
Urna D: 2 palline.

Vogliamo formare insiemi di due palline estratte da due urne distinte. Per ogni coppia di urne \((X, Y)\), il numero di possibili coppie di palline è dato dal prodotto delle cardinalità delle due urne. Il totale si ottiene applicando congiuntamente il principio del prodotto (per le singole coppie) e il principio della somma (per sommare i contributi di tutte le coppie):

\[ n_{\text{tot}} = (5 \times 6) + (5 \times 3) + (5 \times 2) + (6 \times 3) + (6 \times 2) + (3 \times 2) = 91. \]

# Calcolo mediante principi del prodotto e della somma
AB <- 5 * 6
AC <- 5 * 3
AD <- 5 * 2
BC <- 6 * 3
BD <- 6 * 2
CD <- 3 * 2

totale_insiemi <- sum(AB, AC, AD, BC, BD, CD)
totale_insiemi
#> [1] 91

Risultato: è possibile formare 91 insiemi distinti di due palline provenienti da urne differenti.

H.3 Modello dell’urna e metodi di campionamento

Molti problemi combinatori possono essere concettualizzati come estrazioni di palline da un’urna. Le modalità di campionamento si classificano secondo due dimensioni fondamentali:

ripetizione: le estrazioni avvengono con o senza reinserimento della pallina nell’urna.
ordine: la sequenza di estrazione è rilevante o meno.

Le quattro combinazioni possibili danno origine a schemi di conteggio distinti:

Ripetizione	Ordine	Schema di Campionamento	Esempio
Con	Con	Sequenze ordinate con elementi ripetuti	Formazione di codici PIN
Senza	Con	Sequenze ordinate di elementi distinti	Assegnazione di premi (1º, 2º, 3º posto)
Con	Senza	Multinsiemi (insiemi con ripetizioni)	Scelta di ingredienti da un menu
Senza	Senza	Sottoinsiemi di elementi distinti	Formazione di commissioni

Il seguente esempio in R illustra i quattro casi fondamentali per un’urna con tre elementi \(\{a, b, c\}\):

urna <- c("a", "b", "c")

# 1. Con ripetizione e con ordine
campionamento1 <- expand.grid(urna, urna) |>
    rename(Elemento1 = Var1, Elemento2 = Var2)

# 2. Senza ripetizione e con ordine
campionamento2 <- permutations(n = 3, r = 2, v = urna) |>
    as.data.frame() |>
    rename(Elemento1 = V1, Elemento2 = V2)

# 3. Con ripetizione e senza ordine
campionamento3 <- combinations(
    n = 3, r = 2, v = urna, repeats.allowed = TRUE
) |>
    as.data.frame() |>
    rename(Elemento1 = V1, Elemento2 = V2)

# 4. Senza ripetizione e senza ordine
campionamento4 <- combinations(n = 3, r = 2, v = urna) |>
    as.data.frame() |>
    rename(Elemento1 = V1, Elemento2 = V2)

# Risultati
list(
    `Con ripetizione e ordine` = campionamento1,
    `Senza ripetizione e con ordine` = campionamento2,
    `Con ripetizione e senza ordine` = campionamento3,
    `Senza ripetizione e senza ordine` = campionamento4
)
#> $`Con ripetizione e ordine`
#>   Elemento1 Elemento2
#> 1         a         a
#> 2         b         a
#> 3         c         a
#> 4         a         b
#> 5         b         b
#> 6         c         b
#> 7         a         c
#> 8         b         c
#> 9         c         c
#> 
#> $`Senza ripetizione e con ordine`
#>   Elemento1 Elemento2
#> 1         a         b
#> 2         a         c
#> 3         b         a
#> 4         b         c
#> 5         c         a
#> 6         c         b
#> 
#> $`Con ripetizione e senza ordine`
#>   Elemento1 Elemento2
#> 1         a         a
#> 2         a         b
#> 3         a         c
#> 4         b         b
#> 5         b         c
#> 6         c         c
#> 
#> $`Senza ripetizione e senza ordine`
#>   Elemento1 Elemento2
#> 1         a         b
#> 2         a         c
#> 3         b         c

H.4 Permutazioni

Le permutazioni rappresentano tutti i possibili ordinamenti di \(n\) elementi distinti. Il numero di permutazioni di \(n\) oggetti è dato dal fattoriale di \(n\):

\[ P_n = n! = n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 1. \]

H.4.1 Derivazione Intuitiva

Per disporre \(n\) elementi in sequenza:

scelta del primo elemento: \(n\) possibilità;
scelta del secondo elemento: \(n-1\) possibilità;
…
scelta dell’\(n\)-esimo elemento: \(1\) possibilità.

Applicando il principio del prodotto: \(P_n = n \times (n-1) \times \dots \times 1 = n!\).

H.4.2 Metodo di campionamento

Corrisponde a campionamento senza ripetizione e con ordine quando si estraggono tutti gli \(n\) elementi disponibili.

Esempio: le permutazioni di \(\{a, b, c\}\) sono: \[ P_3 = 3! = 6 \]

A <- c("a", "b", "c")
perm <- permutations(n = 3, r = 3, v = A)
perm
#>      [,1] [,2] [,3]
#> [1,] "a"  "b"  "c" 
#> [2,] "a"  "c"  "b" 
#> [3,] "b"  "a"  "c" 
#> [4,] "b"  "c"  "a" 
#> [5,] "c"  "a"  "b" 
#> [6,] "c"  "b"  "a"
nrow(perm)  # Verifica: 6
#> [1] 6

H.5 Disposizioni

Le disposizioni (o permutazioni parziali) rappresentano le sequenze ordinate di \(k\) elementi distinti scelti da un insieme di \(n\) elementi. Il numero di disposizioni è:

\[ D_{n,k} = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot \dots \cdot (n-k+1). \]

H.5.1 Derivazione Intuitiva

Per formare una sequenza ordinata di \(k\) elementi da \(n\):

scelta del primo elemento: \(n\) possibilità;
scelta del secondo elemento: \(n-1\) possibilità;
…
scelta del \(k\)-esimo elemento: \(n-k+1\) possibilità.

Il prodotto di questi termini fornisce la formula delle disposizioni.

H.5.2 Metodo di campionamento

Corrisponde a campionamento senza ripetizione e con ordine quando si estraggono \(k < n\) elementi.

Esempio: disposizioni di 2 elementi da \(\{a, b, c\}\): \[ D_{3,2} = \frac{3!}{(3-2)!} = \frac{3 \times 2 \times 1}{1} = 6 \]

disp <- permutations(n = 3, r = 2, v = A)
disp
#>      [,1] [,2]
#> [1,] "a"  "b" 
#> [2,] "a"  "c" 
#> [3,] "b"  "a" 
#> [4,] "b"  "c" 
#> [5,] "c"  "a" 
#> [6,] "c"  "b"
nrow(disp)  # Verifica: 6
#> [1] 6

H.6 Combinazioni

Le combinazioni rappresentano i sottoinsiemi non ordinati di \(k\) elementi scelti da un insieme di \(n\) elementi. Il numero di combinazioni è dato dal coefficiente binomiale:

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

H.6.1 Derivazione intuitiva

Per ottenere il numero di combinazioni, si parte dal numero di disposizioni \(D_{n,k}\) e si divide per \(k!\) (il numero di modi in cui i \(k\) elementi possono essere permutati), poiché nell’insieme l’ordine non è rilevante:

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

H.6.2 Metodo di campionamento

Corrisponde a campionamento senza ripetizione e senza ordine.

Esempio: combinazioni di 2 elementi da \(\{a, b, c\}\): \[ C_{3,2} = \binom{3}{2} = \frac{3!}{2!1!} = 3 \]

comb <- combinations(n = 3, r = 2, v = A)
comb
#>      [,1] [,2]
#> [1,] "a"  "b" 
#> [2,] "a"  "c" 
#> [3,] "b"  "c"
nrow(comb)  # Verifica: 3
#> [1] 3

H.7 Quadro sinottico dei metodi combinatori

Concetto	Ripetizione	Ordine	Formula	Esempio Tipico
Permutazioni	No	Sì	\(n!\)	Ordinamento di \(n\) oggetti distinti
Disposizioni	No	Sì	\(\frac{n!}{(n-k)!}\)	Formazione di podi (1º, 2º, 3º posto)
Combinazioni	No	No	\(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)	Selezione di commissioni o squadre
Disposizioni con ripetizione	Sì	Sì	\(n^k\)	Formazione di password
Combinazioni con ripetizione	Sì	No	\(\binom{n+k-1}{k}\)	Scelta di ingredienti con possibilità di duplicati

H.8 Conclusioni

Il calcolo combinatorio fornisce gli strumenti fondamentali per quantificare il numero di esiti possibili in esperimenti casuali. La corretta applicazione di permutazioni, disposizioni e combinazioni dipende dalla considerazione attenta di due attributi chiave: la possibilità di ripetizione degli elementi e l’importanza del loro ordinamento. La padronanza di questi concetti, illustrata tramite il modello dell’urna e implementata in R, costituisce un prerequisito fondamentale per lo studio della probabilità e della statistica inferenziale.