Coefficienti binomiali

matteos43

In matematica, il coefficiente binomiale {n \choose k} è un numero intero non negativo definito dalla seguente formula:

{n \choose k} = C_{n,k} = \frac{n!}{k!(n-k)!}


Questo numero è dimostrato corrispondere alle combinazioni semplici di n elementi di classe k, che equivale a dire il numero di sottoinsiemi di k elementi estratti da un insieme di n elementi (non considerando rilevante l’ordine degli insiemi).

Le combinazioni sono parte del calcolo combinatorio, una branda della matematica che studia i modi per raggruppare e/o ordinare secondo date regole gli elementi di un insieme finito di oggetti. Esistono 3 principali categorie di raggrupamento, ognuna delle quali può essere considerata con o senza ripetizioni (ovvero permettendo o meno l’estrazione di uno stesso elemento di un insieme più di una volta). Si possono distinguere infatti:

  • Permutazioni:
    • semplici (senza ripetizioni) P_n
    • con ripetizioni P_n^{k_1,k_2,...,k_r}
  • Disposizioni:
    • semplici (senza ripetizioni) D_{n,k}
    • con ripetizioni D'_{n,k}
  • Combinazioni:
    • semplici (senza ripetizioni) C_{n,k}
    • con ripetizioni C'_{n,k}

Una permutazione di un insieme di oggetti è una presentazione ordinata, cioè una sequenza, dei suoi elementi nella quale ogni oggetto viene presentato una ed una sola volta. Nel caso in cui gli n elementi dell’insieme siano tutti diversi, si parla di permutazioni semplici e si calcolano con la formula:

P_n = n\cdot(n-1)\cdot(n-2)\cdot ... \cdot 1 = n!


Se invece l’insieme contiene delle ripetizioni, occorre utilizzare la formula per le permutazioni con ripetizione, poiché alcuni insiemi risulteranno uguali tra loro. Indicando con k_1, k_2, ... ,k_r il numero di volte che si ripetono r elementi dell’insieme, la formula delle permutazioni sarà la seguente:

P_n^{k_1,k_2,...,k_r} = \frac{n!}{k_1! k_2! \ldots k_r!}


Una disposizione semplice di k elementi da un insieme di n è una collezione ordinata nella quale non si può avere la ripetizione di uno stesso oggetto e si calcola con la seguente formula:

D_{n,k} = \frac{n!}{(n-k)!}


Nel caso in cui invece fosse possibile avere le ripetizioni di uno stesso oggetto, allora bisognerà utilizzare la formula delle disposizioni con ripetizione:

D'_{n,k} = {\underbrace{n \cdot n \cdot \dots \cdot n} \atop {k\mbox{ volte}}} = n^k


Infine, le combinazioni semplici, come già detto, rappresentano il numero di sottoinsiemi non ordinati di k elementi estratti da un insieme di n elementi. La formula può essere ricavata attraverso le permutazioni e le disposizioni e, come si vedrà, coincide esattamente con il coefficiente binomiale. Infatti le combinazioni semplici possono essere viste come il numero di insiemi ordinati di k elementi che si possono ottenere da un insieme di n diviso il numero di permutazione di ogni sottoinsieme, ovvero attraverso il rapporto tra D_{n,k} e P_k:

C_{n,k} = \frac{ D_{n,k} }{ P_k } = \frac{n!}{(n-k)!} \cdot \frac{1}{k!} = \frac{n!}{(n-k)!k!} = {n \choose k}


Una delle proprietà principali del coefficiente binomiale è che permette di ricavare i coefficienti che precedono i termini ottenuti dallo sviluppo di un binomio di potenza p, permettendo di sviluppare il “Triangolo di Tartaglia”, ovvero una sorta di piramide dei coefficienti associati ad ogni esponente.

p = 0                           1     
p = 1                        1     1     
p = 2                     1     2     1     
p = 3                  1     3     3     1     
p = 4               1     4     6     4     1     
p = 5            1     5     10    10    5     1     
p = 6         1     6     15    20    15    6     1     
p = 7      1     7     21    35    35    21    7     1    

Il coefficiente binomiale presenta inoltre diverse proprietà molto utili. La prima riguarda la simmetria del coefficiente binomiale. Infatti:

{n \choose k} = {n \choose (n - k)}


Questa proprietà è vera poichè:

{n \choose k} = {{n!}\over{k!(n-k)!}} = {{n!}\over{(n-k)![n-(n-k)]!}} = {n \choose n-k}


Inoltre, dato che 0! = 1 per definizione, è vera anche le seguente proprietà:

{n \choose 0} = {n \choose n} = 1


Questa proprietà è vera poichè:

{n \choose 0} = {{n!}\over{0!(n-0)!}} = {n! \over n!} = 1

{n \choose n} = {{n!}\over{n!(n-n)!}} = {n! \over n!} = 1


Esistono anche delle proprietà che permettono il calcolo ricorsivo del coefficiente binomiale. Infatti, è possibile scomporre il coefficiente binomiale nel seguente modo:

{n+1 \choose k+1} = {n \choose k+1} + {n \choose k}


In questo modo è possibile ottenere due strutture di ricorrenza per il coefficiente binomiale, ovvero:

{n+1 \choose k+1} = \frac{n+1}{k+1} \cdot {n \choose k}

{n+1 \choose k+1} = \frac{n - k + 2}{k+1} \cdot {n+1 \choose k}


Lascia un commento