Coefficiente binomiale

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 gode delle seguenti proprietà:

$(\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})$ o, equivalentemente, $(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) .$

Questa proprietà 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)!

e

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

ossia 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 si ha

2^{n} = (1 + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) 1^{(n - k)} 1^{k} = \sum_{k = 0}^{n} (\binom{n}{k}),

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

\begin{matrix} 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}) . \end{matrix}

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 .

Note

↑ (EN) Successione A000096, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.

Bibliografia

Mauro Cerasoli, Franco Eugeni; Marco Protasi, Elementi di matematica discreta, Bologna, Zanichelli, 1988.
Giorgio Dall'Aglio, Calcolo delle probabilità, Bologna, Zanichelli, 2003.
Sheldon M. Ross, Calcolo delle probabilità, Milano, Apogeo, 2004.
Saunders Mac Lane, Garrett Birkhoff, Algebra, Milano, Mursia 1998

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file sul coefficiente binomiale

Collegamenti esterni

coefficiente binomiale, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.

(EN) binomial coefficients, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

(EN) Opere riguardanti Binomial coefficients, su Open Library, Internet Archive.

(EN) Eric W. Weisstein, Binomial Coefficient, su MathWorld, Wolfram Research.

(EN) Binomial coefficients, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.

Controllo di autorità	GND (DE) 4145586-1

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] (EN) Successione A000096, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.

V · D · M Combinatoria
Orientamento generale	Combinatoria · Storia della combinatoria · Matematica discreta · Sezione 05-XX di MSC
Nozioni introduttive	Permutazioni · Disposizioni · Combinazioni · Coefficienti binomiali · Partizioni di interi · Partizioni di insiemi finiti - Identità combinatorie e biiezioni · Principio dei cassetti
Configurazioni	Quadrati latini · Quadrati magici · Disegni a blocchi · Geometrie finite · Matroidi - Tassellazioni · Polimini
Teoria dei grafi	Alberi · Cammini sui grafi (euleriani, hamiltoniani) · Connessione nei grafi - Grafi planari · Colorazione dei grafi e teorema dei quattro colori) · Ipergrafi · Grafi e gruppi · Digrafo · Flussi su grafi · Passeggiate aleatorie su grafi · Omomorfismo fra grafi · Algoritmi sui grafi
Combinatoria algebrica	Tavola di Young · Funzioni simmetriche - Serie formale di potenze · Funzioni generatrici · Polinomi ortogonali · Azioni di un gruppo su strutture combinatorie - Aspetti combinatorici dell'algebra commutativa
Altre aree	Calcolo umbrale (sequenze polinomiali di tipo binomiale · sequenze di Sheffer) - Combinatoria estremale