Coefficiente binomiale

Da Wikipedia, l'enciclopedia libera.

Il coefficiente binomiale è definito da

C(n ; k) = {n \choose k} = \frac{n!}{k! \cdot \left( n - k \right)!}\qquad n,k\in\Z; 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.

Indice

[modifica] 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}
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
2n è 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.

[modifica] 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

[modifica] Applicazioni

Il coefficiente binomiale è utilizzato per il calcolo dello sviluppo di un binomio, mediante la formula di Newton, ma soprattutto nel calcolo combinatorio. Per esempio per stabilire quante possibili coppie di rappresentanti di classe si possono avere in una classe di 25 alunni, basta calcolare

{25\choose 2}={25!\over 2!(25-2)!}=300\,

Ci sono quindi 300 diverse possibilità di abbinamento dei due rappresentanti di classe.

[modifica] Voci correlate

[modifica] Collegamenti esterni

Estratto da "http://it.wikipedia.org/wiki/Coefficiente_binomiale"
Strumenti personali