# Coefficiente binomiale

In matematica, il coefficiente binomiale ${\tbinom {n}{k}}$ (che si legge "$n$ su $k$") è un numero intero non negativo definito dalla seguente formula
    ${\binom {n}{k}}=C(n;k)={\frac {n!}{k!\cdot \left(n-k\right)!}},\qquad n,k\in \mathbb {N} ,\,0\leq k\leq n,$
dove $n!$ è il fattoriale di $n$. Può essere calcolato anche facendo ricorso al triangolo di Tartaglia. Esso fornisce il numero delle combinazioni semplici di $n$ elementi di classe $k$.
Per esempio:
    ${5 \choose 3}={\frac {5!}{3!(5-3)!}}={\frac {5\cdot 4\cdot 3\cdot 2\cdot 1}{3\cdot 2\cdot 1\cdot (2\cdot 1)}}={120 \over 12}=10$
è il numero di combinazioni di $5$ elementi presi $3$ alla volta, evitando ripetizioni ma indipendentemente dall'ordine di estrazione.

## Proprietà

Il coefficiente binomiale ha le seguenti proprietà:
* 1) ${n \choose 0}={n \choose n}=1.$
    Dimostrazione formale:
    ${n \choose 0}={{n!} \over {0!(n-0)!}}={n! \over n!}=1$
    ${n \choose n}={{n!} \over {n!(n-n)!}}={n! \over n!}=1.$
    Dimostrazione combinatoria: le combinazioni di $n$ elementi di lunghezza $0$ o $n$ sono evidentemente una sola: rispettivamente l'insieme vuoto o l'intero insieme di $n$ elementi.
* ${n \choose 1}={n \choose n-1}=n.$
    Dimostrazione formale:
    ${n \choose 1}={{n!} \over {1!(n-1)!}}={{n!} \over {(n-1)![n-(n-1)]!}}={n \choose n-1}=n.$
    Dimostrazione combinatoria: vi sono evidentemente $n$ modi per scegliere un elemento tra $n$ o per tralasciarne uno.
* ${n \choose k}={n \choose n-k}$
    Dimostrazione formale:
    ${n \choose k}={{n!} \over {k!(n-k)!}}={{n!} \over {(n-k)![n-(n-k)]!}}={n \choose n-k}.$
    Dimostrazione combinatoria: le scelte di $k$ elementi sono in corrispondenza biunivoca con i sottoinsiemi degli $n-k$ elementi tralasciati.
* ${n+1 \choose k+1}={n \choose k+1}+{n \choose k}$, ovvero: ${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}.$
    (proprietà che permette di costruire i coefficienti binomiali con il triangolo di Tartaglia. Inoltre, tale proprietà può essere utile per dimostrare che ${n \choose k}$ è un numero intero non negativo usando il principio d'induzione su $n$, con l'ipotesi per cui ${n \choose k}$ appartiene ai numeri interi non negativi per ogni $k\in \mathbb {N}$ tale che $0\leq k\leq n$, e come tesi che lo stesso valga per ${n+1 \choose k}$; per $n=1$ abbiamo che ${1 \choose 0}={1 \choose 1}=1\in \mathbb {N}$).
    Dimostrazione formale:
    ${n \choose k+1}+{n \choose k}={{n!} \over {(k+1)!(n-k-1)!}}+{{n!} \over {k!(n-k)!}}$
    considerando il fatto che
    $(n-k)!=(n-k)(n-k-1)!$, ed allo stesso modo $(k+1)!=(k+1)k!$
    si ha
    ${n \choose k+1}+{n \choose k}={{n!} \over {(k+1)k!(n-k-1)!}}+{{n!} \over {(n-k)k!(n-k-1)!}}=$
    $={(n-k){n!} \over {(k+1)(n-k)k!(n-k-1)!}}+{(k+1){n!} \over {(k+1)(n-k)k!(n-k-1)!}}$
    e quindi
    ${n \choose k+1}+{n \choose k}={(n-k+k+1){n!} \over {(k+1)k!(n-k)(n-k-1)!}}$
    ${n \choose k+1}+{n \choose k}={{(n+1)!} \over {(k+1)!(n-k)!}}={n+1 \choose k+1}$
    ovvero la tesi.
    Dimostrazione combinatoria: Per calcolare il numero di combinazioni semplici di $n+1$ elementi di lunghezza $k+1$, scegliamo uno degli $n+1$ elementi, che chiameremo Pippo, e dividiamo le combinazioni in due classi: quelle che non contengono Pippo e quelle che lo contengono. Le cardinalità delle due classi sono evidentemente date dai due termini del secondo membro della formula che volevamo dimostrare.
* $2^{n}={n \choose 0}+{n \choose 1}+{n \choose 2}+\ldots +{n \choose n-1}+{n \choose n}=\sum _{k=0}^{n}{n \choose k}.$
    Dimostrazione formale:
    partendo dal teorema binomiale abbiamo:
    $2^{n}=(1+1)^{n}=\sum _{k=0}^{n}{n \choose k}1^{(n-k)}1^{k}=\sum _{k=0}^{n}{n \choose k}$
    ovvero la tesi.
    Dimostrazione combinatoria:
    $2^{n}$ è il numero dei sottoinsiemi di un insieme di $n$ elementi. Possiamo dividere tali sottoinsiemi in classi, ponendo in ogni classe quelli di una data cardinalità. Poiché i sottoinsiemi di cardinalità $k$ sono proprio ${n \choose k}$, si ottiene subito la tesi.

## Applicazioni

* Il teorema binomiale, o binomio di Newton, utilizza il coefficiente binomiale per esprimere lo sviluppo di una potenza $n$-esima di un binomio qualsiasi secondo la seguente formula:
    $(a+b)^{n}=\sum _{k=0}^{n}{n \choose k}a^{n-k}b^{k}.$
* Il numero di diagonali di un poligono convesso di $n$ lati può essere espresso secondo la seguente formula: $d={n \choose 2}-n={\frac {n(n-3)}{2}}$
* Dato un insieme $S$, tale che $|S|=n$, si utilizza il coefficiente binomiale per calcolare la cardinalità dell'insieme delle parti di $S$, ${\mathcal {P}}(S)$:
    $|{\mathcal {P}}(S)|=\sum _{k=0}^{n}{n \choose k}=2^{n}.$
* La potenza $n$-esima di un numero intero $x$ può essere espressa con la sommatoria di tutte le possibili produttorie di $x-1$ coefficienti binomiali ${n \choose a}{a \choose b}{b \choose c}\ldots {i \choose j}{j \choose k}{k \choose l}$, con $n\geq a\geq b\geq c\geq \ldots \geq i\geq j\geq k\geq l\geq 0$. Esempio:
    $4^{3}={3 \choose 3}{3 \choose 3}{3 \choose 3}+{3 \choose 3}{3 \choose 3}{3 \choose 2}+{3 \choose 3}{3 \choose 3}{3 \choose 1}+{3 \choose 3}{3 \choose 3}{3 \choose 0}+{3 \choose 3}{3 \choose 2}{2 \choose 2}+\ldots +{3 \choose 1}{1 \choose 1}{1 \choose 0}+{3 \choose 1}{1 \choose 0}{0 \choose 0}+{3 \choose 0}{0 \choose 0}{0 \choose 0}.$

## Estensioni

Si può estendere il coefficiente binomiale al caso in cui $k$ sia negativo, oppure maggiore di $n$, ponendo:
    ${n \choose k}=0,\qquad n,k\in \mathbb {Z} ,n>0,k<0$ oppure $k>n.$
Si può anche estendere il coefficiente ai numeri reali. A tale scopo, può convenire iniziare con l'osservazione che il coefficiente binomiale è anche il rapporto tra il numero delle funzioni iniettive da un insieme di cardinalità $k$ in uno di cardinalità $n$ (ovvero il numero delle disposizioni semplici di $n$ oggetti di classe $k$) ed il numero delle permutazioni di $k$ oggetti:
    ${n \choose k}={\frac {(n)_{k}}{k!}}={\frac {n!}{(n-k)!k!}}.$
Si può porre:
    $(a)_{k}=a(a-1)\cdots (a-k+1)=\prod _{i=0}^{k-1}(a-i),\qquad a\in \mathbb {C} ,k\in \mathbb {Z} ,k\geq 0,$
ad esempio,
    $(4{,}5)_{3}=4{,}5\cdot 3{,}5\cdot 2{,}5=39{,}375.$
Con tale convenzione, si ha:
    ${a \choose k}={\frac {(a)_{k}}{k!}}\qquad a\in \mathbb {C} ;k\in \mathbb {Z} ,k\geq 0,$
ad esempio:
    ${4{,}5 \choose 3}={\frac {(4{,}5)_{3}}{3!}}={\frac {39{,}375}{6}}=6{,}5625.$
Infine, esiste una generalizzazione del coefficiente binomiale che coinvolge un parametro $q$, denominata coefficiente binomiale gaussiano (talvolta semplicemente $q$-binomiale).

## Caso particolare

Si può notare che per $k=2$ il coefficiente binomiale equivale alla somma dei primi $n-1$ numeri naturali:
    ${n \choose 2}={\frac {n!}{(n-2)!2!}}={\frac {n(n-1)(n-2)!}{(n-2)!2}}={\frac {n(n-1)}{2}}=\sum _{i=1}^{n-1}i.$