Coefficiente binomiale: differenze tra le versioni

Versione delle 23:26, 3 dic 2007

Versione delle 23:56, 3 dic 2007

Riga 13:

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

{{cassetto|titolo=Dimostrazione formale|testo=

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

}}

{{cassetto|titolo=Dimostrazione combinatoria|testo=

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

}}

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

{{cassetto|titolo=Dimostrazione formale|testo=

<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 combinatoria|testo=

Vi sono evidentemente n modi per sceglier un elemento tra n o per tralasciarne uno

}}

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

{{cassetto|titolo=Dimostrazione formale|testo=

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

}}

{{cassetto|titolo=Dimostrazione combinatoria|testo=

Le scelte di k elementi sono in corrispondenza biunivoca con i sottoinsiemi degli n-k elementi tralasciati}}

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

{{cassetto|titolo=Prima dimostrazioneDimostrazione formale|testo=

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

Riga 59 ⟶ 70:

}}

{{cassetto|titolo= Dimostrazione alternativacombinatoria|testo=

Per calcolare il numero di combinazioni semplici di di n+1 elementi di lunghezza k+1, scegliamo uno dei 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.

}}

* <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+1 \choose k+1} = {kn \choose k0} + {k+1n \choose k1} + {k+2n \choose k2} + ... + {n-1 \choose kn-1} + {n \choose kn} </math>

{{cassetto|titolo=Dimostrazione formale|testo=

Partendo dal [[Teorema binomiale]] abbiamo:

Riga 86 ⟶ 96:

ovvero la tesi.

}}

{{cassetto|titolo=Dimostrazione combinatoria|testo=

<math> 2^{n}</math> è 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 <math> {n \choose k}</math>, si ottiene subito la tesi.

}}