Coefficiente binomiale

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

${\displaystyle {n \choose 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}$) e può essere calcolato anche facendo ricorso al triangolo di Tartaglia. Alla voce Combinazione è dimostrato che 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.

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

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

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 su coefficiente binomiale

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica