Da Wikipedia, l'enciclopedia libera.
In matematica , il coefficiente binomiale
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
(che si legge "
n
{\displaystyle n}
su
k
{\displaystyle k}
") è un numero intero non negativo definito dalla seguente formula
(
n
k
)
=
C
(
n
;
k
)
=
n
!
k
!
⋅
(
n
−
k
)
!
,
n
,
k
∈
N
,
0
≤
k
≤
n
,
{\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
n
!
{\displaystyle n!}
è il fattoriale di
n
{\displaystyle n}
. Può essere calcolato anche facendo ricorso al triangolo di Tartaglia . Esso fornisce il numero delle combinazioni semplici di
n
{\displaystyle n}
elementi di classe
k
{\displaystyle k}
.
Per esempio:
(
5
3
)
=
5
!
3
!
(
5
−
3
)
!
=
5
⋅
4
⋅
3
⋅
2
⋅
1
3
⋅
2
⋅
1
⋅
(
2
⋅
1
)
=
120
12
=
10
{\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
5
{\displaystyle 5}
elementi presi
3
{\displaystyle 3}
alla volta, evitando ripetizioni ma indipendentemente dall'ordine di estrazione.
Il coefficiente binomiale ha le seguenti proprietà:
(
n
0
)
=
(
n
n
)
=
1.
{\displaystyle {n \choose 0}={n \choose n}=1.}
Dimostrazione formale:
(
n
0
)
=
n
!
0
!
(
n
−
0
)
!
=
n
!
n
!
=
1
{\displaystyle {n \choose 0}={{n!} \over {0!(n-0)!}}={n! \over n!}=1}
(
n
n
)
=
n
!
n
!
(
n
−
n
)
!
=
n
!
n
!
=
1.
{\displaystyle {n \choose n}={{n!} \over {n!(n-n)!}}={n! \over n!}=1.}
Dimostrazione combinatoria: le combinazioni di
n
{\displaystyle n}
elementi di lunghezza
0
{\displaystyle 0}
o
n
{\displaystyle n}
sono evidentemente una sola: rispettivamente l'insieme vuoto o l'intero insieme di
n
{\displaystyle n}
elementi.
(
n
1
)
=
(
n
n
−
1
)
=
n
.
{\displaystyle {n \choose 1}={n \choose n-1}=n.}
Dimostrazione formale:
(
n
1
)
=
n
!
1
!
(
n
−
1
)
!
=
n
!
(
n
−
1
)
!
[
n
−
(
n
−
1
)
]
!
=
(
n
n
−
1
)
=
n
.
{\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
n
{\displaystyle n}
modi per scegliere un elemento tra
n
{\displaystyle n}
o per tralasciarne uno.
(
n
k
)
=
(
n
n
−
k
)
{\displaystyle {n \choose k}={n \choose n-k}}
Dimostrazione formale:
(
n
k
)
=
n
!
k
!
(
n
−
k
)
!
=
n
!
(
n
−
k
)
!
[
n
−
(
n
−
k
)
]
!
=
(
n
n
−
k
)
.
{\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
k
{\displaystyle k}
elementi sono in corrispondenza biunivoca con i sottoinsiemi degli
n
−
k
{\displaystyle n-k}
elementi tralasciati.
(
n
+
1
k
+
1
)
=
(
n
k
+
1
)
+
(
n
k
)
{\displaystyle {n+1 \choose k+1}={n \choose k+1}+{n \choose k}}
, ovvero:
(
n
k
)
=
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
.
{\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
(
n
k
)
{\displaystyle {n \choose k}}
è un numero intero non negativo usando il principio d'induzione su
n
{\displaystyle n}
, con l'ipotesi per cui
(
n
k
)
{\displaystyle {n \choose k}}
appartiene ai numeri interi non negativi per ogni
k
∈
N
{\displaystyle k\in \mathbb {N} }
tale che
0
≤
k
≤
n
{\displaystyle 0\leq k\leq n}
, e come tesi che lo stesso valga per
(
n
+
1
k
)
{\displaystyle {n+1 \choose k}}
; per
n
=
1
{\displaystyle n=1}
abbiamo che
(
1
0
)
=
(
1
1
)
=
1
∈
N
{\displaystyle {1 \choose 0}={1 \choose 1}=1\in \mathbb {N} }
).
Dimostrazione formale:
(
n
k
+
1
)
+
(
n
k
)
=
n
!
(
k
+
1
)
!
(
n
−
k
−
1
)
!
+
n
!
k
!
(
n
−
k
)
!
{\displaystyle {n \choose k+1}+{n \choose k}={{n!} \over {(k+1)!(n-k-1)!}}+{{n!} \over {k!(n-k)!}}}
considerando il fatto che
(
n
−
k
)
!
=
(
n
−
k
)
(
n
−
k
−
1
)
!
{\displaystyle (n-k)!=(n-k)(n-k-1)!}
, ed allo stesso modo
(
k
+
1
)
!
=
(
k
+
1
)
k
!
{\displaystyle (k+1)!=(k+1)k!}
si ha
(
n
k
+
1
)
+
(
n
k
)
=
n
!
(
k
+
1
)
k
!
(
n
−
k
−
1
)
!
+
n
!
(
n
−
k
)
k
!
(
n
−
k
−
1
)
!
=
{\displaystyle {n \choose k+1}+{n \choose k}={{n!} \over {(k+1)k!(n-k-1)!}}+{{n!} \over {(n-k)k!(n-k-1)!}}=}
=
(
n
−
k
)
n
!
(
k
+
1
)
(
n
−
k
)
k
!
(
n
−
k
−
1
)
!
+
(
k
+
1
)
n
!
(
k
+
1
)
(
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
(
n
k
+
1
)
+
(
n
k
)
=
(
n
−
k
+
k
+
1
)
n
!
(
k
+
1
)
k
!
(
n
−
k
)
(
n
−
k
−
1
)
!
{\displaystyle {n \choose k+1}+{n \choose k}={(n-k+k+1){n!} \over {(k+1)k!(n-k)(n-k-1)!}}}
(
n
k
+
1
)
+
(
n
k
)
=
(
n
+
1
)
!
(
k
+
1
)
!
(
n
−
k
)
!
=
(
n
+
1
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
n
+
1
{\displaystyle n+1}
elementi di lunghezza
k
+
1
{\displaystyle k+1}
, scegliamo uno degli
n
+
1
{\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.
2
n
=
(
n
0
)
+
(
n
1
)
+
(
n
2
)
+
…
+
(
n
n
−
1
)
+
(
n
n
)
=
∑
k
=
0
n
(
n
k
)
.
{\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:
2
n
=
(
1
+
1
)
n
=
∑
k
=
0
n
(
n
k
)
1
(
n
−
k
)
1
k
=
∑
k
=
0
n
(
n
k
)
{\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:
2
n
{\displaystyle 2^{n}}
è il numero dei sottoinsiemi di un insieme di
n
{\displaystyle n}
elementi. Possiamo dividere tali sottoinsiemi in classi, ponendo in ogni classe quelli di una data cardinalità. Poiché i sottoinsiemi di cardinalità
k
{\displaystyle k}
sono proprio
(
n
k
)
{\displaystyle {n \choose k}}
, si ottiene subito la tesi.
Il teorema binomiale , o binomio di Newton, utilizza il coefficiente binomiale per esprimere lo sviluppo di una potenza
n
{\displaystyle n}
-esima di un binomio qualsiasi secondo la seguente formula:
(
a
+
b
)
n
=
∑
k
=
0
n
(
n
k
)
a
n
−
k
b
k
.
{\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
n
{\displaystyle n}
lati può essere espresso secondo la seguente formula:
d
=
(
n
2
)
−
n
=
n
(
n
−
3
)
2
{\displaystyle d={n \choose 2}-n={\frac {n(n-3)}{2}}}
Dato un insieme
S
{\displaystyle S}
, tale che
|
S
|
=
n
{\displaystyle |S|=n}
, si utilizza il coefficiente binomiale per calcolare la cardinalità dell'insieme delle parti di
S
{\displaystyle S}
,
P
(
S
)
{\displaystyle {\mathcal {P}}(S)}
:
|
P
(
S
)
|
=
∑
k
=
0
n
(
n
k
)
=
2
n
.
{\displaystyle |{\mathcal {P}}(S)|=\sum _{k=0}^{n}{n \choose k}=2^{n}.}
La potenza
n
{\displaystyle n}
-esima di un numero intero
x
{\displaystyle x}
può essere espressa con la sommatoria di tutte le possibili produttorie di
x
−
1
{\displaystyle x-1}
coefficienti binomiali
(
n
a
)
(
a
b
)
(
b
c
)
…
(
i
j
)
(
j
k
)
(
k
l
)
{\displaystyle {n \choose a}{a \choose b}{b \choose c}\ldots {i \choose j}{j \choose k}{k \choose l}}
, con
n
≥
a
≥
b
≥
c
≥
…
≥
i
≥
j
≥
k
≥
l
≥
0
{\displaystyle n\geq a\geq b\geq c\geq \ldots \geq i\geq j\geq k\geq l\geq 0}
. Esempio:
4
3
=
(
3
3
)
(
3
3
)
(
3
3
)
+
(
3
3
)
(
3
3
)
(
3
2
)
+
(
3
3
)
(
3
3
)
(
3
1
)
+
(
3
3
)
(
3
3
)
(
3
0
)
+
(
3
3
)
(
3
2
)
(
2
2
)
+
…
+
(
3
1
)
(
1
1
)
(
1
0
)
+
(
3
1
)
(
1
0
)
(
0
0
)
+
(
3
0
)
(
0
0
)
(
0
0
)
.
{\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}.}
Si può estendere il coefficiente binomiale al caso in cui
k
{\displaystyle k}
sia negativo, oppure maggiore di
n
{\displaystyle n}
, ponendo:
(
n
k
)
=
0
,
n
,
k
∈
Z
,
n
>
0
,
k
<
0
{\displaystyle {n \choose k}=0,\qquad n,k\in \mathbb {Z} ,n>0,k<0}
oppure
k
>
n
.
{\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à
k
{\displaystyle k}
in uno di cardinalità
n
{\displaystyle n}
(ovvero il numero delle disposizioni semplici di
n
{\displaystyle n}
oggetti di classe
k
{\displaystyle k}
) ed il numero delle permutazioni di
k
{\displaystyle k}
oggetti:
(
n
k
)
=
(
n
)
k
k
!
=
n
!
(
n
−
k
)
!
k
!
.
{\displaystyle {n \choose k}={\frac {(n)_{k}}{k!}}={\frac {n!}{(n-k)!k!}}.}
Si può porre:
(
a
)
k
=
a
(
a
−
1
)
⋯
(
a
−
k
+
1
)
=
∏
i
=
0
k
−
1
(
a
−
i
)
,
a
∈
C
,
k
∈
Z
,
k
≥
0
,
{\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,
(
4
,
5
)
3
=
4
,
5
⋅
3
,
5
⋅
2
,
5
=
39,375.
{\displaystyle (4{,}5)_{3}=4{,}5\cdot 3{,}5\cdot 2{,}5=39{,}375.}
Con tale convenzione, si ha:
(
a
k
)
=
(
a
)
k
k
!
a
∈
C
;
k
∈
Z
,
k
≥
0
,
{\displaystyle {a \choose k}={\frac {(a)_{k}}{k!}}\qquad a\in \mathbb {C} ;k\in \mathbb {Z} ,k\geq 0,}
ad esempio:
(
4
,
5
3
)
=
(
4
,
5
)
3
3
!
=
39,375
6
=
6,562
5.
{\displaystyle {4{,}5 \choose 3}={\frac {(4{,}5)_{3}}{3!}}={\frac {39{,}375}{6}}=6{,}5625.}
Si può notare che per
k
=
2
{\displaystyle k=2}
il coefficiente binomiale equivale alla somma dei primi
n
−
1
{\displaystyle n-1}
numeri naturali :
(
n
2
)
=
n
!
(
n
−
2
)
!
2
!
=
n
(
n
−
1
)
(
n
−
2
)
!
(
n
−
2
)
!
2
=
n
(
n
−
1
)
2
=
∑
i
=
1
n
−
1
i
.
{\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.}
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
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.