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à:

• ${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 che $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.$

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.$

Bibliografia

• Mauro Cerasoli, Franco Eugeni; Marco Protasi, Elementi di matematica discreta, Bologna, Zanichelli, 1988.
• Giorgio Dall'Aglio, Calcolo delle probabilità, Bologna, Zanichelli, 2003.
• Sheldon M. Ross, Calcolo delle probabilità, Milano, Apogeo, 2004.
• Saunders Mac Lane, Garrett Birkhoff, Algebra, Milano, Mursia 1998

Voci correlate

• Coefficiente multinomiale
• Coefficiente binomiale simmetrico
• Teorema binomiale
• Fattoriale
• Calcolo combinatorio, Combinazione, Permutazione
• Probabilità
• Variabile casuale binomiale
• Statistica
• Triangolo di Tartaglia

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul coefficiente binomiale

Collegamenti esterni

• coefficiente binomiale, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) binomial coefficients, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Opere riguardanti Binomial coefficients, su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Binomial Coefficient, su MathWorld, Wolfram Research.
• (EN) Binomial coefficients, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.

Controllo di autorità	GND (DE) 4145586-1