Calcolo Combinatorio - Matefilia.it

Il calcolo combinatorio è quella branca della matematica che studia i modi in cui è possibile raggruppare, ordinare o selezionare elementi da un insieme finito, secondo determinate regole.

In altre parole, risponde a domande del tipo: "In quanti modi posso...?"

A cosa serve?

Il calcolo combinatorio è uno strumento fondamentale in molti ambiti:

Probabilità — per contare i casi favorevoli e i casi possibili.
Crittografia — per valutare il numero di chiavi possibili.
Informatica — per analizzare algoritmi e strutture dati.
Statistica — per progettare esperimenti e campionamenti.
Vita quotidiana — quante targhe automobilistiche si possono formare? Quante password diverse esistono?

Il Fattoriale

Prima di affrontare i raggruppamenti, è utile richiamare il concetto di fattoriale, che compare in quasi tutte le formule del calcolo combinatorio.

Il fattoriale di un numero naturale \(n\) (scritto \(n!\)) è il prodotto di tutti i numeri interi positivi da 1 fino a \(n\):

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

Per convenzione si definisce: \(0! = 1\)

Esempi:

\(3! = 3 \times 2 \times 1 = 6\)
\(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)
\(7! = 5040\)

I raggruppamenti: uno schema riassuntivo

Tutti i raggruppamenti si distinguono in base a due domande fondamentali:

L'ordine conta? — Se sì, parliamo di disposizioni o permutazioni. Se no, di combinazioni.
La ripetizione è ammessa? — Possiamo usare lo stesso elemento più volte?

Le disposizioni semplici di \(n\) oggetti presi \(k\) a \(k\) sono tutti i raggruppamenti ordinati di \(k\) elementi scelti da un insieme di \(n\) elementi distinti, in cui:

L'ordine conta (raggruppamenti diversi per ordine sono considerati diversi).
Ogni elemento può comparire al massimo una volta (senza ripetizione).
Vale necessariamente \(k \le n\).

Come si calcola: la striscia delle caselle

Immaginiamo di avere una striscia con \(k\) caselle da riempire con oggetti scelti da un insieme di \(n\) elementi distinti:

n casella 1

n−1 casella 2

n−2 casella 3

…

n−k+1 casella k

Il ragionamento è il seguente:

Casella 1: possiamo scegliere tra tutti gli \(n\) oggetti → \(n\) scelte possibili
Casella 2: un oggetto è già stato usato → \(n-1\) scelte possibili
Casella 3: due oggetti sono già stati usati → \(n-2\) scelte possibili
\(\dots\)
Casella \(k\): \(k-1\) oggetti sono già stati usati → \(n-(k-1) = n-k+1\) scelte possibili

Per il principio fondamentale del conteggio, il numero totale di modi è il prodotto di tutte le scelte:

\[ D_{n,k} = n \times (n-1) \times (n-2) \times \dots \times (n-k+1) \quad \text{(prodotto di } k \text{ fattori)} \]

Esempio immediato:

\(D_{5,3} = 5 \times 4 \times 3 = 60\) (3 fattori, che partono da 5 e scendono di 1)

Altro modo di scrivere le Disposizioni semplici

Osserviamo che dopo il fattore \(n-k+1\), togliendo 1 si ottiene \(n-k\). Se moltiplichiamo e dividiamo per \((n-k)! = (n-k)(n-k-1) \times \dots \times 1\), otteniamo al numeratore esattamente \(n!\):

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

Quindi la formula compatta delle disposizioni semplici è:

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

Esempio: podio di una gara

In una gara con 8 atleti, in quanti modi diversi si possono assegnare i posti del podio (1°, 2°, 3°)?

Abbiamo \(n = 8\) atleti e vogliamo scegliere \(k = 3\) posti. L'ordine conta (1° ≠ 2° ≠ 3°) e non ci possono essere ripetizioni.

\[ D_{8,3} = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \times 7 \times 6 = 336 \]

Ci sono 336 possibili podi diversi.

Le disposizioni con ripetizione di \(n\) oggetti presi \(k\) a \(k\) sono tutti i raggruppamenti ordinati di \(k\) elementi scelti da un insieme di \(n\) elementi, in cui:

L'ordine conta.
Ogni elemento può comparire più volte (con ripetizione).
\(k\) può essere anche maggiore di \(n\).

Come si calcola: la striscia delle caselle

Immaginiamo di avere una striscia con \(k\) caselle da riempire con oggetti scelti da un insieme di \(n\) elementi. Questa volta, a differenza delle disposizioni semplici, ogni oggetto può essere riutilizzato: dopo aver scelto un oggetto per una casella, esso rimane disponibile per le caselle successive.

n casella 1

n casella 2

n casella 3

…

n casella k

Il ragionamento è il seguente:

Casella 1: possiamo scegliere tra tutti gli \(n\) oggetti → \(n\) scelte possibili
Casella 2: l'oggetto precedente è ancora disponibile → \(n\) scelte possibili
Casella 3: stessa cosa → \(n\) scelte possibili
\(\dots\)
Casella \(k\): ancora \(n\) scelte possibili

Ogni casella ha sempre \(n\) scelte possibili. Per il principio fondamentale del conteggio, il numero totale di modi è:

\[ D_{n,k}^r = \underbrace{n \times n \times n \times \dots \times n}_{k \text{ volte}} = n^k \]

Esempio immediato:

\(D_{5,3}^r = 5^3 = 125\) (3 caselle, ognuna con 5 scelte)

Confrontando con le disposizioni semplici: \(D_{5,3} = 60\). La differenza (125 vs 60) è dovuta proprio alla ripetizione: con essa ci sono molte più possibilità.

Esempio: codice PIN

Quanti codici PIN di 4 cifre (da 0 a 9) si possono formare, ammettendo cifre ripetute?

Abbiamo \(n = 10\) cifre e \(k = 4\) posizioni. L'ordine conta (1234 ≠ 4321) e la ripetizione è ammessa (es. 1122).

\[ D_{10,4}^r = 10^4 = 10.000 \]

Esistono 10.000 possibili PIN diversi.

Le permutazioni semplici di \(n\) oggetti sono tutti i modi di ordinare tutti gli \(n\) elementi di un insieme, in cui:

Si usano tutti gli \(n\) elementi (quindi \(k = n\)).
L'ordine conta.
Ogni elemento compare esattamente una volta.

Le permutazioni semplici sono un caso particolare delle disposizioni semplici con \(k = n\):

\[ P_n = D_{n,n} = n \times (n-1) \times (n-2) \times \dots \times (n-n+1) = n \times (n-1) \times (n-2) \times \dots \times 1 = n! \]

Osservazione: perché si pone per definizione \(0! = 1\)

Usando la formula compatta delle disposizioni semplici con \(k = n\):

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

Affinché questo risultato sia coerente con \(D_{n,n} = n!\), è necessario che \(0! = 1\). Questo è uno dei motivi principali per cui si pone per definizione \(0! = 1\): garantisce che la formula delle disposizioni semplici funzioni correttamente anche nel caso limite in cui si usano tutti gli \(n\) elementi disponibili.

Esempio: anagrammi di una parola senza lettere ripetute

In quanti modi diversi si possono disporre le lettere della parola ROMA?

La parola ha \(n = 4\) lettere tutte distinte. Vogliamo ordinarle tutte.

\[ P_4 = 4! = 4 \times 3 \times 2 \times 1 = 24 \]

Esistono 24 anagrammi diversi di ROMA (tra cui: MORA, AMOR, ARMO, ...).

Le permutazioni con ripetizione si usano quando si vogliono disporre \(n\) oggetti in cui alcuni elementi si ripetono. Se tra gli \(n\) elementi ci sono gruppi di elementi identici di numerosità \(k_1, k_2, \dots, k_m\) (con \(k_1 + k_2 + \dots + k_m = n\)), la formula è:

\[ P_n^{(k_1, k_2, \dots, k_m)} = \frac{n!}{k_1! \cdot k_2! \cdot \dots \cdot k_m!} \]

Si divide per i fattoriali delle molteplicità per eliminare le permutazioni indistinguibili dovute agli elementi uguali.

Esempio: anagrammi di MATEMATICA

Quanti sono gli anagrammi della parola MATEMATICA?

La parola ha \(n = 10\) lettere, con le seguenti ripetizioni:

M appare \(k_1 = 2\) volte
A appare \(k_2 = 3\) volte
T appare \(k_3 = 2\) volte
E, I, C appaiono 1 volta ciascuna

\[ P_{10}^{(2,3,2)} = \frac{10!}{2! \cdot 3! \cdot 2!} = \frac{3.628.800}{2 \cdot 6 \cdot 2} = \frac{3.628.800}{24} = 151.200 \]

Esistono 151.200 anagrammi distinti di MATEMATICA.

Le combinazioni semplici di \(n\) oggetti presi \(k\) a \(k\) sono tutti i raggruppamenti di \(k\) elementi scelti da un insieme di \(n\) elementi, in cui:

L'ordine non conta (due raggruppamenti con gli stessi elementi ma in ordine diverso sono considerati uguali).
Ogni elemento può comparire al massimo una volta.
Vale \(k \le n\).

Come si ottengono le combinazioni dalle disposizioni

Supponiamo di voler contare le terne ordinate che si possono formare con 5 elementi. Queste sono le disposizioni semplici:

\[ D_{5,3} = 5 \times 4 \times 3 = 60 \]

Supponiamo ora di voler contare le terne non ordinate (cioè i gruppi in cui l'ordine non conta) che si possono formare con gli stessi 5 elementi.

Osserviamo che ogni terna non ordinata, ad esempio \(\{a, b, c\}\), dà luogo a esattamente \(3! = 6\) terne ordinate, ottenute permutando \(a\), \(b\) e \(c\) in tutti i modi possibili:

\[ abc, \; acb, \; bac, \; bca, \; cab, \; cba \]

Quindi ogni gruppo non ordinato viene contato \(3!\) volte nelle disposizioni. Per ottenere le combinazioni basta dividere:

\[ C_{5,3} = \frac{D_{5,3}}{3!} = \frac{60}{6} = 10 \]

Generalizzando: ogni gruppo non ordinato di \(k\) elementi genera \(k!\) disposizioni ordinate. Quindi:

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

Il simbolo del coefficiente binomiale

Le combinazioni semplici si indicano comunemente con il simbolo del coefficiente binomiale:

\[ C_{n,k} = \binom{n}{k} \]

che si legge "n su k".

⚠️ Attenzione! Il simbolo \(\binom{n}{k}\) non va confuso con la frazione \(\dfrac{n}{k}\): sono due cose completamente diverse!

Ad esempio: \(\dbinom{5}{3} = 10\), mentre \(\dfrac{5}{3} \approx 1{,}67\).

Proprietà simmetrica del coefficiente binomiale

\[ \binom{n}{k} = \binom{n}{n-k} \]

Ad esempio: \(\binom{10}{3} = \binom{10}{7} = 120\). Scegliere 3 elementi da 10 equivale a "escludere" i restanti 7.

Esempio: commissione scolastica

Da una classe di 20 studenti si deve formare una commissione di 4 persone. In quanti modi è possibile sceglierla?

L'ordine non conta (una commissione \(\{A, B, C, D\}\) è uguale a \(\{D, C, B, A\}\)) e non ci sono ripetizioni.

\[ C_{20,4} = \binom{20}{4} = \frac{20!}{4! \cdot 16!} = \frac{20 \times 19 \times 18 \times 17}{4 \times 3 \times 2 \times 1} = \frac{116.280}{24} = 4.845 \]

Esistono 4.845 commissioni diverse possibili.

Le combinazioni con ripetizione di \(n\) oggetti presi \(k\) a \(k\) sono tutti i raggruppamenti di \(k\) elementi scelti da un insieme di \(n\) tipi di elementi, in cui:

L'ordine non conta.
Ogni elemento può comparire più volte (con ripetizione).
\(k\) può essere anche maggiore di \(n\).

\[ C^r_{n,k} = \binom{n+k-1}{k} = \frac{(n+k-1)!}{k!(n-1)!} \]

Come si ricava questa formula?

Il problema delle combinazioni con ripetizione è equivalente a distribuire \(k\) oggetti identici in \(n\) contenitori distinti. Si può dimostrare che ciò equivale a scegliere \(k\) elementi da un insieme di \(n + k - 1\) elementi senza ripetizione.

Esempio: scegliere le calzine

In un cassetto ci sono paia di calzine di 4 colori diversi: bianco, nero, grigio e blu. Vogliamo sceglierne 6 paia, ammettendo di poter prendere più paia dello stesso colore. In quanti modi diversi possiamo farlo?

L'ordine non conta (non importa in quale sequenza le prendiamo) e la ripetizione è ammessa (possiamo prendere più paia dello stesso colore). Abbiamo \(n = 4\) colori e \(k = 6\) paia da scegliere.

\[ C^r_{4,6} = \binom{4+6-1}{6} = \binom{9}{6} = \frac{9!}{6! \cdot 3!} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = \frac{504}{6} = 84 \]

Esistono 84 modi diversi di scegliere 6 paia di calzine da 4 colori.

Perché non le combinazioni semplici?

Con le combinazioni semplici \(\binom{4}{6}\) non avrebbe senso: non si possono scegliere 6 elementi distinti da un insieme di soli 4 colori! La ripetizione è necessaria proprio perché possiamo prendere più paia dello stesso colore.

Esempio: coppetta di gelato

In una gelateria ci sono 6 gusti disponibili: cioccolato, fragola, limone, pistacchio, vaniglia e nocciola. Vogliamo ordinare una coppetta con 3 palline, potendo scegliere più volte lo stesso gusto. In quanti modi diversi possiamo comporre la coppetta?

L'ordine non conta (una coppetta con cioccolato, fragola e limone è uguale a una con limone, cioccolato e fragola) e la ripetizione è ammessa (possiamo prendere, ad esempio, 3 palline di cioccolato). Abbiamo \(n = 6\) gusti e \(k = 3\) palline da scegliere.

\[ C^r_{6,3} = \binom{6+3-1}{3} = \binom{8}{3} = \frac{8!}{3! \cdot 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56 \]

Esistono 56 coppette diverse possibili.

Qualche esempio di coppetta:

3 gusti tutti diversi, es. cioccolato + fragola + limone
2 gusti uguali + 1 diverso, es. cioccolato + cioccolato + pistacchio
3 gusti tutti uguali, es. vaniglia + vaniglia + vaniglia

Tutte e tre le situazioni sono contemplate dalla formula delle combinazioni con ripetizione, che è proprio questo il suo punto di forza rispetto alle combinazioni semplici.

Il Binomio di Newton fornisce una formula generale per sviluppare la potenza \(n\)-esima di un binomio \((a + b)^n\), utilizzando i coefficienti binomiali.

\[ (a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k \]

Esplicitando i termini:

\[ (a+b)^n = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \binom{n}{2}a^{n-2}b^2 + \dots + \binom{n}{n-1}ab^{n-1} + \binom{n}{n}b^n \]

Il Triangolo di Tartaglia (o di Pascal)

I coefficienti binomiali \(\binom{n}{k}\) si possono leggere direttamente dal Triangolo di Tartaglia: ogni numero è la somma dei due numeri immediatamente sopra di esso.

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

La riga \(n\)-esima contiene i coefficienti dello sviluppo di \((a+b)^n\).

Esempio 1: sviluppo di \((a+b)^4\)

Dalla riga \(n=4\) del triangolo di Tartaglia leggiamo i coefficienti: 1, 4, 6, 4, 1.

\[ (a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4 \]

Esempio 2: sviluppo di \((2x - 1)^3\)

Poniamo \(a = 2x\) e \(b = -1\), con \(n = 3\). I coefficienti per \(n=3\) sono: 1, 3, 3, 1.

\[ (2x-1)^3 = \binom{3}{0}(2x)^3 + \binom{3}{1}(2x)^2(-1) + \binom{3}{2}(2x)(-1)^2 + \binom{3}{3}(-1)^3 \]

\[ = 8x^3 - 3 \cdot 4x^2 + 3 \cdot 2x - 1 = 8x^3 - 12x^2 + 6x - 1 \]

Il termine generale dello sviluppo

Il termine di posto \(k+1\) (con \(k = 0, 1, \dots, n\)) nello sviluppo di \((a+b)^n\) è:

\[ T_{k+1} = \binom{n}{k} a^{n-k} b^k \]

Questa formula è utile quando si vuole trovare un termine specifico senza sviluppare tutto il binomio.

Esempio: trovare il 3° termine di \((x+2)^5\)

Il 3° termine corrisponde a \(k = 2\):

\[ T_3 = \binom{5}{2} x^{5-2} \cdot 2^2 = 10 \cdot x^3 \cdot 4 = 40x^3 \]

Ecco uno schema riassuntivo di tutti i raggruppamenti studiati. Per ogni tipo, la domanda chiave è: l'ordine conta? e la ripetizione è ammessa?

Raggruppamento	Ordine	Ripetizione	Formula
Disposizioni semplici	✓	✗	\( D_{n,k} = \dfrac{n!}{(n-k)!} \)
Disposizioni con ripetizione	✓	✓	\( D^r_{n,k} = n^k \)
Permutazioni semplici	✓	✗	\( P_n = n! \)
Permutazioni con ripetizione	✓	✓	\( P_n^{(k_1,\dots,k_m)} = \dfrac{n!}{k_1! \cdot k_2! \cdots k_m!} \)
Combinazioni semplici	✗	✗	\( C_{n,k} = \dbinom{n}{k} = \dfrac{n!}{k!(n-k)!} \)
Combinazioni con ripetizione	✗	✓	\( C^r_{n,k} = \dbinom{n+k-1}{k} = \dfrac{(n+k-1)!}{k!(n-1)!} \)

Schema decisionale

Di fronte a un problema di calcolo combinatorio, chiediti:

➡️ L'ordine conta?
- Sì → Disposizioni o Permutazioni
- No → Combinazioni
➡️ La ripetizione è ammessa?
- Sì → versione "con ripetizione"
- No → versione "semplice"
➡️ Uso tutti gli elementi disponibili?
- Sì → Permutazioni (caso particolare con \(k = n\))
- No → Disposizioni o Combinazioni