Coefficiente binomiale

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

${\displaystyle {\binom {n}{k}}=C(n;k)={\frac {n!}{k!\cdot \left(n-k\right)!}},\qquad n,k\in \mathbb {N} ,\,0\leq k\leq n,}$

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

Per esempio:

${\displaystyle {5 \choose 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)}}={120 \over 12}=10}$

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

Proprietà

Il coefficiente binomiale ha le seguenti proprietà:

• ${\displaystyle {n \choose 0}={n \choose n}=1.}$

Dimostrazione formale:

${\displaystyle {n \choose 0}={{n!} \over {0!(n-0)!}}={n! \over n!}=1}$

${\displaystyle {n \choose n}={{n!} \over {n!(n-n)!}}={n! \over n!}=1.}$

Dimostrazione combinatoria: le combinazioni di ${\displaystyle n}$ elementi di lunghezza ${\displaystyle 0}$ o ${\displaystyle n}$ sono evidentemente una sola: rispettivamente l'insieme vuoto o l'intero insieme di ${\displaystyle n}$ elementi.

• ${\displaystyle {n \choose 1}={n \choose n-1}=n.}$

Dimostrazione formale:

${\displaystyle {n \choose 1}={{n!} \over {1!(n-1)!}}={{n!} \over {(n-1)![n-(n-1)]!}}={n \choose n-1}=n.}$

Dimostrazione combinatoria: vi sono evidentemente ${\displaystyle n}$ modi per scegliere un elemento tra ${\displaystyle n}$ o per tralasciarne uno.

• ${\displaystyle {n \choose k}={n \choose n-k}}$

Dimostrazione formale:

${\displaystyle {n \choose k}={{n!} \over {k!(n-k)!}}={{n!} \over {(n-k)![n-(n-k)]!}}={n \choose n-k}.}$

Dimostrazione combinatoria: le scelte di ${\displaystyle k}$ elementi sono in corrispondenza biunivoca con i sottoinsiemi degli ${\displaystyle n-k}$ elementi tralasciati.

• ${\displaystyle {n+1 \choose k+1}={n \choose k+1}+{n \choose k}}$, ovvero: ${\displaystyle {n \choose k}={n-1 \choose k}+{n-1 \choose k-1}.}$

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

Dimostrazione formale:

${\displaystyle {n \choose k+1}+{n \choose k}={{n!} \over {(k+1)!(n-k-1)!}}+{{n!} \over {k!(n-k)!}}}$

considerando il fatto che

${\displaystyle (n-k)!=(n-k)(n-k-1)!}$, ed allo stesso modo ${\displaystyle (k+1)!=(k+1)k!}$

si ha

${\displaystyle {n \choose k+1}+{n \choose k}={{n!} \over {(k+1)k!(n-k-1)!}}+{{n!} \over {(n-k)k!(n-k-1)!}}=}$

${\displaystyle ={(n-k){n!} \over {(k+1)(n-k)k!(n-k-1)!}}+{(k+1){n!} \over {(k+1)(n-k)k!(n-k-1)!}}}$

e quindi

${\displaystyle {n \choose k+1}+{n \choose k}={(n-k+k+1){n!} \over {(k+1)k!(n-k)(n-k-1)!}}}$

${\displaystyle {n \choose k+1}+{n \choose k}={{(n+1)!} \over {(k+1)!(n-k)!}}={n+1 \choose k+1}}$

ovvero la tesi.

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

• ${\displaystyle 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}.}$

Dimostrazione formale:

partendo dal teorema binomiale abbiamo:

${\displaystyle 2^{n}=(1+1)^{n}=\sum _{k=0}^{n}{n \choose k}1^{(n-k)}1^{k}=\sum _{k=0}^{n}{n \choose k}}$

ovvero la tesi.

Dimostrazione combinatoria:

${\displaystyle 2^{n}}$ è il numero dei sottoinsiemi di un insieme di ${\displaystyle n}$ elementi. Possiamo dividere tali sottoinsiemi in classi, ponendo in ogni classe quelli di una data cardinalità. Poiché i sottoinsiemi di cardinalità ${\displaystyle k}$ sono proprio ${\displaystyle {n \choose 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 ${\displaystyle n}$-esima di un binomio qualsiasi secondo la seguente formula:

${\displaystyle (a+b)^{n}=\sum _{k=0}^{n}{n \choose k}a^{n-k}b^{k}.}$

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

${\displaystyle |{\mathcal {P}}(S)|=\sum _{k=0}^{n}{n \choose k}=2^{n}.}$

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

${\displaystyle 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}.}$

Estensioni

Si può estendere il coefficiente binomiale al caso che ${\displaystyle k}$ sia negativo, oppure maggiore di ${\displaystyle n}$, ponendo:

${\displaystyle {n \choose k}=0,\qquad n,k\in \mathbb {Z} ,n>0,k<0}$ oppure ${\displaystyle 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à ${\displaystyle k}$ in uno di cardinalità ${\displaystyle n}$ (ovvero il numero delle disposizioni semplici di ${\displaystyle n}$ oggetti di classe ${\displaystyle k}$) ed il numero delle permutazioni di ${\displaystyle k}$ oggetti:

${\displaystyle {n \choose k}={\frac {(n)_{k}}{k!}}={\frac {n!}{(n-k)!k!}}.}$

Si può porre:

${\displaystyle (a)_{k}=a(a-1)\cdots (a-k+1)=\prod _{i=0}^{k-1}(a-i),\qquad a\in \mathbb {C} ,k\in \mathbb {Z} ,k\geq 0,}$

ad esempio,

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

Con tale convenzione, si ha:

${\displaystyle {a \choose k}={\frac {(a)_{k}}{k!}}\qquad a\in \mathbb {C} ;k\in \mathbb {Z} ,k\geq 0,}$

ad esempio:

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

Caso particolare

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

${\displaystyle {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.}$

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

• Coefficiente multinomiale
• Coefficiente binomiale simmetrico
• Teorema binomiale
• Fattoriale
• Calcolo combinatorio, Combinazione, Permutazione
• Probabilità
• Variabile casuale binomiale
• Statistica
• Triangolo di Tartaglia

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.

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

Controllo di autorità	GND (DE) 4145586-1