Coefficiente binomiale: differenze tra le versioni

Versione delle 20:10, 13 mar 2007

Versione attuale delle 18:23, 20 giu 2025

(151 versioni intermedie di 82 utenti non mostrate)

Riga 1:

{{NN|matematica|dicembre 2020}}

Il '''coefficiente binomiale''' è definito da

In [[matematica]], il '''coefficiente binomiale''' <math> \tbinom{n}{k} </math> (che si legge "<math>n</math> su <math>k</math>") è un [[numero intero]] non negativo definito dalla seguente formula

:<math> C(n ; k) = {n \choose k} = \frac{n!}{k! \cdot \left( n - k \right)!}</math>

:<math> \binom{n}{k} = C(n ; k) = \frac{n!}{k! \cdot \left( n - k \right)!},\qquad n,k\in\N, \, 0\le k\le n,</math>

(dove n! è il [[n fattoriale|fattoriale]] di n)

edove può<math>n!</math> è il [[fattoriale]] di <math>n</math>. Può essere calcolato anche facendo ricorso al [[triangolo di Tartaglia]]. Esso fornisce il numero delle [[Combinazione#Combinazioni semplici|combinazioni semplici]] di <math>n</math> elementi di classe <math>k</math>.

Per esempio:

:<math>{5\choose 3}=\frac{5!}{3!(5-3)!}=\frac{5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1\cdot(2\cdot1)}={120\over 12}=10 </math>

è il numero di combinazioni di <math>5</math> elementi presi <math>3</math> alla volta, evitando ripetizioni ma indipendentemente dall'ordine di estrazione.

== Proprietà ==

:<math>{5\choose 3}=\frac{5!}{3!(5-3)!}={120\over 12}=10\,</math>

Il coefficiente binomiale gode delle seguenti proprietà:

*1) <math>{n \choose 0} = {n \choose n} = 1.</math>

:Dimostrazione formale:

:<math>{n \choose 0} = {{n!}\over{0!(n-0)!}} = {n! \over n!} = 1</math>

e ha le seguenti proprietà:

* <math>{n \choose 0} = {n \choose n} = 1</math>

:<math>{n \choose n} = {{n!}\over{n!(n-n)!}}= {n! \over n!} = 1.</math>

{{cassetto|titolo=Dimostrazione|testo=

:Dimostrazione combinatoria: le combinazioni di <math>n</math> elementi di lunghezza <math>0</math> o <math>n</math> sono evidentemente una sola: rispettivamente l'insieme vuoto o l'intero insieme di <math>n</math> elementi.

<math>{n \choose 0} = {{n!}\over{0!(n-0)!}} = {n! \over n!} = 1</math>

* <math>{n \choose n1} = {{n!}\over{n!(n-n)!}}= {n! \overchoose n!-1} = 1n.</math>

}}

:Dimostrazione formale:

* <math>{n \choose 1} = {n \choose n-1} = n</math>

:<math>{n \choose 1} = {{n!}\over{1!(n-1)!}} = {{n!}\over{(n-1)![n-(n-1)]!}} = {n \choose n-1} = n.</math>

{{cassetto|titolo=Dimostrazione|testo=

:Dimostrazione combinatoria: vi sono evidentemente <math>n</math> modi per scegliere un elemento tra <math>n</math> o per tralasciarne uno.

<math>{n \choose 1} = {{n!}\over{1!(n-1)!}} = {{n!}\over{(n-1)![n-(n-1)]!}} = {n \choose n-1} = n</math>

}}

* <math>{n \choose k} = {n \choose n-k} </math>

{{cassetto|titolo=:Dimostrazione|testo= formale:

:<math>{n \choose k} = {{n!}\over{k!(n-k)!}} = {{n!}\over{(n-k)![n-(n-k)]!}} = {n \choose n-k} .</math>

}}

:Dimostrazione combinatoria: le scelte di <math>k</math> elementi sono in [[corrispondenza biunivoca]] con i sottoinsiemi degli <math>n-k</math> elementi tralasciati.

* <math>{n+1 \choose k+1} = {n \choose k+1} + {n \choose k} </math> , formula per il [[Teorema binomiale|binomio di Newton]]

* <math>{n+1 \choose k+1} = {n \choose k+1} + {n \choose k} </math>, ovvero: <math>{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.</math>

{{cassetto|titolo=Dimostrazione|testo=

:(proprietà che permette di costruire i coefficienti binomiali con il [[triangolo di Tartaglia]]. Inoltre, tale proprietà può essere utile per dimostrare che <math>{n \choose k}</math> è un [[numero intero]] non negativo usando il [[principio d'induzione]] su <math>n</math>, con l'ipotesi per cui <math>{n \choose k}</math> appartiene ai [[numero intero|numeri interi]] non negativi per ogni <math>k\in\N </math> tale che <math> 0\le k\le n</math>, e come tesi che lo stesso valga per <math>{n+1 \choose k}</math>; per <math>n=1</math> abbiamo che <math>{1 \choose 0} = {1 \choose 1} =1\in\N</math>).

<math>{n \choose k+1} + {n \choose k} = {{n!}\over{(k+1)!(n-k-1)!}}+{{n!}\over{k!(n-k)!}}</math>

:Dimostrazione formale:

considerando il fatto che

<math>(n-k)!=(n-k)(n-k-1)!</math>, ed allo stesso modo <math>(k+1)!=(k+1)k!</math> si ha

<math>{n \choose k+1} + {n \choose k} = {{n!}\over{(k+1)k!(n-k-1)!}}+{{n!}\over{(n-k)k!(n-k-1)!}}</math>

:<math>{n \choose k+1} + {n \choose k} = {{n!}\over{(k+1)!(n-k-1)!}}+{{n!}\over{k!(n-k)!}}</math>

da cui si ottiene

:considerando il fatto che

<math>

{:<math>(n-k){n!}\over{(k+1)=(n-k)k!(n-k-1)!}}+{</math>, ed allo stesso modo <math>(k+1){n!}\over{=(k+1)(n-k)k!(n-k-1)!}}</math>

:si ha

e quindi

:<math>{n \choose k+1} + {n \choose k} = {{n!}\over{(k+1)k!(n-k-1)!}}+{{n!}\over{(n-k)k!(n-k-1)!}} = </math>

:<math>= {(n -k){n!}\choose over{(k+1} + {)(n \choose -k} = {)k!(n-k-1)!}}+{(k+1){n!}\over{(k+1)k!(n-k)k!(n-k-1)!}}</math>

:e quindi

:<math>{n \choose k+1} + {n \choose k} = {{(n-k+k+1){n!}\over{(k+1)k!(n-k)!}} = {(n+1 \choose -k+-1)!}}</math>

:<math>{n \choose k+1} + {n \choose k} = {{(n+1)!}\over{(k+1)!(n-k)!}} = {n+1 \choose k+1}</math>

ovvero la tesi

:ovvero la tesi.

}}

:Dimostrazione combinatoria: Per calcolare il numero di combinazioni semplici di <math>n+1</math> elementi di lunghezza <math>k+1</math>, scegliamo uno degli <math>n+1</math> 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.

* <math>{n+1 \choose k+1} = {k \choose k} + {k+1 \choose k} + {k+2 \choose k} + ... + {n-1 \choose k} + {n \choose k} </math>

* <math>2^n = {n \choose 0} + {n \choose 1} + {n \choose 2} + ... + {n \choose n-1} + {n \choose n} </math>

* <math>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}.</math>

{{cassetto|titolo=:Dimostrazione|testo= formale:

Partendo:partendo dal [[Teoremateorema binomiale]] abbiamo:

:<math> 2^{n}a^{n} =(2a1 + 1)^{n}=(a+a)^n_{} = \sum_{k=0}^n {n \choose k} a1^{(n-k)} a1^{k} = \sum_{k=0}^n {n \choose k} a^{n} </math>

:ovvero la tesi.

Dividendo il primo e l'ultimo termine dell'uguaglianza per <math> a^{n} </math> abbiamo che:

:Dimostrazione combinatoria:

<math> 2^{n}= \sum_{k=0}^n {n \choose k}={n \choose 0} + {n \choose 1} + {n \choose 2} + ... + {n \choose n}</math>

:<math> 2^{n}</math> è il numero dei sottoinsiemi di un insieme di <math>n</math> elementi. Possiamo dividere tali sottoinsiemi in classi, ponendo in ogni classe quelli di una data cardinalità. Poiché i sottoinsiemi di cardinalità <math>k</math> sono proprio <math>{n \choose k}</math>, si ottiene subito la tesi.

}}

=== Applicazioni ===

* Il [[teorema binomiale]], o binomio di Newton, utilizza il coefficiente binomiale per esprimere lo sviluppo di una potenza <math>n</math>-esima di un binomio qualsiasi secondo la seguente formula:

:<math>(a+b)^n = \sum_{k=0}^n {n \choose k}a^{n-k}b^{k}.</math>

* Il numero di [[diagonale|diagonali]] di un poligono convesso di <math>n</math> lati può essere espresso secondo la seguente formula: <math>d={n \choose 2}-n=\frac{n(n - 3)}{2}</math>

* Dato un insieme <math>S</math>, tale che <math>|S|=n</math>, si utilizza il coefficiente binomiale per calcolare la cardinalità dell'[[insieme delle parti]] di <math>S</math>, <math>\mathcal{P}(S)</math>:

:<math>|\mathcal{P}(S)|=\sum_{k=0}^n {n \choose k}=2^n.</math>

*La potenza <math>n</math>-esima di un numero intero <math>x</math> può essere espressa con la [[sommatoria]] di tutte le possibili produttorie di <math>x-1</math> coefficienti binomiali <math>{n \choose a} {a \choose b} {b \choose c} \ldots {i \choose j} {j \choose k} {k \choose l} </math>, con <math>n \ge a \ge b \ge c \ge \ldots \ge i \ge j \ge k \ge l\ge0</math>. Esempio:

:<math>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}.</math>

== Estensioni ==

Il coefficiente binomiale è utilizzato per il calcolo dello sviluppo di un binomio, mediante la [[Teorema binomiale|formula di newton]], ma soprattutto nel calcolo combinatorio. Infatti il numero <math>{n\choose k}\,</math> indica il numero totale di gruppi di <math>k\,</math> elementi che si possono formare partendo da <math>n\,</math> elementi. Per esempio per stabilire quante possibili coppie di rappresentanti di classe si possono avere in una classe di 25 alunni, basta calcolare

Si può estendere il coefficiente binomiale al caso in cui <math>k</math> sia negativo, oppure maggiore di <math>n</math>, ponendo:

:<math>{25\choose 2}={25!\over 2!(25-2)!}=300\,</math>

:<math>{n \choose k}=0,\qquad n,k\in\Z, n>0, k<0</math> oppure <math>k>n.</math>

Si può anche estendere il coefficiente ai [[Numero reale|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à <math>k</math> in uno di cardinalità <math>n</math> (ovvero il numero delle [[Disposizione#Disposizioni semplici|disposizioni semplici]] di <math>n</math> oggetti di classe <math>k</math>) ed il numero delle permutazioni di <math>k</math> oggetti:

:<math>{n \choose k}=\frac{(n)_k}{k!}=\frac{n!}{(n-k)!k!}.</math>

Si può porre:

:<math>(a)_k=a(a-1)\cdots(a-k+1) = \prod_{i=0}^{k-1}(a-i), \qquad a\in\Complex, k\in\Z, k\ge 0,</math>

ad esempio,

:<math>(4{,}5)_3=4{,}5\cdot 3{,}5\cdot 2{,}5=39{,}375.</math>

Con tale convenzione, si ha:

:<math>{a \choose k}=\frac{(a)_k}{k!}\qquad a\in\Complex; k\in\Z, k\ge 0,</math>

ad esempio:

:<math>{4{,}5 \choose 3}=\frac{(4{,}5)_3}{3!}=\frac{39{,}375}{6}=6{,}5625.</math>

Infine, esiste una generalizzazione del coefficiente binomiale che coinvolge un parametro <math>q</math>, denominata [[coefficiente binomiale gaussiano]] (talvolta semplicemente <math>q</math>-binomiale).

== Caso particolare ==

allora ci sono 300 diverse possibilità di abbinamento dei due rappresentanti di classe.

Si può notare che per <math>k=2</math> il coefficiente binomiale equivale alla [[Somma dei numeri naturali|somma dei primi <math>n-1</math> numeri naturali]]:

:<math>{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.</math>

== Bibliografia ==

* {{cita libro|autore=[[Mauro Cerasoli]]|coautori=[[Franco Eugeni]]; [[Marco Protasi]]|titolo=Elementi di matematica discreta|anno=1988|editore=Zanichelli|città=Bologna}}

* {{cita libro|autore=Giorgio Dall'Aglio|titolo=Calcolo delle probabilità|anno=2003|editore=Zanichelli|città=Bologna}}

* {{cita libro|autore=Sheldon M. Ross|titolo=Calcolo delle probabilità|anno=2004|editore=Apogeo|città=Milano}}

* Saunders Mac Lane, Garrett Birkhoff, ''Algebra'', Milano, Mursia 1998

== Voci correlate ==

* [[Coefficiente multinomiale]]

* [[Coefficiente binomiale simmetrico]]

* [[Teorema binomiale]]

* [[Fattoriale]]

* [[Calcolo combinatorio]], [[Combinazione]], [[Permutazione]]

* [[Probabilità]]

* [[Distribuzione binomiale|Variabile casuale binomiale]]

* [[Statistica]]

* [[Triangolo di Tartaglia]]

== Altri progetti ==

{{interprogetto|preposizione=sul}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Combinatoria}}

{{Controllo di autorità}}

{{Portale|matematica}}

[[Categoria:Combinatoria]]

[[Categoria:Polinomi]]

[[Categoria:Funzioni speciali]]

[[Categoria:Successioni a due indici]]