Coefficiente binomiale

Il coefficiente binomiale è definito da

$C(n ; k) = {n \choose k} = \frac{n!}{k! \cdot \left( n - k \right)!}\qquad n,k\in\N; 0\le k\le n$

(dove n! è il fattoriale di 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 n elementi di classe k.

Per esempio:

${5\choose 3}=\frac{5!}{3!(5-3)!}={120\over 12}=10$

è il numero di combinazioni di 5 elementi presi 3 alla volta.

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)

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

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\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)\qquad a\in\R; k\in\Z, k\ge 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\R; k\in\Z, k\ge 0$

ad esempio:

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

Voci correlate

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

Altri progetti

• Commons

• Commons contiene immagini o altri file su Coefficiente binomiale

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