Appendice G — Calcolo combinatorio

here::here("code", "_common.R") |>
    source()

if (!requireNamespace("pacman")) install.packages("pacman")
pacman::p_load(gtools, combinat)

Il calcolo combinatorio si occupa di determinare il numero di modi in cui è possibile combinare, ordinare o disporre elementi di uno o più insiemi, seguendo regole predefinite. Molti problemi di probabilità richiedono l’applicazione di tecniche combinatorie per calcolare le probabilità di eventi complessi. In questo capitolo, esploreremo le nozioni fondamentali del calcolo combinatorio, mettendo in relazione i suoi concetti con i vari metodi di campionamento dall’urna. Descriveremo i principi della somma e del prodotto, che costituiscono le basi del calcolo combinatorio e trovano applicazione in problemi più complessi, come permutazioni, disposizioni e combinazioni.

G.1 Principio della somma

Il principio della somma si applica quando un insieme può essere suddiviso in sottoinsiemi disgiunti (cioè senza sovrapposizioni). In questo caso, il numero totale di elementi è dato dalla somma degli elementi dei sottoinsiemi:

\[ n_{\text{tot}} = n_1 + n_2 + \dots + n_k . \]

Esempio G.1 Un distributore contiene tre diversi scomparti di caramelle:

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

Quante caramelle diverse ci sono in totale nel distributore?

Secondo il principio della somma, il totale è dato dalla somma delle caramelle nei tre scomparti:

\[ n_{\text{tot}} = n_A + n_B + n_C . \]

Calcolo in R:

A <- 10
B <- 8
C <- 12

totale_caramelle <- A + B + C
totale_caramelle
#> [1] 30

Risultato: Nel distributore ci sono 30 caramelle in totale.

G.2 Principio del prodotto

Il principio del prodotto si applica quando un’operazione può essere suddivisa in più fasi indipendenti, ciascuna con un numero di possibilità specifico. Il numero totale di combinazioni è dato dal prodotto delle possibilità offerte da ciascuna fase:

\[ n_{\text{tot}} = n_1 \cdot n_2 \cdot \dots \cdot n_k . \]

Esempio G.2 Poniamo di avere quattro urne:

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

Vogliamo formare insiemi di due palline, ciascuna estratta da urne differenti.

Secondo il principio del prodotto, per ogni coppia di urne, il numero di combinazioni è dato dal prodotto delle palline nelle due urne. Successivamente, usiamo il principio della somma per sommare tutte le possibilità.

\[ n_{\text{tot}} = AB + AC + AD + BC + BD + CD \]

Calcolo in R:

AB <- 5 * 6
AC <- 5 * 3
AD <- 5 * 2
BC <- 6 * 3
BD <- 6 * 2
CD <- 3 * 2

totale_insiemi <- AB + AC + AD + BC + BD + CD
totale_insiemi
#> [1] 91

Risultato: Si possono formare 91 insiemi di due palline, ciascuna estratta da urne differenti.

G.3 Il modello dell’urna e i metodi di campionamento

I problemi combinatori spesso si riducono a modelli di estrazione di palline da urne, con quattro principali varianti:

Con ripetizione e ordine: ogni estrazione rimette la pallina nell’urna (campionamento Bernoulliano).
Senza ripetizione e con ordine: ogni estrazione rimuove la pallina.
Con ripetizione e senza ordine: si considerano le combinazioni, ignorando l’ordine.
Senza ripetizione e senza ordine: si contano le combinazioni senza rimettere la pallina.

Esempio G.3

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

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

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

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

# Senza ripetizione e senza ordine
campionamento4 <- combinations(n = length(urna), 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

G.4 Permutazioni Semplici

Le permutazioni rappresentano tutte le disposizioni possibili di un insieme di \(n\) elementi distinti, considerando l’ordine. Il numero totale di permutazioni è dato dalla formula:

\[ P_n = n! \]

dove \(n!\) (n fattoriale) indica il prodotto di tutti i numeri interi da 1 a \(n\):

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

Esempio G.4 Calcoliamo tutte le permutazioni possibili per un insieme di tre elementi distinti \(\{a, b, c\}\). Il numero di permutazioni atteso è:

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

Implementazione in R:

# Insieme di partenza
A <- c("a", "b", "c")

# Calcolo delle permutazioni
perm <- permutations(n = length(A), r = length(A), v = A)

# Visualizzazione delle permutazioni
print(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"

# Verifica del numero di permutazioni
nrow(perm)
#> [1] 6

Le permutazioni dell’insieme sono:

\[ \begin{aligned} &\{a, b, c\}, \{a, c, b\}, \{b, a, c\}, \{b, c, a\}, \{c, a, b\}, \{c, b, a\} . \end{aligned} \]

Il numero totale è \(P_3 = 6\).

G.4.1 Caratteristiche delle Permutazioni

Le permutazioni rappresentano un caso di campionamento senza ripetizione con ordine:

Senza ripetizione: Ogni elemento può essere utilizzato una sola volta.
Con ordine: La disposizione degli elementi è importante.

G.5 Disposizioni Semplici

Le disposizioni semplici sono sequenze ordinate di \(k\) elementi scelti da un insieme di \(n\) elementi distinti. Il numero totale di disposizioni si calcola con la formula:

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

dove:

\(n!\) (fattoriale di \(n\)) è il prodotto dei numeri interi da 1 a \(n\),
\((n-k)!\) rappresenta il fattoriale della differenza tra il numero totale di elementi e quelli scelti.

Esempio G.5 Consideriamo l’insieme\(\{a, b, c\}\) (\(n = 3\)) e calcoliamo tutte le disposizioni possibili di 2 elementi (\(k = 2\)).
Il numero di disposizioni atteso è:

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

Implementazione in R:

# Insieme di partenza
A <- c("a", "b", "c")

# Calcolo delle disposizioni di 2 elementi
disp <- permutations(n = length(A), r = 2, v = A)

# Visualizzazione delle disposizioni
print(disp)
#>      [,1] [,2]
#> [1,] "a"  "b" 
#> [2,] "a"  "c" 
#> [3,] "b"  "a" 
#> [4,] "b"  "c" 
#> [5,] "c"  "a" 
#> [6,] "c"  "b"

# Verifica del numero di disposizioni
nrow(disp)
#> [1] 6

Le disposizioni di 2 elementi sono: \[ \{a, b\}, \{a, c\}, \{b, a\}, \{b, c\}, \{c, a\}, \{c, b\} . \]
Il numero totale è \(D_{3,2} = 6\).

G.5.1 Caratteristiche delle Disposizioni Semplici

Le disposizioni semplici rappresentano un caso di campionamento senza ripetizione e con ordine:

Senza ripetizione: Ogni elemento può essere utilizzato una sola volta.
Con ordine: La disposizione degli elementi selezionati è importante.

G.6 Combinazioni Semplici

Le combinazioni semplici rappresentano i modi di selezionare \(k\) elementi da un insieme di \(n\) elementi senza considerare l’ordine. Il numero totale di combinazioni si calcola con la formula:

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

dove:

\(n!\) è il fattoriale di \(n\),
\(k!\) è il fattoriale di \(k\),
\((n-k)!\) è il fattoriale della differenza tra il numero totale di elementi e quelli scelti.

Esempio G.6 Consideriamo l’insieme \(\{a, b, c\}\) (\(n = 3\)) e calcoliamo tutte le combinazioni possibili di 2 elementi (\(k = 2\)).

Il numero di combinazioni atteso è:

\[ C_{3,2} = \binom{3}{2} = \frac{3!}{2! \cdot (3-2)!} = \frac{3 \cdot 2 \cdot 1}{2 \cdot 1 \cdot 1} = 3 . \]

Implementazione in R:

# Insieme di partenza
A <- c("a", "b", "c")

# Calcolo delle combinazioni di 2 elementi
comb <- combinations(n = length(A), r = 2, v = A)

# Visualizzazione delle combinazioni
print(comb)
#>      [,1] [,2]
#> [1,] "a"  "b" 
#> [2,] "a"  "c" 
#> [3,] "b"  "c"

# Verifica del numero di combinazioni
nrow(comb)
#> [1] 3

Le combinazioni di 2 elementi sono: \[ \{a, b\}, \{a, c\}, \{b, c\} . \]
Il numero totale è \(C_{3,2} = 3\).

G.6.1 Caratteristiche delle Combinazioni Semplici

Le combinazioni semplici rappresentano un caso di campionamento senza ripetizione e senza ordine:

Senza ripetizione: Ogni elemento può essere selezionato una sola volta.
Senza ordine: L’ordine degli elementi selezionati non ha importanza (\(\{a, b\}\) è uguale a \(\{b, a\}\)).

Questo capitolo ha illustrato i legami tra i metodi del calcolo combinatorio e le diverse modalità di campionamento, mostrando come implementare questi concetti in R.