Che cos'è una combinazione semplice
Un raggruppamento si definisce combinazione se:- è definito [math] n [/math]il numero degli oggetti
- è definito [math] k [/math]il numero dei posti, in modo che[math] n != k [/math]
- non conta l'ordine con cui gli oggetti sono disposti
Come calcolare il numero di combinazioni di [math] n [/math] oggetti su [math] k [/math] posti senza ripetizioni
Supponiamo che gli
[math] n [/math]
oggetti da combinare siano tutti tra loro distinguibili. Allora per dar luogo a una combinazione procederemo come segue:- In primo luogo creiamo una disposizione di [math] n [/math]oggetti su[math] k [/math]posti senza ripetizioni. Per fare ciò utilizzeremo chiaramente quanto già noto in merito alle disposizioni
- Consideriamo adesso i [math] k [/math]oggetti facenti parte della disposizione prefissata al punto 1. L'unica distinzione tra disposizioni e combinazioni è che nelle ultime non conta l'ordine e dunque dovremo considerare come uguali tutte quelle disposizioni date da una permutazione dei[math] k [/math]elementi di quella prefissata
Per concludere dunque quante combinazioni ci sono in tutto dovremo solo dividere il numero di disposizioni di
[math] n [/math]
oggetti su [math] k [/math]
posti per il numero di permutazioni di [math] k [/math]
oggetti:
[math]C_{n,k} = \frac{D_{n,k}}{P_k} = \frac{n!}{k!(n-k)!} [/math]
Quel che otteniamo è il coefficiente binomiale di
[math] n [/math]
su [math] k [/math]
, che è stato definito proprio a questo scopo. Per le combinazioni valgono perciò tutte le proprietà che sono già note per il coefficiente binomiale.
Come calcolare il numero di combinazioni di [math] n [/math] oggetti su [math] k [/math] posti con ripetizioni
Per trovare questa formula dovremo seguire un ragionamento del tutto diverso, articolato nei seguenti passaggi:
- In primo luogo ordiniamo gli [math] n [/math]oggetti da combinare assegnando loro dei nomi con numeri crescenti, del tipo[math]( e_1, e_2, l\dots, e_n )[/math]. Gli oggetti si possono a priori ordinare in qualsiasi modo vogliamo, quindi non facciamo altro che fissare arbitrariamente un ordinamento
- Osserviamo che dalla Definizione 1 segue che in una combinazione l'ordine in cui compaiono gli oggetti è irrilevante. Conveniamo allora di costruire la combinazione mettendo prima tutte le copie di [math]e_1[/math], poi quelle di[math]e_2[/math]e così via, rispettando l'ordine dato agli oggetti nel punto 1
- Indichiamo ciascuna copia di [math]e_1[/math]che intendiamo usare nella combinazione con un cerchietto; mettiamo una virgola di separazione, poi indichiamo allo stesso modo le copie di[math]e_2[/math]che vogliamo inserire, e procediamo fino alla fine;
- Se non vogliamo inserire copie di un determinato oggetto, non inseriremo cerchietti e metteremo direttamente la nuova virgola di separazione
- In tal modo ricaviamo un codice per indicare le varie combinazioni in maniera univoca. Per esempio, supponendo che sia ( k = 7 ) e ( n = 4 ), le scritture seguenti indicano rispettivamente le combinazioni:
[math]
\begin{pmatrix}
e_1 & e_1 & e_2 & e_3 & e_3 & e_3 & e_4 \\
\hline
e_1 & e_1 & e_3 & e_3 & e_3 & e_3 & e_4 \\
\hline
e_1 & e_1 & e_2 & e_3 & e_3 & e_3 & e_3 \\
\hline
\end{pmatrix}
[/math]
\begin{pmatrix}
e_1 & e_1 & e_2 & e_3 & e_3 & e_3 & e_4 \\
\hline
e_1 & e_1 & e_3 & e_3 & e_3 & e_3 & e_4 \\
\hline
e_1 & e_1 & e_2 & e_3 & e_3 & e_3 & e_3 \\
\hline
\end{pmatrix}
[/math]
- Contare le combinazioni dunque equivalente al contare il numero di diversi ordini di cerchietti e virgole che possono essere formati. Notiamo che il numero di cerchi è sempre [math] k [/math], poichè equivale al numero di posti, mentre il numero di virgole sempre[math] n - 1 [/math], in quanto l'ultimo gruppo di oggetti non richiede una virgola
- Il risultato ricercato è perciò uguale al numero di permutazioni di [math] n + k - 1 [/math]oggetti organizzati in due sottoinsiemi di oggetti uguali, comprendenti rispettivamente[math] k [/math]ed[math] n - 1 [/math]oggetti:
[math]C_{n,k}^r = P_{n+k-1}^r = \frac{(n+k-1)!}{k!(n-k)!} [/math]
Svolgimento di esercizi inerenti alla combinazione
Esempio 1: Quanti sottoinsiemi di 3 elementi esistono di un insieme che ne contiene 9?Questo è il tipico caso nel quale si utilizzano le combinazioni: infatti vogliamo scegliere 3 elementi da 9, ovvero disporre 9 oggetti su 3 posti senza che conti l'ordine. Il risultato si ottiene con la formula precedentemente mostrata, poichè siccome un elemento può apparire una sola volta in ogni insieme non esistono ripetizioni:
[math]C_{9,3} =\frac{9 \cdot 8 \cdot 7 \cdot 6!}{6 \cdot 6!} = \frac{9 \cdot 8 \cdot 7}{6} = 3 \cdot 4 \cdot 7 = 84 [/math]
Esempio 2: Quanti diversi risultati si possono ottenere lanciando contemporaneamente tre dadi a sei facce?
Si osservi che in questo caso ci sono 6 oggetti (i diversi risultati che possono scaturire dal lancio di un singolo dado), 3 posti (i dadi), non conta l'ordine (i dadi cadono in maniera casuale) e ci possono essere ripetizioni (due dadi diversi possono dare lo stesso risultato). Quindi occorre adoperare la formula delle combinazioni con ripetizione:
[math]C_{6,3}^r = \frac{8!}{3!5!} = \frac{8 \cdot 7 \cdot 6 \cdot 5!}{6 \cdot 5!} = 8 \cdot 7 = 56 [/math]
Per ulteriori approfondimenti sulle combinazioni vedi anche qua
