Coefficiente binomiale

Questa voce o sezione sull'argomento matematica è priva o carente di note e riferimenti bibliografici puntuali.

---

Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i suggerimenti del progetto di riferimento.

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 gode delle 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}} o, equivalentemente, ( n k ) = ( n − 1 k ) + ( n − 1 k − 1 ) . {\displaystyle {n \choose k}={n-1 \choose k}+{n-1 \choose k-1}.}

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

e

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

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

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},}

ossia 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 {\begin{aligned}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}.\end{aligned}}}

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.}

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

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 multinomiale
• Coefficiente binomiale simmetrico
• Teorema binomiale
• Fattoriale
• Calcolo combinatorio, Combinazione, Permutazione
• Probabilità
• Variabile casuale binomiale
• Statistica
• Triangolo di Tartaglia

• Wikimedia Commons contiene immagini o altri file sul coefficiente binomiale

• 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

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