Combinazioni

Una combinazione è un sottoinsieme di k elementi estratti da un insieme di n elementi. $$ \begin{pmatrix} n \\ k \end{pmatrix} $$

Se la combinazione è composta da k elementi, è detta combinazione di classe k.

Essendo un insieme, in una combinazione l'ordine degli elementi non è importante.

Esistono due tipi di combinazioni: semplici e con ripetizione.

Le combinazioni semplici (senza ripetizioni)

Le combinazioni semplici di \( n \) elementi distinti di classe \( k \) sono tutti i gruppi di \( k \) elementi scelti fra gli \( n \) in cui ogni elemento compare una sola volta e l’ordine non ha importanza. Il numero delle combinazioni semplici è $$ C_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix} = \frac{D_{n,k}}{P_k}  $$ Dove \( k \) è un intero positivo compreso tra \( 0 < k < n \)

In altre parole, una combinazione semplice non ha elementi ripetuti al suo interno. In ogni combinazione ogni elemento compare non più di una volta.

Da un insieme di $ n $ elementi si possono ottenere $ C_{n,k} $ combinazioni di classe $ k $

Il numero dei gruppi che posso ottenere è detto numero combinatorio.

$$ C_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix} = \frac{D_{n,k}}{P_k} =  \frac{n \cdot (n-1) \cdot ... \cdot (n-k+1)}{k!} $$

Per calcolare il numero combinatorio di una combinazione semplice di n oggetti di classe k, si divide il numero delle disposizioni semplici $ D_{n,k} $ per il numero delle permutazioni degli stessi $ k $ elementi, cioé $ P(k)=k! $,

In questo modo si eliminano tutte le sequenze che contengono gli stessi elementi ma in ordine diverso.

Nota. Il numero combinatorio può essere ottenuto anche usando questa formula alternativa, detta legge dei tre fattoriali perché composta da tre numeri fattoriali. $$ C_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{k!(n-k)!} $$ Questa formula si ottiene sapendo che le disposizioni semplici possono essere scritte in forma più compatta come $ D_{n,k} = \frac{n!}{(n-k)!} $. Sostituendo questa identità nella formula generale delle combinazioni semplici si ottiene: $$ C_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix} = \frac{D(n,k)}{P_k} =  \frac{ \frac{n!}{(n-k)!} }{k!} = \frac{n!}{k!(n-k)!} $$

Un esempio

Ho un insieme con le prime tre lettere dell'alfabeto

$$ I = \{ A,B,C \} $$

Voglio trovare le combinazioni di classe 2 semplici, ossia i raggruppamenti possibili delle lettere prese a coppia.

$$ n=3 \\ k=2 $$

Applico la formula per conoscere il numero delle combinazioni semplici di classe 2 che posso ottenere (numero combinatorio).

$$ C_{3,2} = \binom{3}{2} = \frac{D_{3,2}}{P_2} $$

Le disposizioni sono $ D_{3,2} = 3 \cdot 2 = 6 $ mentre le permutazioni sono $ P_2 = 2! = 2 $

$$ C_{3,2} = \binom{3}{2} = \frac{6}{2} = 3 $$

Quindi, le combinazioni semplici possibili di classe $ k = 2 $ sono tre.

• (A,B)
• (A,C)
• (B,C)

Come si può vedere, ogni combinazione semplice è composta da due elementi, non ci sono elementi ripetuti e l'ordine non conta.

Nelle combinazioni l'ordine degli elementi non è importante. Pertanto, scrivere (A,B) o (B,A) indica la stessa combinazione

Nota. Avrei ottenuto lo stesso numero combinatorio anche usando la formula alternativa indicando $ n=3 $ e $ k=2 $ $$ C_{3,2} =  \frac{ \frac{n!}{(n-k)!} }{k!} = \frac{3!}{2!(3-2)!} = \frac{6}{2} = 3 $$ Il risultato finale è lo stesso.

Esempio 2

Ora considero un insieme di \( n = 5 \) elementi, ad esempio le prime cinque lettere dell'alfabeto.

$$ I = \{ A,B,C,D,E \} $$

Voglio formare tutte le combinazioni semplici di classe \( k = 3 \).

Calcolo il numero combinatorio:

$$ C_{5,3} = \binom{5}{3} = \frac{D_{5,3}}{P_3} $$

Le disposizioni sono $ D_{5,3} = 5 \cdot 4 \cdot 3 = 60 $ mentre le permutazioni sono $ P_3 = 3 \cdot 2 \cdot 1 = 6 $

$$ C_{5,3} = \binom{5}{3} = \frac{60}{6} = 10 $$

In questo caso ci sono 10 combinazioni di tre elementi senza ripetizioni. Le elenco tutte:

• (A,B,C)
• (A,B,D)
• (A,B,E)
• (A,C,D)
• (A,C,E)
• (A,D,E)
• (B,C,D)
• (B,C,E)
• (B,D,E)
• (C,D,E)

Questi sono tutti i gruppi da tre elementi che posso formare scegliendo dal set iniziale di cinque elementi.

In ogni gruppo non ci sono elementi ripetuti e l'ordine non conta.

Le combinazioni con ripetizione

Le combinazioni con ripetizione di \( n \) elementi distinti, prese in gruppi di classe \( k \), sono tutti i gruppi di \( k \) elementi scelti da un insieme di ( n ) elementi, in cui l’ordine non conta e ogni elemento può essere utilizzato più volte. Il numero delle combinazioni con ripetizione è dato dalla formula: $$ C'_{n,k} = \begin{pmatrix} n+k-1 \\ k \end{pmatrix} = \frac{(n+k-1)!}{k!(n-1)!} $$ Il parametro ( k ) può essere qualsiasi intero non negativo, cioè $ k \ge 0 $

A differenza delle combinazioni senza ripetizione, non è richiesto che \( k \le n \), perché gli elementi possono comparire più volte nello stesso gruppo.

Il numero delle combinazioni con ripetizione C' eguaglia le combinazioni semplici C(n+k-1, k).

Un esempio

Ho un insieme con tre lettere

$$ I = \{ A,B,C \} $$

Devo calcolare le combinazioni di classe 2 con ripetizione

$$ n=3 \\ k=2 $$

Detto in altri termini, i raggruppamenti a coppia delle lettere.

In ogni coppia può esserci anche due volte la stessa lettera.

$$ C'_{3,2} =  \frac{(n+k-1)!}{k!(n-1)!} = \frac{(3+2-1)!}{2!(3-1)!} = \frac{4!}{2!2!} = \frac{24}{4} = 6 $$

Le combinazioni possibili sono sei.

• (A,A)
• (A,B)
• (A,C)
• (B,B)
• (B,C)
• (C,C)

In questo caso ogni gruppo è composto da due elementi dell'insieme {A,B,C}, l'ordine non conta ma possono esserci gli stessi elementi ripetuti. Ad esempio, la combinazione (A,A) contiene due volte l'elemento A.

Esempio 2

Prendo in considerazione lo stesso insieme con tre lettere dell'esempio precedente.

$$ I = \{ A,B,C \} $$

Questa volta, però, voglio calcolare le combinazioni di classe 4 con ripetizione

$$ n=3 \\ k=4 $$

In altre parole, voglio ottenere i possibili raggruppamenti delle 3 lettere in gruppi di 4 elementi, ammettendo anche la ripetizione delle stesse lettere.

$$ C'_{3,4} =  \frac{(n+k-1)!}{k!(n-1)!} = \frac{(3+4-1)!}{4!(3-1)!} = \frac{6!}{4!2!} $$

$$ C'_{3,4}  = \frac{6 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(4 \cdot 3 \cdot 2 \cdot 1) \cdot (2 \cdot 1)} = \frac{720}{48} = 15 $$

Le combinazioni possibili sono sei.

• (A,A,A,A)
• (A,A,A,B)
• (A,A,A,C)
• (A,A,B,B)
• (A,A,B,C)
• (A,A,C,C)
• (A,B,B,B)
• (A,B,B,C)
• (A,B,C,C)
• (A,C,C,C)
• (B,B,B,B)
• (B,B,B,C)
• (B,B,C,C)
• (B,C,C,C)
• (C,C,C,C)

Ogni gruppo è formato da quattro elementi scelti dall’insieme {A, B, C}, senza considerare l’ordine e ammettendo la ripetizione degli stessi elementi. Ad esempio, nella combinazione (A, A, A, B) l’elemento A compare tre volte.

Qual è la differenza tra le combinazioni con ripetizione e le disposizioni con ripetizione? Nelle disposizioni con ripetizione l’ordine degli elementi conta, quindi sequenze come (A, B, A) e (A, A, B) sono considerate diverse. Nelle combinazioni con ripetizione, invece, l’ordine non conta, quindi gruppi che differiscono solo per la disposizione degli elementi rappresentano la stessa combinazione. In questo caso (A, B, A) e (A, A, B) indicano la stessa combinazione.

Le proprietà delle combinazioni

Ci sono importanti proprietà delle combinazioni da tenere a mente

• Scelta vuota
  C’è un solo modo di scegliere zero elementi da un insieme di $ n $ elementi, cioè non scegliere nulla. $$ \begin{pmatrix} n \\ 0 \end{pmatrix} = 1 $$
• Scelta singola
  Scegliere un solo elemento tra $ n $ è possibile in $ n $ modi, uno per ciascun elemento. $$ \begin{pmatrix} n \\ 1 \end{pmatrix} = n $$
• Scelta totale
  C’è un solo modo di scegliere tutti e $ n $ gli elementi, cioè prendere l’intero insieme. $$ \begin{pmatrix} n \\ n \end{pmatrix} = 1 $$
• Identità di Pascal
  Le combinazioni di \( k \) elementi prese da \( n+1 \) oggetti si ottengono sommando quelle che non includono l’ultimo elemento \( \binom{n}{k} \) e quelle che invece lo includono \( \binom{n}{k-1} \). Questi due insiemi sono disgiunti e coprono tutte le possibilità, quindi la loro somma dà \( \binom{n+1}{k} \). $$ \begin{pmatrix} n+1 \\ k \end{pmatrix} = \begin{pmatrix} n \\ k \end{pmatrix} + \begin{pmatrix} n \\ k-1 \end{pmatrix} $$

  Esempio. Applico l'identità di Pascal al caso $ n=5 $ e $ k=2 $ $$ \begin{pmatrix} 5+1 \\ 2 \end{pmatrix} = \begin{pmatrix} 5 \\ 2 \end{pmatrix} + \begin{pmatrix} 5 \\ 2-1 \end{pmatrix} $$ Sostituisco i valori ed effettuo il calcolo $$ \begin{pmatrix} 6 \\ 2 \end{pmatrix} = \begin{pmatrix} 5 \\ 2 \end{pmatrix} + \begin{pmatrix} 5 \\ 1 \end{pmatrix} $$ $$ \begin{pmatrix} 6 \\ 2 \end{pmatrix} = 10 + 5 =15 $$

• Legge delle classi complementari
  Scegliere \( k \) elementi fra \( n \) è equivalente a scartarne \( n-k \), i due numeri combinatori coincidono. $$ C_{n,k} = C_{n,n-k} = \binom{n}{k} = \binom{n}{n-k} $$ Questa legge è anche detta simmetria del calcolo combinatario ed è molto utile perché permette di semplificare il calcolo quando $ k > \frac{n}{2} $
  

  Esempio. Nel caso \( C_{5,3} \), la legge delle classi complementari dice che scegliere 3 elementi su 5 è equivalente a sceglierne i 2 rimanenti da scartare, quindi: $$ C_{5,3} = C_{5,2} $$ Infatti entrambi valgono 10. $$ C_{5,3} = \binom{5}{3} = \frac{5 \cdot 4 \cdot 3}{3!} = \frac{60}{6} = 10 $$ $$ C_{5,2} = \binom{5}{2} = \frac{5 \cdot 4}{2!} = \frac{20}{2} = 10 $$ Esempio 2. Nel caso \( C_{10,8} \) devo selezionare $ k=8 $ elementi su $ n=10 $, le combinazioni semplici sono $$ C_{10,8} = \binom{10}{8} = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3}{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 45 $$ Poiché $ k > \frac{n}{2} $, è molto più facile fare il calcolo tramite la legge delle classi complementari. $$ C_{10,8} = C_{10,2} = \binom{10}{2} = \frac{10 \cdot 9}{2 \cdot 1} = 45 $$ Il risultato finale è ovviamente lo stesso.

I coefficienti binomiali

I termini n e k di una combinazione sono anche detti coefficienti binomiali perché la combinazione C(n,k) è usata nello sviluppo della potenza di un binomio

$$ (a+b)^n = \sum_{k=0}{n} \begin{pmatrix} n \\ k \end{pmatrix} a^{n-k}b^k $$

Esempio. Devo sviluppare il quadrato n=2 di un binomio (a+b) $$ (a+b)^2 = \begin{pmatrix} 2 \\ 0 \end{pmatrix} a^{2-0}b^0 + \begin{pmatrix} 2 \\ 1 \end{pmatrix} a^{2-1}b^1 + \begin{pmatrix} 2 \\ 2 \end{pmatrix} a^{2-2}b^2 $$ $$ (a+b)^2 = \begin{pmatrix} 2 \\ 0 \end{pmatrix} a^{2} + \begin{pmatrix} 2 \\ 1 \end{pmatrix} ab + \begin{pmatrix} 2 \\ 2 \end{pmatrix} b^2 $$ Calcolo i coefficienti binomiali ossia le combinazioni $$ (a+b)^2 = \frac{2!}{0!(2-0)!} \cdot a^{2} + \frac{2!}{1!(2-1)!} \cdot ab + \frac{2!}{2!(2-2)!} \cdot b^2 $$ $$ (a+b)^2 = \frac{2!}{0! \cdot 2!} \cdot a^{2} + \frac{2!}{1! \cdot 1!} \cdot ab + \frac{2!}{2! \cdot 0!} \cdot b^2 $$ Sapendo che 0! = 1 per convenzione, 1! = 1 e 2!=2·1=2 $$ (a+b)^2 = \frac{2}{1 \cdot 2} \cdot a^{2} + \frac{2}{1 \cdot 1} \cdot ab + \frac{2}{2 \cdot 1} \cdot b^2 $$ $$ (a+b)^2 = \frac{2}{2} \cdot a^{2} + \frac{2}{1} \cdot ab + \frac{2}{2} \cdot b^2 $$ $$ (a+b)^2 = 1 \cdot a^{2} + 2 \cdot ab + 1 \cdot b^2 $$ $$ (a+b)^2 = a^{2} + 2 ab + b^2 $$ Il risultato è il quadrato del binomio. Con lo stesso procedimento si può sviluppare qualsiasi altra potenza ennesima del binomio.

E così via