Calcolo Combinatorio - Versione DSA

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?

🟢 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: le domande chiave

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 \(n\) elementi distinti, in cui:

✅ L'ordine conta
✅ Ogni elemento può comparire al massimo una volta
✅ 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 passo per passo:

🔹 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 già usati → \(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)}

Formula compatta

Moltiplicando e dividendo per \((n-k)!\), otteniamo al numeratore \(n!\):

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°)?

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

D_{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 \(n\), in cui:

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

Come si calcola: la striscia delle caselle

Questa volta 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

Ogni casella ha sempre \(n\) scelte possibili, quindi:

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

Esempio: codice PIN

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

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

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 \dots \times 1 = n!

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

Usando la formula compatta 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\).

Esempio: anagrammi di ROMA

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

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

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

✅ Esistono 24 anagrammi diversi di ROMA.

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!}

💡 Perché si divide per i fattoriali?

Dividere per i fattoriali degli elementi ripetuti serve ad eliminare le permutazioni che sarebbero identiche tra loro, perché gli elementi ripetuti sono indistinguibili.

Esempio: anagrammi di MATEMATICA

Quanti sono gli anagrammi della parola MATEMATICA?

La parola ha \(n = 10\) lettere.
Lettere ripetute:
- 'M' si ripete \(k_1 = 2\) volte
- 'A' si ripete \(k_2 = 3\) volte
- 'T' si ripete \(k_3 = 2\) volte

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 \(n\), in cui:

✅ L'ordine non conta
✅ Ogni elemento può comparire al massimo una volta
✅ Vale \(k \le n\)

Come si ottengono dalle disposizioni

Supponiamo di voler contare le terne ordinate con 5 elementi → sono le disposizioni \(D_{5,3} = 60\).

Supponiamo ora di voler contare le terne non ordinate. Ogni terna non ordinata, ad esempio \(\{a, b, c\}\), dà luogo a esattamente \(3! = 6\) terne ordinate:

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

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

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:

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

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

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 → combinazioni semplici.
Abbiamo \(n = 20\) studenti e \(k = 4\) posti.

C_{20,4} = \binom{20}{4} = \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 \(n\) tipi, in cui:

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

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

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, potendo prendere più paia dello stesso colore. In quanti modi diversi possiamo farlo?

L'ordine non conta e la ripetizione è ammessa → combinazioni con ripetizione.
\(n = 4\) colori (oggetti), \(k = 6\) paia (classe).

C^r_{4,6} = \binom{9}{6} = \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.

Esempio: coppetta di gelato

In una gelateria ci sono 6 gusti disponibili. Vogliamo ordinare una coppetta con 3 palline, potendo scegliere più volte lo stesso gusto. In quanti modi diversi possiamo comporla?

L'ordine non conta e la ripetizione è ammessa → combinazioni con ripetizione.
\(n = 6\) gusti (oggetti), \(k = 3\) palline (classe).

C^r_{6,3} = \binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56

✅ Esistono 56 coppette diverse possibili.

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

Il Triangolo di Tartaglia

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

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

Dalla riga \(n=4\) del triangolo 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\). Coefficienti per \(n=3\): 1, 3, 3, 1.

\[ (2x-1)^3 = (2x)^3 - 3(2x)^2 + 3(2x) - 1 = 8x^3 - 12x^2 + 6x - 1 \]

Il termine generale dello sviluppo

Il termine di posto \(k+1\) nello sviluppo di \((a+b)^n\) è:

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

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

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

T_3 = \binom{5}{2} x^{3} \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?

👉 Scorri orizzontalmente per vedere tutta la tabella.

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! \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

➡️ 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