Il numero di k-combinazioni di un dato insieme S di n elementi è spesso indicato nei testi di combinatoria elementare con C ( n , k ) {\displaystyle C(n,k)}
, o da una variante come C k n {\displaystyle C_{k}^{n}}
, n C k {\displaystyle {}_{n}C_{k}}
, n C k {\displaystyle {}^{n}C_{k}
, C n , k {\displaystyle C_{n,k}
o anche C n k {\displaystyle C_{n}^{k}}
(quest’ultima forma era standard nei testi francesi, rumeni, russi, cinesi e polacchi). Lo stesso numero tuttavia si presenta in molti altri contesti matematici, dove è indicato con ( n k ) {displaystyle {\tbinom {n}{k}}}
(spesso letto come “n sceglie k”); in particolare si presenta come un coefficiente nella formula binomiale, da cui il suo nome coefficiente binomiale. Si può definire ( n k ) {displaystyle {tbinom {n}{k}}
per tutti i numeri naturali k in una volta sola mediante la relazione ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}=somma _{k\geq 0}{binom {n}{k}}X^{k},
da cui si evince che
( n 0 ) = ( n n ) = 1 ,
e inoltre,
( n k ) = 0
e inoltre,
( n k ) = 0 {displaystyle {\binom {n}{k}=0}
per k > n.
Per vedere che questi coefficienti contano k-combinazioni da S, si può prima considerare una collezione di n variabili distinte Xs etichettate dagli elementi s di S, ed espandere il prodotto su tutti gli elementi di S:
∏ s ∈ S ( 1 + X s ) ; {displaystyle \prod _{s\in S}(1+X_{s});}
ha 2n termini distinti corrispondenti a tutti i sottoinsiemi di S, ogni sottoinsieme dà il prodotto delle corrispondenti variabili Xs. Ora, ponendo tutti gli Xs uguali alla variabile non etichettata X, in modo che il prodotto diventi (1 + X)n, il termine per ogni k-combinazione di S diventa Xk, in modo che il coefficiente di quella potenza nel risultato sia uguale al numero di tali k-combinazioni.
I coefficienti del binomio possono essere calcolati esplicitamente in vari modi. Per ottenerli tutti per le espansioni fino a (1 + X)n, si può usare (oltre ai casi base già dati) la relazione di ricorsione
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) , {
per 0 < k < n, che segue da (1 + X)n = (1 + X)n – 1(1 + X); questo porta alla costruzione del triangolo di Pascal.
Per determinare un singolo coefficiente binomiale, è più pratico usare la formula
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k ! {\displaystyle {\binom {n}{k}}={frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}
.
Il numeratore dà il numero di k-permutazioni di n, cioè, di sequenze di k elementi distinti di S, mentre il denominatore dà il numero di tali k-permutazioni che danno la stessa k-combinazione quando si ignora l’ordine.
Quando k supera n/2, la formula precedente contiene fattori comuni al numeratore e al denominatore, e annullandoli si ottiene la relazione
( n k ) = ( n n – k ) , {displaystyle {\binom {n}{k}}={\binom {n}{n-k},}
per 0 ≤ k ≤ n. Questo esprime una simmetria che è evidente dalla formula binomiale, e può anche essere compreso in termini di k-combinazioni prendendo il complemento di tale combinazione, che è una (n – k)-combinazione.
Finalmente c’è una formula che esibisce questa simmetria direttamente, e ha il merito di essere facile da ricordare:
( n k ) = n ! k ! ( n – k ) ! , {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!},}
dove n! indica il fattoriale di n. Si ottiene dalla formula precedente moltiplicando denominatore e numeratore per (n – k)!quindi è certamente computazionalmente meno efficiente di quella formula.
L’ultima formula può essere compresa direttamente, considerando le n! permutazioni di tutti gli elementi di S. Ogni tale permutazione dà una k-combinazione selezionando i suoi primi k elementi. Ci sono molte selezioni duplicate: qualsiasi permutazione combinata dei primi k elementi tra loro, e degli ultimi (n – k) elementi tra loro produce la stessa combinazione; questo spiega la divisione nella formula.
Dalle formule precedenti seguono le relazioni tra i numeri adiacenti nel triangolo di Pascal in tutte e tre le direzioni:
( n k ) = { ( n k – 1 ) n – k + 1 k se k > 0 ( n – 1 k ) n n – k se k < n ( n – 1 k – 1 ) n k se n , k > 0 {displaystyle {binom {n}{k}={begin{casi}{binom {n}{k-1}}{frac {n-k+1}{k}}&quadro {text{if }}k>0{binom {n-1}{k}}{frac {n}{n-k}}&quadro {testo{se}k<n{{binom {n-1}{k-1}}{frac {n}{k-1}&quadro {testo{se}n,k>0\end{cases}}}
.
Insieme ai casi di base ( n 0 ) = 1 = ( n n ) {displaystyle {{tbinom {n}{0}}=1={tbinom {n}{n}}
, questi permettono di calcolare in successione rispettivamente tutti i numeri di combinazioni di uno stesso insieme (una riga del triangolo di Pascal), di k-combinazioni di insiemi di dimensioni crescenti, e di combinazioni con un complemento di dimensione fissa n – k.
Esempio di conteggio delle combinazioniModifica
Come esempio specifico, si può calcolare il numero di mani di cinque carte possibili da un mazzo standard di cinquantadue carte come:
( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311.875.200 120 = 2.598.960. {\displaystyle {52 \scelta 5}={{frac {52 volte 51 volte 50 volte 49 volte 48}{5 volte 4 volte 3 volte 2 volte 1}}={frac {311{875{200}{120}=2{598{960.}
In alternativa si può usare la formula in termini di fattoriali e annullare i fattori nel numeratore contro parti dei fattori nel denominatore, dopo di che è richiesta solo la moltiplicazione dei fattori rimanenti:
( 52 5 ) = 52 ! 5 ! 47 ! = 52 × 51 × 50 × 49 × 48 × 47 ! 5 × 4 × 3 × 2 × 1 × 47 ! = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 = ( 26 × 2 ) × ( 17 × 3 ) × ( 10 × 5 ) × 49 × ( 12 × 4 ) 5 × 4 × 3 × 2 = 26 × 17 × 10 × 49 × 12 = 2,598,960. }}}}\&={{frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}{9782>={frac {(26\times {cancel {2})\times (17\times {cancel {3})\times (10\times {cancel {5))-49 (12))-49 (12))-49 (4))-26 (5) -4 (10) -3 (2) -}}}}&=26 (17) – 10 (10) -49 (12) -=2 (2),}598{,}960.\fine del paragrafo “allineato”.
Un altro calcolo alternativo, equivalente al primo, si basa sulla scrittura
( n k ) = ( n – 0 ) 1 × ( n – 1 ) 2 × ( n – 2 ) 3 × ⋯ × ( n – ( k – 1 ) ) k , {\displaystyle {n \scegliere k}={frac {(n-0)}{1}{ tempo {frac {(n-1)}{2}{ tempo {frac {(n-2)}{3}{ tempo \punti \frac {(n-(k-1))}{k}},
che dà
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2.598,960 {displaystyle {52 \sceglie 5}={frac {52}{1}} volte {frac {51}{2}} volte {frac {50}{3}} volte {frac {49}{4}}{48}{5}=2{,}598{,}960}
.
Se valutato nel seguente ordine, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, questo può essere calcolato usando solo aritmetica intera. La ragione è che quando avviene ogni divisione, il risultato intermedio che viene prodotto è esso stesso un coefficiente binomiale, quindi non si verificano mai residui.
Utilizzando la formula simmetrica in termini di fattoriali senza eseguire semplificazioni si ottiene un calcolo piuttosto esteso:
( 52 5 ) = n ! k ! ( n – k ) ! = 52 ! 5 ! ( 52 – 5 ) ! = 52 ! 5 ! 47 ! = 80 , 658 , 175 , 170 , 943 , 878 , 571 , 660 , 636 , 856 , 403 , 766 , 975 , 289 , 505 , 440 , 883 , 277 , 824 , 000 , 000 , 000 , 000 120 × 258 , 623 , 241 , 511 , 168 , 180 , 642 , 964 , 355 , 153 , 611 , 979 , 969 , 197 , 632 , 389 , 120 , 000 , 000 , 000 = 2,598,960. {\displaystyle {{aligned}{52 \scegliere 5}&={{frac {n!}{k!(n-k)!}={frac {52!}{5!(52-5)!}={frac {52!}{5!47!}}\\&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\&=2{,}598{,}960.\end{aligned}}
Enumerare le k-combinazioniModifica
Si possono enumerare tutte le k-combinazioni di un dato insieme S di n elementi in un ordine fisso, che stabilisce una biiezione da un intervallo di ( n k ) {\displaystyle {\tbinom {n}{k}}}
interi con l’insieme di quelle k-combinazioni. Supponendo che S sia a sua volta ordinato, per esempio S = { 1, 2, …, n }, ci sono due possibilità naturali per ordinare le sue k-combinazioni: confrontando prima i loro elementi più piccoli (come nelle illustrazioni precedenti) o confrontando prima i loro elementi più grandi. Quest’ultima opzione ha il vantaggio che aggiungendo un nuovo elemento più grande a S non cambierà la parte iniziale dell’enumerazione, ma semplicemente aggiungerà le nuove k-combinazioni dell’insieme più grande dopo le precedenti. Ripetendo questo processo, l’enumerazione può essere estesa indefinitamente con k-combinazioni di insiemi sempre più grandi. Se inoltre gli intervalli dei numeri interi sono presi per iniziare da 0, allora la k-combinazione in un dato posto i nell’enumerazione può essere calcolata facilmente da i, e la biiezione così ottenuta è nota come sistema di numeri combinatori. È anche conosciuta come “rank”/”ranking” e “unranking” nella matematica computazionale.
Ci sono molti modi per enumerare k combinazioni. Un modo è quello di visitare tutti i numeri binari inferiori a 2n. Scegliere quei numeri che hanno k bit non nulli, anche se questo è molto inefficiente anche per piccoli n (ad esempio n = 20 richiederebbe di visitare circa un milione di numeri mentre il numero massimo di combinazioni k consentite è circa 186 mila per k = 10). Le posizioni di questi 1 bit in un tale numero è una specifica k-combinazione dell’insieme { 1, …, n }. Un altro modo semplice e più veloce è quello di tracciare k numeri di indice degli elementi selezionati, a partire da {0 .. k-1} (basato su zero) o {1 .. k} (basato su uno) come prima combinazione k consentita e poi spostarsi ripetutamente alla successiva combinazione k consentita incrementando l’ultimo numero di indice se è inferiore a n-1 (basato su zero) o n (basato su uno) o l’ultimo numero di indice x che è inferiore al numero di indice che lo segue meno uno se tale indice esiste e resettando i numeri di indice dopo x a {x+1, x+2, …}.