In matematica, il coefficiente binomiale
(che si legge "
su
") è 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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a91254d9745d2f87c9ad16ffb8155a531af12947)
dove
è il fattoriale di
. Può essere calcolato anche facendo ricorso al triangolo di Tartaglia. Esso fornisce il numero delle combinazioni semplici di
elementi di classe
.
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92b6ae403fa84ec20abaa86a13c5f85005e9f0e3)
è il numero di combinazioni di
elementi presi
alla volta, evitando ripetizioni ma indipendentemente dall'ordine di estrazione.
Il coefficiente binomiale ha le seguenti proprietà:
![{\displaystyle {n \choose 0}={n \choose n}=1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12cf2cba3e33ec660bdff853a511658fcf7b528a)
- Dimostrazione formale:
![{\displaystyle {n \choose 0}={{n!} \over {0!(n-0)!}}={n! \over n!}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/664453227101443ec2dfb934817e1d11f42a8bea)
![{\displaystyle {n \choose n}={{n!} \over {n!(n-n)!}}={n! \over n!}=1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cff2253a571b624d768bf963098e58bdbbc23e8)
- Dimostrazione combinatoria: le combinazioni di
elementi di lunghezza
o
sono evidentemente una sola: rispettivamente l'insieme vuoto o l'intero insieme di
elementi.
![{\displaystyle {n \choose 1}={n \choose n-1}=n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9eda2cd6d9c9a6d675197b2ee5fab6ce2578fe0)
- Dimostrazione formale:
![{\displaystyle {n \choose 1}={{n!} \over {1!(n-1)!}}={{n!} \over {(n-1)![n-(n-1)]!}}={n \choose n-1}=n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13a91db8364bfb634b8958311df1e8de0630d12e)
- Dimostrazione combinatoria: vi sono evidentemente
modi per scegliere un elemento tra
o per tralasciarne uno.
![{\displaystyle {n \choose k}={n \choose n-k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd83be7bb1e592faf5807684c20030276a2644cb)
- Dimostrazione formale:
![{\displaystyle {n \choose k}={{n!} \over {k!(n-k)!}}={{n!} \over {(n-k)![n-(n-k)]!}}={n \choose n-k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5a5047dd729bfa74996bf82da0be2bac480f710)
- Dimostrazione combinatoria: le scelte di
elementi sono in corrispondenza biunivoca con i sottoinsiemi degli
elementi tralasciati.
, ovvero: ![{\displaystyle {n \choose k}={n-1 \choose k}+{n-1 \choose k-1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42b352c9033b1cf100e2672ec4972a54b09fe581)
- (proprietà che permette di costruire i coefficienti binomiali con il triangolo di Tartaglia. Inoltre, tale proprietà può essere utile per dimostrare che
è un numero intero non negativo usando il principio d'induzione su
, con l'ipotesi per cui
appartiene ai numeri interi non negativi per ogni
tale che
, e come tesi che lo stesso valga per
; per
abbiamo che
).
- Dimostrazione formale:
![{\displaystyle {n \choose k+1}+{n \choose k}={{n!} \over {(k+1)!(n-k-1)!}}+{{n!} \over {k!(n-k)!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afe27a4dde030a9081b7f889baf198c1836fa20c)
- considerando il fatto che
, ed allo stesso modo ![{\displaystyle (k+1)!=(k+1)k!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f5dea541ecc5bd06750c634b294c55c8402e3a8)
- 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)!}}=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/898f9e69477dca73f51d1d1954ce3a68d9714c53)
![{\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)!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f7be913d5df90e0930fb1dd11d9c6dd8ff326cf)
- e quindi
![{\displaystyle {n \choose k+1}+{n \choose k}={(n-k+k+1){n!} \over {(k+1)k!(n-k)(n-k-1)!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/936962700b6a894d1c3d1a4c8d926bb3aa00a482)
![{\displaystyle {n \choose k+1}+{n \choose k}={{(n+1)!} \over {(k+1)!(n-k)!}}={n+1 \choose k+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/980257c3b2915b33756349046974ca47ad290f9f)
- ovvero la tesi.
- Dimostrazione combinatoria: Per calcolare il numero di combinazioni semplici di
elementi di lunghezza
, scegliamo uno degli
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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a149518ec911142a8b15b988720f543c7192f3c)
- 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f1624158f68fc920912505d0ffb180e06d2eab7)
- ovvero la tesi.
- Dimostrazione combinatoria:
è il numero dei sottoinsiemi di un insieme di
elementi. Possiamo dividere tali sottoinsiemi in classi, ponendo in ogni classe quelli di una data cardinalità. Poiché i sottoinsiemi di cardinalità
sono proprio
, si ottiene subito la tesi.
- Il teorema binomiale, o binomio di Newton, utilizza il coefficiente binomiale per esprimere lo sviluppo di una potenza
-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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46cc57c00b75fcb39e8c02a0b62401276ac3d9c0)
- Il numero di diagonali di un poligono convesso di
lati può essere espresso secondo la seguente formula: ![{\displaystyle d={n \choose 2}-n={\frac {n(n-3)}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1ac9383d7d6d8b6b7aa930c7c80bac5b66a142f)
- Dato un insieme
, tale che
, si utilizza il coefficiente binomiale per calcolare la cardinalità dell'insieme delle parti di
,
:
![{\displaystyle |{\mathcal {P}}(S)|=\sum _{k=0}^{n}{n \choose k}=2^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e85bd7f095445e39e5f90d6388cc2ac4aca108b3)
- La potenza
-esima di un numero intero
può essere espressa con la sommatoria di tutte le possibili produttorie di
coefficienti binomiali
, con
. 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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f9b79fd1d639d0584ab687433a214432511da88)
Si può estendere il coefficiente binomiale al caso in cui
sia negativo, oppure maggiore di
, ponendo:
oppure ![{\displaystyle k>n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebd425ae2f6622e843ad6430d869bfe40af10bc3)
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à
in uno di cardinalità
(ovvero il numero delle disposizioni semplici di
oggetti di classe
) ed il numero delle permutazioni di
oggetti:
![{\displaystyle {n \choose k}={\frac {(n)_{k}}{k!}}={\frac {n!}{(n-k)!k!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d04b5e3165616a81ed6aa6b41f33e5247d4a5513)
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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edb3a3736d22407c2559886468af80b34566dfcc)
ad esempio,
![{\displaystyle (4{,}5)_{3}=4{,}5\cdot 3{,}5\cdot 2{,}5=39{,}375.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14234509fdfcc8de4729782b1e2f94bda788749b)
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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c0f0495fc1befb4643607fd616a486a00d909d4)
ad esempio:
![{\displaystyle {4{,}5 \choose 3}={\frac {(4{,}5)_{3}}{3!}}={\frac {39{,}375}{6}}=6{,}5625.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/169cd73974508bed2f32badd52201d95cc747489)
Si può notare che per
il coefficiente binomiale equivale alla somma dei primi
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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c865d398bb643fff33bab0b1d31a1c091b5ff679)
- 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.
![Modifica su Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png)
- (EN) binomial coefficients, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
![Modifica su Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png)
- (EN) Opere riguardanti Binomial coefficients, su Open Library, Internet Archive.
![Modifica su Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png)
- (EN) Eric W. Weisstein, Binomial Coefficient, su MathWorld, Wolfram Research.
![Modifica su Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png)
- (EN) Binomial coefficients, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
![Modifica su Wikidata](//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png)