Coefficiente binomiale

Dati due interi naturali \( n \) e \( k \), con \( 0 \le k \le n \), il coefficiente binomiale si indica con \( \binom{n}{k} \) che si legge “\( n \) sopra \( k \)” e per definizione è: \[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \] Dove il simbolo "!" indica il fattoriale di un numero naturale e \( 0! = 1 \).

Il coefficiente binomiale è sempre un numero naturale e ha due interpretazioni: algebrica e combinatoria.

Interpretazione algebrica

Il termine "binomiale" deriva dal fatto che, al variare di \( k \) da \( 0 \) a \( n \), i valori di \( \binom{n}{k} \) compaiono come coefficienti numerici nello sviluppo della potenza ennesima di un binomio \( (a+b)^n \).

\[ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k} \]

Dove ogni termine dello sviluppo ha la forma \( \binom{n}{k} a^{n-k} b^{k} \). Organizzando questi valori in forma triangolare, si ottiene il noto triangolo di Tartaglia.

Quest'ultimo è detto teorema binomiale e rappresenta l'interpretazione algebrica del coefficiente binomiale.

Ad esempio, per \( n = 3 \): \[ (a+b)^3 = \binom{3}{0}a^3 + \binom{3}{1}a^2b + \binom{3}{2}ab^2 + \binom{3}{3}b^3 \] Sostituendo i valori numerici:  \[ (a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 \]

Interpretazione combinatoria

Oltre all'interpretazione algebrica, il coefficiente binomiale ha anche un'interpretazione combinatoria perché coincide con il numero combinatorio delle combinazioni semplici $ C_{n,k} $ di classe $ k $ di un insieme di $ n $ elementi.

\[ C_{n,k}  = \binom{n}{k} = \frac{D_{n,k}}{P_k} = \frac{n!}{k!(n-k)!}   \]

In questo caso il coefficiente binomiale rappresenta il numero di modi in cui è possibile scegliere \( k \) elementi da un insieme di \( n \) elementi senza considerare l’ordine.

Ad esempio, scegliere 3 membri di una commissione composta da 10 persone. Complessivamente, ci sono 120 combinazioni possibili (numero combinatorio). \[ \binom{10}{3} = \frac{10!}{3!(10-3)!} = \frac{10!}{3! \cdot 7!}  = 120 \]. Questa interpretazione è fondamentale nella statistica, nelle probabilità e nella teoria dei campioni.

Le proprietà del coefficiente binomiale

Alcune proprietà del coefficiente binomiale utili da ricordare

• Caso $ k=0 $
  Quando si scelgono zero elementi da un insieme di \( n \) elementi, esiste un’unica possibilità: l’insieme vuoto. $$ \begin{pmatrix} n \\ 0 \end{pmatrix} = 1 $$

  Nota. Uso la formula delle combinazioni \[ C_{n,k} = \binom{n}{k} = \frac{n!}{k!(n-k)!} \] Sostituisco \( k = 0 \) \[ \binom{n}{0} = \frac{n!}{0! (n-0)!} = \frac{n!}{0! \cdot n!} \] Assumendo come già definito $ 0!=1 $, segue che il risultato è 1 \[ \binom{n}{0} = \frac{n!}{1! \cdot n!} = \frac{n!}{n!} = 1 \] È importante osservare che questa formula non può essere utilizzata anche per dimostrare $ 0!=1 $ perché si cadrebbe in una definizione circolare. Quindi, $ 0!=1 $ va considerato come già dimostrato altrove.

• Caso $ k=1 $
  Scegliere un solo elemento da un insieme di \( n \) elementi è possibile in \( n \) modi, perché ogni elemento può essere scelto individualmente. $$ \begin{pmatrix} n \\ 1 \end{pmatrix} = n $$

  Nota. Uso la formula delle combinazioni \[ C_{n,k} = \binom{n}{k} = \frac{n!}{k!(n-k)!} \] Sostituisco \( k = 1 \) \[ \binom{n}{1} = \frac{n!}{1! (n-1)!} = \frac{n!}{(n-1)!} \] Sapendo che $ n! = n \cdot (n-1)! $ \[ \binom{n}{1} = \frac{n \cdot (n-1)!}{(n-1)!} = n \]

• Caso $ k=n $
  C’è un unico modo di scegliere tutti e \( n \) gli elementi: selezionare l’intero insieme. $$ \begin{pmatrix} n \\ n \end{pmatrix} = 1 $$

  Nota. Uso la formula delle combinazioni \[ C_{n,k} = \binom{n}{k} = \frac{n!}{k!(n-k)!} \] Sostituisco \( k = n \) \[ \binom{n}{n} = \frac{n!}{n! (n-n)!} \] \[ \binom{n}{n} = \frac{n!}{n! \cdot 0!} \] Assumendo che \( 0! = 1 \) è già definito altrove la formula diventa. \[ \binom{n}{n} = \frac{n!}{n! \cdot 1}  = 1 \]

• Caso $ n=k=0 $
  Quando si scelgono zero elementi da un insieme che contiene zero elementi, esiste un’unica possibilità: l’insieme vuoto. $$ \begin{pmatrix} 0 \\ 0 \end{pmatrix} = 1 $$

  Nota. Utilizzo la formula delle combinazioni \[ C_{n,k} = \binom{n}{k} = \frac{n!}{k!(n-k)!} \] Sostituisco \( n = 0 \), \( k = 0 \) e ottengo: \[ \binom{0}{0} = \frac{0!}{0! \cdot 0!} \] Assumendo che \( 0! = 1 \) è già definito e dimostrato altrove la formula diventa. \[ \binom{0}{0} = \frac{1}{1\cdot 1} = 1 \]

• Relazione ricorsiva (identità di Pascal)
  Le combinazioni di \( k \) elementi tratte da \( n+1 \) oggetti si ottengono distinguendo due casi: quelle che escludono l’ultimo elemento, in numero pari a \( \binom{n}{k} \), e quelle che invece lo includono, in numero pari a \( \binom{n}{k-1} \). I due insiemi sono disgiunti e coprono tutte le possibilità, perciò la loro somma coincide con \( \binom{n+1}{k} \). \[ \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1} \]

  Esempio. Applico l’identità di Pascal al caso \( n = 6 \) e \( k = 3 \) \[ \binom{6}{3} = \binom{5}{3} + \binom{5}{2} \]
  Sostituisco i valori ed effettuo il calcolo \[ \binom{6}{3} = \binom{5}{3} + \binom{5}{2} = 10 + 10 = 20 \]

• Legge delle classi complementari (simmetria)
  Scegliere \( k \) elementi da un insieme di \( n \) elementi è equivalente a scegliere gli \( n-k \) elementi che restano fuori. \[ \binom{n}{k} = \binom{n}{n-k} \]  Per questo motivo i due numeri combinatori coincidono: \[ C_{n,k} = C_{n,n-k} = \binom{n}{k} = \binom{n}{n-k} \] La ragione è immediata dalla definizione stessa \[ \frac{n!}{k!(n-k)!} = \frac{n!}{(n-k)!k!} \]  Questa proprietà, nota anche come simmetria del calcolo combinatorio, è particolarmente utile perché permette semplifica il calcolo combinatorio quando $ k > \frac{n}{2} $
  

  Esempio. Considero il caso \( C_{6,3} \). La legge delle classi complementari afferma che scegliere 3 elementi su 6 è equivalente a scegliere i 3 elementi da scartare, quindi: \[ C_{6,3} = C_{6,3} \] Entrambi i valori coincidono e valgono 20. \[ C_{6,3} = \binom{6}{3} = \frac{6 \cdot 5 \cdot 4}{3!} = \frac{120}{6} = 20 \] \[ C_{6,3} = \binom{6}{3} = \frac{6 \cdot 5 \cdot 4}{3!} = 20 \] Esempio 2. Nel caso \( C_{10,8} \) potrei selezionare $ k=8 $ elementi su $ n=10 $ per calcolare le combinazioni semplici $$ 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 $$ Tuttavia, poiché $ k > \frac{n}{2} $, è molto più semplice calcolare le combinazioni usando la legge delle classi complementari. $$ C_{10,8} = C_{10,2} = \binom{10}{2} = \frac{10 \cdot 9}{2 \cdot 1} = 45 $$ Alla fine il risultato è lo stesso ma, in questo caso, il calcolo è molto più rapido.

• Formula di Stifel
  Questa proprietà è nota come formula di Stifel e afferma che ogni coefficiente binomiale è la somma dei due coefficienti immediatamente sovrastanti nel triangolo di Pascal - Tartaglia. $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$ In pratica, la formula di Stifel semplifica il calcolo dei coefficienti binomiali, perché mi permette di ottenerli ricorsivamente senza dover usare ogni volta la formula con i fattoriali.

  Esempio. Ecco un esempio di applicazione della formula $$ \binom{4}{2} = \binom{3}{1} + \binom{3}{2} = 3 + 3 = 6  $$ Volendo la formula si può anche applicare ricorsivamente sui singoli termini $$ \binom{4}{2} = \binom{3}{1} + \binom{3}{2} $$ $$ \binom{4}{2} = \binom{3}{1} + \underbrace{ \binom{2}{1} + \binom{2}{2}  }_{ \binom{3}{2} } = 3 + 2 + 1 = 6 $$

Differenza tra coefficiente binomiale e numero combinatorio

Dal punto di vista formale \( \binom{n}{k} \) è allo stesso tempo:

• il coefficiente binomiale, cioè il numero che compare nello sviluppo di \( (a+b)^n \) nell'interpretazione algebrica.
• il numero combinatorio, cioè il numero di combinazioni semplici di \( k \) elementi scelti da \( n \) nell'interpretazione combinatoria.

In simboli, sempre lo stesso oggetto:

\[ \binom{n}{k} = \text{coefficiente binomiale} = \text{numero di combinazioni semplici} \]

Quindi, matematicamente coincidono ma l'origine e il significato cambia. Questa differenza deriva dalla duplice interpretazione algebrica e combinatoria del coefficiente.

In altre parole, sono due nomi diversi dello stesso oggetto usato in contesti diversi.

Coefficiente binomiale

Il coefficiente binomiale nasce dall’algebra e indica il coefficiente davanti al termine \( a^{n-k}b^k \) nello sviluppo del binomio:

$$ a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k $$

Proprio da questo deriva l'aggettivo "binomiale".

Numero combinatorio

Il numero combinatorio, invece, nasce nel calcolo combinatorio ed è il numero di sottoinsiemi con \( k \) elementi in un insieme di ( n ) elementi:

\[ \binom{n}{k} = \text{numero delle combinazioni semplici } C(n,k) \]

Qui il focus non è più il polinomio, ma il conteggio delle scelte.

E così via.