Disposizione: differenze tra le versioni
m Annullate le modifiche di 95.226.20.133 (discussione), riportata alla versione precedente di Robbot |
|||
Riga 41: | Riga 41: | ||
cioè le [[Permutazione|permutazioni]] di n elementi. |
cioè le [[Permutazione|permutazioni]] di n elementi. |
||
== Disposizioni con ripetizione |
== Disposizioni con ripetizione == |
||
Una [[Funzione (matematica)|funzione]] da un insieme ''A'' in un insieme ''B'' può essere vista come un insieme di |
Una [[Funzione (matematica)|funzione]] da un insieme ''A'' in un insieme ''B'' può essere vista come un insieme di coppie (''a'',''b'') tale che vi siano tante coppie quante sono gli elementi ''a'' di ''A'' e che non vi sia alcun ''a'' presente in più di una coppia. Possono invece esservi nessuna o più coppie aventi, come secondo membro, un dato elemento ''b'' di ''B''. |
||
Dati un insieme ''A'' di cardinalità ''k'' ed un insieme ''B'' di cardinalità ''n'', con ''n'' e ''k'' interi positivi, il numero delle funzioni da ''A'' in ''B'' è dato da ''n''<sup>k</sup>, in quanto ciascuna delle ''k'' coppie può avere come secondo membro uno qualsiasi degli ''n'' elementi di ''B''. Ad esempio, il numero delle funzioni da un insieme di 2 elementi {''a'', ''b''} in un insieme di 10 elementi {1,...,10} è 10<sup>2</sup>, in quanto si hanno 10 coppie del tipo (''a'', ''x''), dove ''x'' = 1,2,...,10, e per ciascuna di esse 10 coppie del tipo (''b'', ''x''). Ciascuna delle funzioni cercate è costituita da una delle dieci coppie il cui primo elemento sia ''a'' e da una delle dieci il cui primo elemento sia ''b''; il numero di tali funzioni è quindi dato dalla cardinalità del [[prodotto cartesiano]] dei due insiemi di dieci coppie: 10×10=10<sup>2</sup>. |
Dati un insieme ''A'' di cardinalità ''k'' ed un insieme ''B'' di cardinalità ''n'', con ''n'' e ''k'' interi positivi, il numero delle funzioni da ''A'' in ''B'' è dato da ''n''<sup>k</sup>, in quanto ciascuna delle ''k'' coppie può avere come secondo membro uno qualsiasi degli ''n'' elementi di ''B''. Ad esempio, il numero delle funzioni da un insieme di 2 elementi {''a'', ''b''} in un insieme di 10 elementi {1,...,10} è 10<sup>2</sup>, in quanto si hanno 10 coppie del tipo (''a'', ''x''), dove ''x'' = 1,2,...,10, e per ciascuna di esse 10 coppie del tipo (''b'', ''x''). Ciascuna delle funzioni cercate è costituita da una delle dieci coppie il cui primo elemento sia ''a'' e da una delle dieci il cui primo elemento sia ''b''; il numero di tali funzioni è quindi dato dalla cardinalità del [[prodotto cartesiano]] dei due insiemi di dieci coppie: 10×10=10<sup>2</sup>. |
Versione delle 10:38, 20 ott 2012
Nel calcolo combinatorio, se n e k sono due interi positivi, si definisce disposizione di n elementi k a k (oppure di n elementi di classe k, oppure di n elementi presi k alla volta) ogni sottoinsieme ordinato di k oggetti estratti da un insieme di n oggetti, in cui i sottoinsiemi differiscono se presentano qualche elemento diverso o se presentano gli stessi elementi ma in ordine diverso. Talvolta, k viene chiamato numero di posti e la disposizione di n oggetti in k posti viene chiamata k-disposizione. Se si impone la condizione che in ogni sottoinsieme non sono ammessi elementi ripetuti si parla di disposizioni semplici altrimenti di disposizioni con ripetizione. Nel primo caso deve essere ovviamente k ≤ n.
Disposizioni semplici
Siano A un insieme finito di cardinalità k e B un insieme finito di cardinalità n, con 0 ≤ k ≤ n. Sia inoltre Fk l'insieme delle funzioni iniettive f: A → B.
Sia Fk-1 l'insieme delle funzioni iniettive da un sottoinsieme di A di cardinalità k–1 in B. Ciascuna di tali funzioni è un insieme di k-1 coppie (a,b), con a appartenente al sottoinsieme di A e b appartenente a B, tali che ciascun a e ciascun b compaiano in una sola di esse.
Sia |Fk-1| il numero di tali funzioni. Il numero delle funzioni iniettive da A in B si ottiene aggiungendo, per ciascuna funzione, il numero delle coppie (a,b) in cui a e b non siano già presenti in alcuna coppia. Vi è un solo a, ma vi sono n – (k-1) elementi b, ovvero n – (k-1) nuove coppie. Si ha quindi la ricorrenza:
essendo |F1| = n, in quanto vi sono n coppie (a,b) in cui a sia fissato e b sia scelto tra gli n elementi di B.
Il numero delle funzioni iniettive da un insieme di cardinalità k in uno di cardinalità n si indica anche col simbolo:
Nella terminologia combinatoria classica, il numero delle applicazioni iniettive da un insieme di cardinalità k in un insieme di cardinalità n viene detto numero delle disposizioni semplici di n oggetti presi k alla volta, o di classe k, e si indica con Dn,k.
Ad esempio, se n=5 e k=3 e come oggetti consideriamo le lettere A, B, C, D ed E, allora le disposizioni possibili sono le seguenti 5!/(5-3)! = 120/2 = 60:
- ABC ABD ABE ACB ACD ACE ADB ADC ADE AEB AEC AED
- BAC BAD BAE BCA BCD BCE BDA BDC BDE BEA BEC BED
- CAB CAD CAE CBA CBD CBE CDA CDB CDE CEA CEB CED
- DAB DAC DAE DBA DBC DBE DCA DCB DCE DEA DEB DEC
- EAB EAC EAD EBA EBC EBD ECA ECB ECD EDA EDB EDC
Il risultato può essere ottenuto col seguente ragionamento: supponiamo di mettere in un sacchetto le lettere A, B, C, D ed E e di estrarne una a caso. La prima lettera estratta può essere indifferentemente una delle 5 e quindi abbiamo 5 possibilità di estrazione. Ora passiamo ad estrarre la seconda lettera: poiché nel sacchetto ne sono rimaste 4, abbiamo 4 possibilità di estrazione. A questo punto, nel sacchetto ne sono rimaste 3 ed avremo quindi, per la terza lettera, 3 possibilità di estrazione. Se moltiplichiamo tutte le possibilità fra loro, avremo 5×4×3 = 60 possibili gruppi.
Generalizzando, ogni volta che si estrae una lettera, il numero delle lettere che si possono estrarre diminuisce di uno; se nel sacchetto ci sono n lettere e vogliamo estrarne k avremo:
ovvero un prodotto di k fattori pari a n diminuito di 0, 1, ..., (k-1). Moltiplicando e dividendo tale prodotto per (n-k)!, si ottiene la formula data sopra:
Infine si può notare che c'è una relazione tra le disposizioni e le permutazioni; infatti nel caso in cui k sia uguale a n si avrebbe:
cioè le permutazioni di n elementi.
Disposizioni con ripetizione
Una funzione da un insieme A in un insieme B può essere vista come un insieme di coppie (a,b) tale che vi siano tante coppie quante sono gli elementi a di A e che non vi sia alcun a presente in più di una coppia. Possono invece esservi nessuna o più coppie aventi, come secondo membro, un dato elemento b di B.
Dati un insieme A di cardinalità k ed un insieme B di cardinalità n, con n e k interi positivi, il numero delle funzioni da A in B è dato da nk, in quanto ciascuna delle k coppie può avere come secondo membro uno qualsiasi degli n elementi di B. Ad esempio, il numero delle funzioni da un insieme di 2 elementi {a, b} in un insieme di 10 elementi {1,...,10} è 102, in quanto si hanno 10 coppie del tipo (a, x), dove x = 1,2,...,10, e per ciascuna di esse 10 coppie del tipo (b, x). Ciascuna delle funzioni cercate è costituita da una delle dieci coppie il cui primo elemento sia a e da una delle dieci il cui primo elemento sia b; il numero di tali funzioni è quindi dato dalla cardinalità del prodotto cartesiano dei due insiemi di dieci coppie: 10×10=102.
Nella terminologia combinatoria classica, il numero delle funzioni da un insieme di cardinalità k in uno di cardinalità n viene detto numero delle disposizioni con ripetizione di n oggetti k a k, o di classe k; a differenza delle disposizioni semplici, k può essere maggiore di n.
L'esempio sopra proposto può essere reinterpretato come segue. Dati 10 oggetti distinti, il numero delle presentazioni di 2 di tali elementi, anche non diversi tra loro, è 102; in particolare, con le 10 cifre da 0 a 9 si possono comporre 100 numeri di due cifre: 00, 01, ..., 09, 10, 11, ..., 19, 20, 21, 22, ...., 99.
Analogamente, il numero delle possibili colonne del totocalcio, composte da tredici pronostici scelti tra tre (1, X o 2), è pari a: 313 = 1.594.323.