Matefilia - Calcolo Combinatorio: Teoria ed Esempi Svolti

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

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

CALCOLO COMBINATORIO

A cosa serve?

Esempio immediato:

Esempio: podio di una gara

Esempio immediato:

Esempio: codice PIN

Esempio: anagrammi di una parola senza lettere ripetute

Esempio: anagrammi di MATEMATICA

Esempio: commissione scolastica

Esempio: scegliere le calzine

Esempio: coppetta di gelato

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

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

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