Differenze tra le versioni di "Combinazione"

247 byte aggiunti ,  1 anno fa
nessun oggetto della modifica
m (Sostituisco Collegamenti esterni ai vecchi template e rimuovo alcuni duplicati)
{{Nota disambigua}}
 
Nel [[calcolo combinatorio]], se ''n'' e ''k'' sono due [[Numero intero|interi]] positivi, si definisce '''combinazione''' di ''n'' elementi presi ''k'' alla volta (oppure di ''n'' elementi di classe ''k'' oppure di ''n'' elementi a ''k'' a ''k'') ogni sottoinsieme di ''k'' oggettielementi estratti da un insieme di ''n'' oggettielementi. SeSi siparlerà imponedi la'''combinazione condizionesemplice''' chese una combinazioneessa non può avere unelementi elemento ripetutoche si parlaripetono di combinazioni semplici, altrimentie di [[combinazioni con ripetizione|combinazione con ripetizione]] altrimenti. Nel primo caso di combinazioni semplici deve essererisultare ovviamentenecessariamente ''k'' ≤ ''n''.
 
In entrambi i casi i sottoinsiemi sivanno consideranoconsiderati indipendenti'''indipendentemente dall'ordine''' degli elementi. Ad esempio, se siamo in presenza dell'insieme {''p,q,r,s,t''} e prendiamo in esame le combinazioni di classe 3, non fa alcuna differenza considerare i gruppi ''prs'', ''psr'', ''rps'', ''spr'', ''rsp'' ed ''srp'' inrappresentano quanto''la essistessa sonocombinazione'' in quanto formati dagli stessi elementi, mentre i gruppi ''prs'' ed ''srq'' sono consideraterappresentano ''due combinazionidiverse distintecombinazioni'' in quanto differiscono in almeno uno degli elementi.
 
== Combinazioni semplici ==
Dato un [[insieme]] ''A'' di [[cardinalità]] ''n'', il numero dei sottoinsiemi di ''A'' di cardinalità ''k'' ≤ ''n'', vale a dire le combinazioni di n elementi presi a k a k, si ottiene calcolando primadividendo il numero delledi funzionitutti dai unpossibili generico sottoinsiemesottoinsiemi di cardinalità ''k'' in ''A'', che è il numero delle ([[Disposizione|disposizioni]] di ''n'' elementi di classe ''k'',) poi,per dal momento che si prescinde dall'ordine, si divide taleil numero per quello delle [[Permutazione|permutazioni]] di ''k'' elementi:
:<math>C_{n,k}=\frac{D_{n,k}}{P_k}=\frac{\frac{n!}{(n-k)!}}{k!}=\frac{n!}{(n-k)!k!}={n \choose k}</math>
Il simbolo <math>{n \choose k}</math> viene detto [[coefficiente binomiale]].
 
=== Giustificazione della formula ===
FacciamoSi riferimentoconsiderino al numero deii sottoinsiemi di cardinalità 4 dell'insieme {''a,b,c,d,e,f''};. per la definizione data,Avremo abbiamoche:
:<math>C_{6,4}=\frac{6!}{(6-4)!4!}=\frac{6!}{2!4!}=\frac{720}{2\cdot 24}=15</math>
 
:acdf, acef, adef, bcde, bcdf, bcef, bdef, cdef
 
Il risultato può essere ottenuto col seguente ragionamento. Immaginiamo di mettere in un sacchetto le 6 lettere ''a,b,c,d,e,f'' ed estraiamo a caso la prima, che può essere indifferentemente una delle 6: abbiamo quindi 6 possibilità di estrazione. Ora passiamo ad estrarre la seconda lettera: poiché nel sacchetto ne sono rimaste 5, abbiamo 5 possibilità di estrazione. APassiamo questoquindi puntoad estrarre la terza lettera: poiché nel sacchetto ne sono rimaste 4:, quando estrarremo la terza lettera avremoabbiamo 4 possibilità di estrazione. Infine, essendonereiterando rimasteancora 3il ragionamento, quando estrarremoandremo ad estrarre la quarta lettera ne saranno rimaste 3 nel sacchetto e avremo quindi 3 possibilità di estrazione. Se moltiplichiamo tutte le possibilità fra loro, avremo 6×5×4×3 = 360 possibili gruppi.
 
Il valore ottenuto di 360 è, in realtà, il numero delle [[Disposizione|disposizioni semplici]] di 6 oggetti di classe 4, nelle quali '''l'ordine è rilevante'''. Ad esempio, le lettere successivamente estratte potrebbero essere ''a,b,c,d'', ma anche ''d,c,b,a''. Le due sequenze rappresentano ''la stessa combinazione'' in quanto differiscono solo nell'ordine, ma comprendono''non entrambe gli stessinegli elementi diche unle unico sottoinsieme dellcostituiscono''insieme dato. In generale, le quattro lettere ''a,b,c,d'' possono presentarsi in 24 modi diversi, da considerarsi però equivalenti ai fini delle combinazioni:
:abcd abdc acbd acdb adbc adcb
:bacd badc bcad bcda bdac bdca
:dabc dacb dbac dbca dcab dcba
 
PoichéNon nelle combinazioni '''non siamoessendo interessati all'ordine di estrazione''', dobbiamo dividere 360 per il numero di tutte le diversedelle sequenze che si possono formare con le stesse 4 lettere, cioè per il numero delle [[Permutazione|permutazioni]] di 4 elementi, dato da 4! = 24. Il risultato finale è:
 
:<math>
</math>
 
AdFacciamo un ulteriore esempio, seper ribadire la differenza tra combinazione e disposizione. Se si vuole conoscere il numero di comitati di 3 membri che si possono formare scegliendo tra 6 persone, interessa solo sapere in quanti modi si possono scegliere i membri del comitato eindipendentemente '''nonda importa''' qualechi venga scelto per primo o quale per ultimo: in tal caso, stiamo considerando le combinazioni e il numero dei comitati possibili è dato da ''C''<sub>6,3</sub> = 20. Se invece volessimo sapere in quanti modi possono presentarsi i primi 3 classificati tra 6 concorrenti, l'ordine sarebbe rilevante: in quest'altro caso stiamo considerando le disposizioni e, quindi, le possibili classifiche sarebbero date da ''D''<sub>6,3</sub> = 120.
 
=== Ordine lessicografico ===
2 463

contributi