Il Coefficiente Binomiale

Il coefficiente binomiale è un numero naturale che si ottiene a partire da altri due numeri naturali, $n$ e $k$ . Questo coefficiente è molto importante nell'ambito del calcolo combinatorio, in quanto ci permette di calcolare il numero di sottoinsiemi di $k$ elementi che possiamo estrarre da un insieme di $n$ elementi.

In questa lezione vedremo la definizione del coefficiente binomiale, alcune sue proprietà e come calcolarlo.

Definizione di Coefficiente Binomiale

A partire dalla Funzione Fattoriale, possiamo definire il cosiddetto coefficiente binomiale. Questo coefficiente è una formula molto importante nell'ambito del calcolo combinatorio:

Definizione

Il Coefficiente Binomiale

Il Coefficiente Binomiale è una funzione di due numeri naturali $n$ e $k$ , definita come:

n, k \in \mathbb{N} \quad \text{e} \quad 0 \leq k \leq n

\binom{n}{k} = \frac{n!}{k!(n-k)!}

Si legge "n su k".

Supponiamo ad esempio di voler calcolare il coefficiente binomiale $\binom{5}{2}$ . La formula ci dice che:

\binom{5}{2} = \frac{5!}{2!(5-2)!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1 \cdot 3 \cdot 2 \cdot 1} =

= \frac{5 \cdot 4}{2 \cdot 1} = 10

Quindi $\binom{5}{2} = 10$ .

Coefficiente Binomiale per valori particolari

Sfruttando la definizione del coefficiente binomiale e le proprietà della funzione fattoriale, possiamo calcolare alcuni valori particolari del coefficiente binomiale.

Partiamo dal caso $k=0$ :

\binom{n}{0} = \frac{n!}{0!(n-0)!} = \frac{n!}{n!} = 1

Ovvero, per ogni $n \in \mathbb{N}$ , $\binom{n}{0} = 1$ .

Analogamente, per $k=n$ :

\binom{n}{n} = \frac{n!}{n!(n-n)!} = \frac{n!}{n!} = 1

Quindi, per ogni $n \in \mathbb{N}$ , $\binom{n}{n} = 1$ .

Infine, se $k=0$ e $n=0$ abbiamo che:

\binom{0}{0} = \frac{0!}{0!(0-0)!} = \frac{1}{1} = 1

Ricapitolando:

Definizione

Valori particolari del Coefficiente Binomiale

Per ogni $n \in \mathbb{N}$ :

\binom{n}{0} = 1

\binom{n}{n} = 1

\binom{0}{0} = 1

Legge delle Classi Complementari

Un'importante proprietà del coefficiente binomiale è la seguente:

Definizione

Legge delle Classi Complementari

Per ogni $n \in \mathbb{N}$ e $k \in \mathbb{N}$ , tali che $0 \leq k \leq n$ :

\binom{n}{k} = \binom{n}{n-k}

La dimostrazione è abbastanza semplice:

Dimostrazione

Dalla definizione del coefficiente binomiale, abbiamo che:

\binom{n}{k} = \frac{n!}{k!(n-k)!}

Però, possiamo riscrivere $k!$ come:

k! = (n - n + k)! = (n - (n - k))!

Quindi:

\binom{n}{k} = \frac{n!}{(n - (n - k))!(n-k)!}

Ma se poniamo $k' = n - k$ , otteniamo:

\binom{n}{k} = \frac{n!}{k'!(n-k')!} = \binom{n}{n-k}

Vediamo un esempio:

Esempio

Calcoliamo il coefficiente binomiale $\binom{16}{14}$ :

\binom{16}{14} = \frac{16!}{14!(16-14)!} = \frac{16!}{14!2!}

Ma è facile vedere che:

\frac{16!}{14!2!} = \frac{16 \cdot 15}{2 \cdot 1} = 120

Quindi $\binom{16}{14} = 120$ .

Adesso, verifichiamo che:

\binom{16}{14} = \binom{16}{16-14} = \binom{16}{2}

E calcoliamo:

\binom{16}{2} = \frac{16!}{2!(16-2)!} = \frac{16!}{2!14!}

\frac{16!}{2!14!} = \frac{16 \cdot 15}{2 \cdot 1} = 120

Quindi $\binom{16}{2} = 120$ .

Formula Ricorsiva del Coefficiente Binomiale

Così come abbiamo fatto per la funzione fattoriale, possiamo definire una formula ricorsiva per il coefficiente binomiale:

Definizione

Formula Ricorsiva del Coefficiente Binomiale

Per ogni $n \in \mathbb{N}$ e $k \in \mathbb{N}$ , tali che $0 \leq k \leq n$ :

\binom{n}{k + 1} = \binom{n}{k} \cdot \frac{n - k}{k + 1}

Questa formula è molto utile nei casi in cui sappiamo già il valore di un coefficiente binomiale e vogliamo calcolare quello di classe successivo, ossia con $k + 1$ .

La dimostrazione è abbastanza semplice:

Dimostrazione

Dalla definizione del coefficiente binomiale, abbiamo che:

\binom{n}{k} = \frac{n!}{k!(n-k)!}

Applicando la definizione anche a $\binom{n}{k + 1}$ , otteniamo:

\binom{n}{k + 1} = \frac{n!}{(k + 1)!(n - (k + 1))!}

Ma possiamo riscrivere $(k + 1)!$ come:

(k + 1)! = (k + 1) \cdot k!

Mentre $(n - (k + 1))!$ come:

(n - (k + 1))! = \frac{(n-k)!}{(n-k)}

Quindi:

\binom{n}{k + 1} = \frac{n!}{(k + 1) \cdot k! \cdot \frac{(n-k)!}{(n-k)}}

= \frac{n!}{k! \cdot (n-k)!} \cdot \frac{n - k}{k + 1} = \binom{n}{k} \cdot \frac{n - k}{k + 1}

Vediamo un esempio:

Esempio

Sappiamo che il coefficiente binomiale $\binom{8}{3} = 56$ . Calcoliamo $\binom{8}{4}$ :

\binom{8}{4} = \binom{8}{3} \cdot \frac{8 - 3}{3 + 1} = 56 \cdot \frac{5}{4} = 70

Quindi $\binom{8}{4} = 70$ .

In Sintesi

Il coefficiente binomiale è una funzione molto importante nell'ambito del calcolo combinatorio. È definito come:

\binom{n}{k} = \frac{n!}{k!(n-k)!}

E soddisfa alcune proprietà interessanti, come la Legge delle Classi Complementari e la Formula Ricorsiva.

Nelle prossime lezioni vedremo come il coefficiente binomiale sia utilizzato per risolvere problemi di conteggio, come nel caso delle Combinazioni con Ripetizione.

Lezione Precedente Indice del capitolo Lezione Successiva