Appunti del Corso: Capitolo 6 - Calcolo Combinatorio
Introduzione alla Combinatoria: L'Arte del Contare
Il calcolo combinatorio è quella branca della matematica che studia i modi per raggruppare e ordinare gli elementi di un insieme finito, secondo determinate regole. In sostanza, risponde a domande del tipo: "In quanti modi posso...?" oppure "Quante configurazioni possibili ci sono...?". È fondamentale in informatica, ad esempio, per analizzare la complessità degli algoritmi, nel calcolo delle probabilità, nella crittografia e in molte altre aree.
Useremo spesso l'insieme degli indici $I_n = \{1, 2, \dots, n\}$. Ricordiamo che un insieme $A$ ha cardinalità $n$ (cioè $|A|=n$) se esiste una funzione biiettiva $f: I_n \to A$.
Principi di Base del Conteggio
1. Principio della Somma
Se un compito può essere svolto in $m$ modi e un secondo compito (indipendente dal primo e che non può essere svolto contemporaneamente) può essere svolto in $n$ modi, allora ci sono $m+n$ modi per svolgere uno dei due compiti.
Più formalmente: Se $S$ e $T$ sono due insiemi finiti e disgiunti ($S \cap T = \emptyset$), allora la cardinalità della loro unione è la somma delle loro cardinalità:
$|S \cup T| = |S| + |T|$.
Principio della Somma Generalizzato: Se abbiamo $k$ insiemi $S_1, S_2, \dots, S_k$, tutti finiti e a due a due disgiunti (cioè $S_i \cap S_j = \emptyset$ per $i \neq j$), allora:
$|S_1 \cup S_2 \cup \dots \cup S_k| = \sum_{i=1}^{k} |S_i| = |S_1| + |S_2| + \dots + |S_k|$.
Esempio: Se posso scegliere un dolce tra 3 tipi di torte o 2 tipi di gelati, ho $3+2=5$ scelte possibili per il dolce.
2. Principio del Prodotto
Se una procedura può essere scomposta in una sequenza di due compiti, dove ci sono $m$ modi per eseguire il primo compito e, per ciascuno di questi modi, ci sono $n$ modi per eseguire il secondo compito, allora ci sono $m \cdot n$ modi per eseguire l'intera procedura.
Più formalmente: Dati due insiemi finiti $S_1$ e $S_2$, con $|S_1|=m$ e $|S_2|=n$, allora la cardinalità del loro prodotto cartesiano è:
$|S_1 \times S_2| = |S_1| \cdot |S_2| = m \cdot n$.
Principio del Prodotto Generalizzato: Se abbiamo una sequenza di $k$ compiti, dove il primo può essere fatto in $n_1$ modi, il secondo in $n_2$ modi, ..., il $k$-esimo in $n_k$ modi, allora il numero totale di modi per eseguire l'intera sequenza di compiti è:
$n_1 \cdot n_2 \cdot \dots \cdot n_k = \prod_{i=1}^{k} n_i$.
Equivalentemente, per $k$ insiemi finiti $S_1, \dots, S_k$:
$|S_1 \times S_2 \times \dots \times S_k| = \prod_{i=1}^{k} |S_i|$.
Esempio: Se ho 3 magliette e 2 paia di pantaloni, posso vestirmi in $3 \cdot 2 = 6$ modi diversi.
Fattoriale ($n!$)
Il **fattoriale** di un numero naturale non negativo $n$, indicato con $n!$, è il prodotto di tutti i numeri interi positivi minori o uguali a $n$.
Se $n > 0$, $n! = n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 3 \cdot 2 \cdot 1 = \prod_{i=1}^{n} i$.
Per definizione, si pone $0! = 1$. Questa convenzione è utile in molte formule combinatorie.
Si può anche definire ricorsivamente:
$n! = \begin{cases} 1 & \text{se } n=0 \\ n \cdot (n-1)! & \text{se } n > 0 \end{cases}$
$3! = 3 \cdot 2 \cdot 1 = 6$
$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$
Permutazioni: Ordinare Elementi
Una **permutazione** di un insieme di oggetti distinti è un arrangiamento di questi oggetti in un ordine specifico. L'ordine conta!
1. Permutazioni Semplici (di $n$ elementi)
Il numero di permutazioni semplici di $n$ oggetti distinti (cioè, tutti i modi diversi di ordinare $n$ oggetti) è dato da $P_n = n!$.
Esempio: Le permutazioni degli elementi dell'insieme $S=\{a,b,c\}$ (quindi $n=3$) sono:
$(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)$.
Ci sono $3! = 3 \cdot 2 \cdot 1 = 6$ permutazioni.
2. Permutazioni di $k$ Elementi da un Insieme di $n$ Elementi (Disposizioni Semplici senza Ripetizione)
Una permutazione di $k$ elementi scelti da un insieme di $n$ elementi distinti (con $k \le n$), a volte chiamata anche **disposizione semplice di $n$ elementi di classe $k$** ($D_{n,k}$), è una sequenza ordinata di $k$ elementi distinti presi dall'insieme di $n$. Il numero di tali permutazioni/disposizioni è:
$P(n,k) = D_{n,k} = n \cdot (n-1) \cdot \dots \cdot (n-k+1) = \frac{n!}{(n-k)!}$.
Esempio: In quanti modi possiamo scegliere un Presidente e un Segretario da un gruppo di 6 persone?
Qui $n=6$ e $k=2$. L'ordine conta (Presidente-Segretario è diverso da Segretario-Presidente).
Numero di modi = $P(6,2) = \frac{6!}{(6-2)!} = \frac{6!}{4!} = 6 \cdot 5 = 30$.
Formalmente, una permutazione di $k$ elementi di un insieme $S$ (con $|S|=n$) è una funzione iniettiva $f: I_k \to S$. Il numero di tali funzioni è $\frac{n!}{(n-k)!}$.
3. Permutazioni con Ripetizione
Se abbiamo $n$ oggetti, ma alcuni di essi sono indistinguibili (ripetuti), il numero di permutazioni distinte è minore. Se ci sono $n_1$ oggetti di un tipo, $n_2$ di un altro tipo, ..., $n_j$ di un $j$-esimo tipo, con $n_1 + n_2 + \dots + n_j = n$, allora il numero di permutazioni distinte è:
$P_n^{n_1, n_2, \dots, n_j} = \frac{n!}{n_1! \cdot n_2! \cdot \dots \cdot n_j!}$.
Esempio: Quanti anagrammi distinti della parola "MATEMATICA"?
Lunghezza $n=10$.
M: 2 volte ($n_1=2$)
A: 3 volte ($n_2=3$)
T: 2 volte ($n_3=2$)
E: 1 volta ($n_4=1$)
I: 1 volta ($n_5=1$)
C: 1 volta ($n_6=1$)
Numero di anagrammi = $\frac{10!}{2! \cdot 3! \cdot 2! \cdot 1! \cdot 1! \cdot 1!} = \frac{3628800}{2 \cdot 6 \cdot 2} = \frac{3628800}{24} = 151200$.
Disposizioni: Sequenze Ordinate con o senza Ripetizione
Le disposizioni riguardano la formazione di gruppi ordinati di elementi.
1. Disposizioni Semplici (senza ripetizione di elementi)
Una disposizione semplice di $n$ elementi distinti presi a $k$ alla volta (o di classe $k$), indicata $D_{n,k}$, è un modo di scegliere $k$ elementi da $n$ e ordinarli. L'ordine conta e gli elementi non possono ripetersi. Questo è esattamente ciò che abbiamo chiamato "Permutazioni di $k$ elementi da $n$".
$D_{n,k} = \frac{n!}{(n-k)!}$ (per $0 \le k \le n$).
2. Disposizioni con Ripetizione
Una disposizione con ripetizione di $n$ elementi distinti presi a $k$ alla volta, indicata $D'_{n,k}$ (o $D_{n,k}^{(r)}$), è un modo di scegliere $k$ elementi da $n$, dove ogni elemento può essere scelto più volte e l'ordine conta.
$D'_{n,k} = n^k$.
Esempio: Quante sequenze di 3 cifre si possono formare usando le cifre $\{0, 1, \dots, 9\}$, se le ripetizioni sono ammesse?
Qui $n=10$ (le 10 cifre) e $k=3$ (la lunghezza della sequenza).
Numero di sequenze = $D'_{10,3} = 10^3 = 1000$ (da 000 a 999).
Combinazioni: Scegliere Sottoinsiemi (l'Ordine Non Conta)
Una combinazione è una selezione di oggetti da un insieme in cui l'ordine della selezione non ha importanza. Si tratta di contare quanti sottoinsiemi di una certa dimensione si possono formare.
1. Combinazioni Semplici (senza ripetizione di elementi)
Il numero di combinazioni semplici di $n$ oggetti distinti presi a $k$ alla volta (o di classe $k$), indicato con $C_{n,k}$ o, più comunemente, con $\binom{n}{k}$ (leggi "$n$ su $k$"), è il numero di modi di scegliere un sottoinsieme di $k$ elementi da un insieme di $n$ elementi.
$\binom{n}{k} = C_{n,k} = \frac{D_{n,k}}{k!} = \frac{n!}{k!(n-k)!}$ (per $0 \le k \le n$).
Questo simbolo $\binom{n}{k}$ è chiamato **coefficiente binomiale**.
Esempio: Da un gruppo di 5 persone ($n=5$), quanti comitati di 3 persone ($k=3$) si possono formare?
L'ordine non conta (un comitato {Anna, Bruno, Carla} è lo stesso di {Carla, Anna, Bruno}).
Numero di comitati = $\binom{5}{3} = \frac{5!}{3!(5-3)!} = \frac{5!}{3!2!} = \frac{5 \cdot 4}{2 \cdot 1} = 10$.
Proprietà importanti dei coefficienti binomiali:
- $\binom{n}{0} = 1$ (C'è un solo modo di scegliere 0 elementi: prendere l'insieme vuoto).
- $\binom{n}{n} = 1$ (C'è un solo modo di scegliere tutti gli $n$ elementi: prendere l'insieme stesso).
- $\binom{n}{k} = \binom{n}{n-k}$ (Proprietà di simmetria: scegliere $k$ elementi è come scegliere gli $n-k$ da escludere).
- $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (Legge di Stifel/Pascal, alla base del Triangolo di Tartaglia/Pascal).
L'identità $\sum_{i=0}^{n} \binom{n}{i} = 2^n$ afferma che la somma dei numeri di sottoinsiemi di tutte le possibili dimensioni (da 0 a $n$) è uguale al numero totale di sottoinsiemi di un insieme di $n$ elementi, che è $|\mathcal{P}(S)| = 2^n$.
Triangolo di Tartaglia (o di Pascal)
È una disposizione geometrica dei coefficienti binomiali in un triangolo. Ogni numero è la somma dei due numeri direttamente sopra di esso (basato sulla legge di Stifel).
k=0 1 2 3 4 5
n=0: 1
n=1: 1 1
n=2: 1 2 1
n=3: 1 3 3 1
n=4: 1 4 6 4 1
n=5: 1 5 10 10 5 1
L'elemento nella riga $n$ e posizione $k$ (partendo da 0) è $\binom{n}{k}$.
Formula del Binomio di Newton
I coefficienti binomiali appaiono nello sviluppo della potenza di un binomio:
$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$
$(a+b)^3 = \binom{3}{0}a^3b^0 + \binom{3}{1}a^2b^1 + \binom{3}{2}a^1b^2 + \binom{3}{3}a^0b^3 = 1a^3 + 3a^2b + 3ab^2 + 1b^3$.