Coefficiente binomiale

Template:NN In matematica, il coefficiente binomiale $(\binom{n}{k})$ (che si legge " $n$ su $k$ ") è un numero intero non negativo definito dalla seguente formula

(\binom{n}{k}) = C (n; k) = \frac{n!}{k! \cdot (n - k)!}, n, k \in ℕ, 0 \leq k \leq n,

dove $n!$ è il fattoriale di $n$ . Può essere calcolato anche facendo ricorso al triangolo di Tartaglia. Esso fornisce il numero delle combinazioni semplici di $n$ elementi di classe $k$ .

Per esempio:

(\binom{5}{3}) = \frac{5!}{3! (5 - 3)!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1 \cdot (2 \cdot 1)} = \frac{120}{12} = 10

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

Proprietà

Il coefficiente binomiale ha le seguenti proprietà:

1) $(\binom{n}{0}) = (\binom{n}{n}) = 1 .$

Dimostrazione formale:

(\binom{n}{0}) = \frac{n!}{0! (n - 0)!} = \frac{n!}{n!} = 1

(\binom{n}{n}) = \frac{n!}{n! (n - n)!} = \frac{n!}{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.

$(\binom{n}{1}) = (\binom{n}{n - 1}) = n .$

Dimostrazione formale:

(\binom{n}{1}) = \frac{n!}{1! (n - 1)!} = \frac{n!}{(n - 1)! [n - (n - 1)]!} = (\binom{n}{n - 1}) = n .

Dimostrazione combinatoria: vi sono evidentemente

n

modi per scegliere un elemento tra

n

o per tralasciarne uno.

$(\binom{n}{k}) = (\binom{n}{n - k})$

Dimostrazione formale:

(\binom{n}{k}) = \frac{n!}{k! (n - k)!} = \frac{n!}{(n - k)! [n - (n - k)]!} = (\binom{n}{n - k}) .

Dimostrazione combinatoria: le scelte di

k

elementi sono in corrispondenza biunivoca con i sottoinsiemi degli

n - k

elementi tralasciati.

$(\binom{n + 1}{k + 1}) = (\binom{n}{k + 1}) + (\binom{n}{k})$ , ovvero: $(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) .$

(proprietà che permette di costruire i coefficienti binomiali con il triangolo di Tartaglia. Inoltre, tale proprietà può essere utile per dimostrare che

(\binom{n}{k})

è un numero intero non negativo usando il principio d'induzione su

n

, con l'ipotesi per cui

(\binom{n}{k})

appartiene ai numeri interi non negativi per ogni

k \in ℕ

tale che

0 \leq k \leq n

, e come tesi che lo stesso valga per

(\binom{n + 1}{k})

; per

n = 1

abbiamo che

(\binom{1}{0}) = (\binom{1}{1}) = 1 \in ℕ

).

Dimostrazione formale:

(\binom{n}{k + 1}) + (\binom{n}{k}) = \frac{n!}{(k + 1)! (n - k - 1)!} + \frac{n!}{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

(\binom{n}{k + 1}) + (\binom{n}{k}) = \frac{n!}{(k + 1) k! (n - k - 1)!} + \frac{n!}{(n - k) k! (n - k - 1)!} =

= \frac{(n - k) n!}{(k + 1) (n - k) k! (n - k - 1)!} + \frac{(k + 1) n!}{(k + 1) (n - k) k! (n - k - 1)!}

e quindi

(\binom{n}{k + 1}) + (\binom{n}{k}) = \frac{(n - k + k + 1) n!}{(k + 1) k! (n - k) (n - k - 1)!}

(\binom{n}{k + 1}) + (\binom{n}{k}) = \frac{(n + 1)!}{(k + 1)! (n - k)!} = (\binom{n + 1}{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} = (\binom{n}{0}) + (\binom{n}{1}) + (\binom{n}{2}) + \dots + (\binom{n}{n - 1}) + (\binom{n}{n}) = \sum_{k = 0}^{n} (\binom{n}{k}) .$

Dimostrazione formale:

partendo dal teorema binomiale abbiamo:

2^{n} = (1 + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) 1^{(n - k)} 1^{k} = \sum_{k = 0}^{n} (\binom{n}{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

(\binom{n}{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} (\binom{n}{k}) a^{n - k} b^{k} .

Il numero di diagonali di un poligono convesso di $n$ lati può essere espresso secondo la seguente formula: $d = (\binom{n}{2}) - n = \frac{n (n - 3)}{2}$
Dato un insieme $S$ , tale che $| S | = n$ , si utilizza il coefficiente binomiale per calcolare la cardinalità dell'insieme delle parti di $S$ , $𝒫 (S)$ :

| 𝒫 (S) | = \sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n} .

La potenza $n$ -esima di un numero intero $x$ può essere espressa con la sommatoria di tutte le possibili produttorie di $x - 1$ coefficienti binomiali $(\binom{n}{a}) (\binom{a}{b}) (\binom{b}{c}) \dots (\binom{i}{j}) (\binom{j}{k}) (\binom{k}{l})$ , con $n \geq a \geq b \geq c \geq \dots \geq i \geq j \geq k \geq l \geq 0$ . Esempio:

4^{3} = (\binom{3}{3}) (\binom{3}{3}) (\binom{3}{3}) + (\binom{3}{3}) (\binom{3}{3}) (\binom{3}{2}) + (\binom{3}{3}) (\binom{3}{3}) (\binom{3}{1}) + (\binom{3}{3}) (\binom{3}{3}) (\binom{3}{0}) + (\binom{3}{3}) (\binom{3}{2}) (\binom{2}{2}) + \dots + (\binom{3}{1}) (\binom{1}{1}) (\binom{1}{0}) + (\binom{3}{1}) (\binom{1}{0}) (\binom{0}{0}) + (\binom{3}{0}) (\binom{0}{0}) (\binom{0}{0}) .

Estensioni

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

(\binom{n}{k}) = 0, n, k \in ℤ, 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:

(\binom{n}{k}) = \frac{(n)_{k}}{k!} = \frac{n!}{(n - k)! k!} .

Si può porre:

(a)_{k} = a (a - 1) \dots (a - k + 1) = \prod_{i = 0}^{k - 1} (a - i), a \in ℂ, k \in ℤ, k \geq 0,

ad esempio,

(4, 5)_{3} = 4, 5 \cdot 3, 5 \cdot 2, 5 = 39, 375 .

Con tale convenzione, si ha:

(\binom{a}{k}) = \frac{(a)_{k}}{k!} a \in ℂ; k \in ℤ, k \geq 0,

ad esempio:

(\binom{4, 5}{3}) = \frac{(4, 5)_{3}}{3!} = \frac{39, 375}{6} = 6, 5625 .

Infine, esiste una generalizzazione del coefficiente binomiale che coinvolge un parametro $q$ , denominata coefficiente binomiale gaussiano (talvolta semplicemente $q$ -binomiale).

Caso particolare

Si può notare che per $k = 2$ il coefficiente binomiale equivale alla somma dei primi $n - 1$ numeri naturali:

(\binom{n}{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 .

Bibliografia

Template:Cita libro
Template:Cita libro
Template:Cita libro
Saunders Mac Lane, Garrett Birkhoff, Algebra, Milano, Mursia 1998

Voci correlate

Altri progetti

Template:Interprogetto

Collegamenti esterni

Template:Collegamenti esterni

Template:Combinatoria Template:Controllo di autorità Template:Portale

Coefficiente binomiale

Indice

Proprietà

Applicazioni

Estensioni

Caso particolare

Bibliografia

Voci correlate

Altri progetti

Collegamenti esterni

Menu di navigazione

Coefficiente binomiale

Proprietà

Applicazioni

Estensioni

Caso particolare

Bibliografia

Voci correlate

Altri progetti

Collegamenti esterni

Menu di navigazione

Ricerca