Calcolo combinatorio
Il calcolo combinatorio serve a contare in modo efficiente il numero di possibili configurazioni di oggetti, senza doverle elencare una a una.
È alla base della probabilità, della statistica e di molti algoritmi informatici.
Indice
1. Principi fondamentali del conteggio
- Principio della moltiplicazione: se un evento può avvenire in \( m \) modi e un altro in \( n \), allora l’insieme degli eventi avviene in \( m \cdot n \) modi.
- Principio dell’addizione: se due eventi sono alternativi, il numero totale di modi è la somma delle possibilità.
2. Permutazioni
Senza ripetizione:
\[
P(n) = n!
\]
Con ripetizione:
\[
\frac{n!}{k_1! \cdot k_2! \cdots k_r!}
\]
3. Disposizioni
Disposizioni semplici di \( n \) oggetti presi a \( k \) a \( k \):
\[
D_{n,k} = \frac{n!}{(n-k)!}
\]
Con ripetizione:
\[
D_{n,k}^{(r)} = n^k
\]
4. Combinazioni
Senza ripetizione:
\[
C_{n,k} = \binom{n}{k} = \frac{n!}{k!(n-k)!}
\]
Con ripetizione:
\[
C_{n+k-1,k} = \binom{n+k-1}{k}
\]
5. Coefficiente binomiale
Il numero \( \binom{n}{k} \) indica quante combinazioni di \( k \) elementi si possono scegliere da un insieme di \( n \).
Triangolo di Pascal: ogni numero è la somma dei due sopra.
Formula del binomio di Newton:
\[
(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k
\]
6. Esempi svolti
Esempio 1 – Permutazioni semplici
\[
P(5) = 5! = 120
\]
Esempio 2 – Disposizioni semplici
\[
D_{6,3} = \frac{6!}{3!} = 120
\]
Esempio 3 – Combinazioni
\[
C_{7,3} = \binom{7}{3} = \frac{7!}{3! \cdot 4!} = 35
\]
Esempio 4 – Permutazioni con ripetizioni
\[
\text{PAROLE: “ANNA” } \Rightarrow \frac{4!}{2! \cdot 2!} = 6
\]
7. Esercizi proposti
- (Facile)
- Quante permutazioni si possono fare con 4 lettere distinte?
- Calcola \( \binom{8}{5} \)
- (Medio)
- In quanti modi si possono disporre 3 oggetti su 5 posti?
- Quante combinazioni di 2 elementi da un insieme di 6?
- (Avanzato)
- Quante parole (anche senza senso) si possono formare con le lettere della parola “STATISTICA”?
- Dimostra la formula del binomio di Newton per \( n = 3 \)
Link utili
🔗 Approfondimenti interattivi