Questa voce o sezione sull'argomento matematica è priva o carente di note e riferimenti bibliografici puntuali.

---

Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i suggerimenti del progetto di riferimento.

In matematica, il coefficiente binomiale ${\displaystyle {\tbinom {n}{k))}$ (che si legge "${\displaystyle n}$ su ${\displaystyle k}$") è un numero intero non negativo definito dalla seguente formula

${\displaystyle {\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 ${\displaystyle n!}$ è il fattoriale di ${\displaystyle n}$. Può essere calcolato anche facendo ricorso al triangolo di Tartaglia. Esso fornisce il numero delle combinazioni semplici di ${\displaystyle n}$ elementi di classe ${\displaystyle k}$.

Per esempio:

${\displaystyle {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 ${\displaystyle 5}$ elementi presi ${\displaystyle 3}$ alla volta, evitando ripetizioni ma indipendentemente dall'ordine di estrazione.

Proprietà

Il coefficiente binomiale ha le seguenti proprietà:

• ${\displaystyle {n \choose 0}={n \choose n}=1.}$

Dimostrazione formale:

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

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

Dimostrazione combinatoria: le combinazioni di ${\displaystyle n}$ elementi di lunghezza ${\displaystyle 0}$ o ${\displaystyle n}$ sono evidentemente una sola: rispettivamente l'insieme vuoto o l'intero insieme di ${\displaystyle n}$ elementi.

• ${\displaystyle {n \choose 1}={n \choose n-1}=n.}$

Dimostrazione formale:

${\displaystyle {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 ${\displaystyle n}$ modi per scegliere un elemento tra ${\displaystyle n}$ o per tralasciarne uno.

• ${\displaystyle {n \choose k}={n \choose n-k))$

Dimostrazione formale:

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

Dimostrazione combinatoria: le scelte di ${\displaystyle k}$ elementi sono in corrispondenza biunivoca con i sottoinsiemi degli ${\displaystyle n-k}$ elementi tralasciati.

• ${\displaystyle {n+1 \choose k+1}={n \choose k+1}+{n \choose k))$, ovvero: ${\displaystyle {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 ${\displaystyle {n \choose k))$ è un numero intero non negativo usando il principio d'induzione su ${\displaystyle n}$, con l'ipotesi per cui ${\displaystyle {n \choose k))$ appartiene ai numeri interi non negativi per ogni ${\displaystyle k\in \mathbb {N} }$ tale che ${\displaystyle 0\leq k\leq n}$, e come tesi che lo stesso valga per ${\displaystyle {n+1 \choose k))$; per ${\displaystyle n=1}$ abbiamo che ${\displaystyle {1 \choose 0}={1 \choose 1}=1\in \mathbb {N} }$).

Dimostrazione formale:

${\displaystyle {n \choose k+1}+{n \choose k}=((n!} \over {(k+1)!(n-k-1)!))+((n!} \over {k!(n-k)!))}$

considerando il fatto che

${\displaystyle (n-k)!=(n-k)(n-k-1)!}$, ed allo stesso modo ${\displaystyle (k+1)!=(k+1)k!}$

si ha

${\displaystyle {n \choose k+1}+{n \choose k}=((n!} \over {(k+1)k!(n-k-1)!))+((n!} \over {(n-k)k!(n-k-1)!))=}$

${\displaystyle ={(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

${\displaystyle {n \choose k+1}+{n \choose k}={(n-k+k+1){n!} \over {(k+1)k!(n-k)(n-k-1)!))}$

${\displaystyle {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 ${\displaystyle n+1}$ elementi di lunghezza ${\displaystyle k+1}$, scegliamo uno degli ${\displaystyle 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.

• ${\displaystyle 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:

${\displaystyle 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:

${\displaystyle 2^{n))$ è il numero dei sottoinsiemi di un insieme di ${\displaystyle n}$ elementi. Possiamo dividere tali sottoinsiemi in classi, ponendo in ogni classe quelli di una data cardinalità. Poiché i sottoinsiemi di cardinalità ${\displaystyle k}$ sono proprio ${\displaystyle {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 ${\displaystyle n}$-esima di un binomio qualsiasi secondo la seguente formula:

${\displaystyle (a+b)^{n}=\sum _{k=0}^{n}{n \choose k}a^{n-k}b^{k}.}$

• Il numero di diagonali di un poligono convesso di ${\displaystyle n}$ lati può essere espresso secondo la seguente formula: ${\displaystyle d={n \choose 2}-n={\frac {n(n-3)}{2))}$
• Dato un insieme ${\displaystyle S}$, tale che ${\displaystyle |S|=n}$, si utilizza il coefficiente binomiale per calcolare la cardinalità dell'insieme delle parti di ${\displaystyle S}$, ${\displaystyle {\mathcal {P))(S)}$:

${\displaystyle |{\mathcal {P))(S)|=\sum _{k=0}^{n}{n \choose k}=2^{n}.}$

• La potenza ${\displaystyle n}$-esima di un numero intero ${\displaystyle x}$ può essere espressa con la sommatoria di tutte le possibili produttorie di ${\displaystyle x-1}$ coefficienti binomiali ${\displaystyle {n \choose a}{a \choose b}{b \choose c}\ldots {i \choose j}{j \choose k}{k \choose l))$, con ${\displaystyle n\geq a\geq b\geq c\geq \ldots \geq i\geq j\geq k\geq l\geq 0}$. Esempio:

${\displaystyle 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 che ${\displaystyle k}$ sia negativo, oppure maggiore di ${\displaystyle n}$, ponendo:

${\displaystyle {n \choose k}=0,\qquad n,k\in \mathbb {Z} ,n>0,k<0}$ oppure ${\displaystyle 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à ${\displaystyle k}$ in uno di cardinalità ${\displaystyle n}$ (ovvero il numero delle disposizioni semplici di ${\displaystyle n}$ oggetti di classe ${\displaystyle k}$) ed il numero delle permutazioni di ${\displaystyle k}$ oggetti:

${\displaystyle {n \choose k}={\frac {(n)_{k)){k!))={\frac {n!}{(n-k)!k!)).}$

Si può porre:

${\displaystyle (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,

${\displaystyle (4{,}5)_{3}=4{,}5\cdot 3{,}5\cdot 2{,}5=39{,}375.}$

Con tale convenzione, si ha:

${\displaystyle {a \choose k}={\frac {(a)_{k)){k!))\qquad a\in \mathbb {C} ;k\in \mathbb {Z} ,k\geq 0,}$

ad esempio:

${\displaystyle {4{,}5 \choose 3}={\frac {(4{,}5)_{3)){3!))={\frac {39{,}375}{6))=6{,}5625.}$

Caso particolare

Si può notare che per ${\displaystyle k=2}$ il coefficiente binomiale equivale alla somma dei primi ${\displaystyle n-1}$ numeri naturali:

${\displaystyle {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.}$