|
:<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à ==
Il coefficiente binomiale ha le 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>
:<math>{n \choose n} = {{n!}\over{n!(n-n)!}}= {n! \over n!} = 1.</math>
: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 1} = {n \choose n-1} = n.</math>
:Dimostrazione formale:
:<math>{n \choose 1} = {{n!}\over{1!(n-1)!}} = {{n!}\over{(n-1)![n-(n-1)]!}} = {n \choose n-1} = n.</math>
:Dimostrazione combinatoria: vi sono evidentemente <math>n</math> modi per scegliere un elemento tra <math>n</math> o per tralasciarne uno.
* <math>{n \choose k} = {n \choose n-k} </math>
:Dimostrazione 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>, ovvero: <math>{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.</math>
:(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>).
:Dimostrazione formale:
:<math>{n \choose k+1} + {n \choose k} = {{n!}\over{(k+1)!(n-k-1)!}}+{{n!}\over{k!(n-k)!}}</math>
: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-k){n!}\over{(k+1)(n-k)k!(n-k-1)!}}+{(k+1){n!}\over{(k+1)(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-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.
: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>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>
:Dimostrazione formale:
:partendo dal [[teorema binomiale]] abbiamo:
:<math> 2^n =(1 + 1)^n = \sum_{k=0}^n {n \choose k} 1^{(n-k)} 1^{k} = \sum_{k=0}^n {n \choose k}</math>
:ovvero la tesi.
:Dimostrazione combinatoria:
:<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 ==
| 