Differenze tra le versioni di "Disposizione"

4 376 byte aggiunti ,  2 anni fa
 
== Disposizioni con ripetizione ==
Il numero di disposizioni con ripetizione, denotate con il simbolo <math>D^'_{n, k},</math> di <math>n</math> elementi a <math>k</math> a <math>k</math> è pari a:
:<math>D^'_{n, k} = n^k.</math>
 
Anche qui per dare una spiegazione di tale formula si può ricorrere all'estrazione degli elementi da un sacchetto oppure alle funzioni iniettive e suriettive.
 
=== Estrazione degli elementi ===
Supponiamo di voler estrarre 3 elementi a partire da un insieme di 4 elementi ma a differenza di prima facciamo in modo che gli elementi possano ripetersi: in altri termini si vogliono trovare le disposizioni con ripetizione di 4 elementi a 3 a 3.
 
A tale proposito supponiamo di mettere in un sacchetto le 4 lettere A, B, C e D e di volerne estrarre 3 a caso. La prima lettera che andremo ad estrarre sarà indifferentemente una delle 4 e quindi avremo 4 possibilità di estrazione. Ora però, prima di procedere all'estrazione della seconda lettera, '''rimettiamo nel sacchetto la lettera che abbiamo appena estratto'''. Anche la seconda lettera che andremo ad estrarre sarà indifferentemente una delle 4 e quindi avremo nuovamente 4 possibilità di estrazione: tra l'altro può capitare che la seconda lettera estratta sia la stessa della prima, che quindi ci sia la '''ripetitività''', essendo ripartiti con tutte le lettere nel sacchetto. Ancora una volta rimettiamo nel sacchetto la lettera appena estratta. Infine, anche la terza lettera che andremo ad estrarre sarà indifferentemente una delle 4 e quindi avremo nuovamente 4 possibilità di estrazione. Se moltiplichiamo tutte le possibilità fra loro avremo 4x4x4=4<sup>3</sup>=64 possibili gruppi, vale a dire le ''64 possibili disposizioni con ripetizione'' di 4 elementi presi a 3 a 3.
 
Tali disposizioni sono riportate di seguito:
 
:AAA AAB AAC AAD ABA ABB ABC ABD
:ACA ACB ACC ACD ADA ADB ADC ADD
:BAA BAB BAC BAD BBA BBB BBC BBD
:BCA BCB BCC BCD BDA BDB BDC BDD
:CAA CAB CAC CAD CBA CBB CBC CBD
:CCA CCB CCC CCD CDA CDB CDC CDD
:DAA DAB DAC DAD DBA DBB DBC DBD
:DCA DCB DCC DCD DDA DDB DDC DDD
 
Come si può vedere diversi gruppi presentano elementi ripetuti e anche qui, per esempio, le disposizioni AAB e BAA sono considerate differenti in quanto pur avendo gli stessi elementi (la lettera A che si ripete due volte e la lettera B) esse sono ordinate diversamente.
 
Generalizzando, se le lettere sono ''n'' e le estrazioni da effettuare sono ''k'', si nota che, avendo cura di rimettere la lettera estratta nel sacchetto, si riparte ogni volta con una probabilità n indipendentemente se si tratta della prima, seconda, terza estrazione e così via. Il numero di disposizioni con ripetizione sarà dato dal prodotto di ''n'' per se stesso ''k'' volte (''nxnxnx...xn''). Da ciò deriva la formula:
 
Il numero di disposizioni con ripetizione, denotate con il simbolo <math>D^'_{n, k},</math> di <math>n</math> elementi a <math>k</math> a <math>k</math> è:
:<math>D^'_{n, k} = n^k.</math>
 
È da notare infine che, a differenza delle disposizioni semplici, nelle disposizioni con ripetizione ''non vale il vincolo'' <math>k \le n</math>: poiché ogni volta si rimette nel sacchetto la lettera appena estratta, non c'è il rischio che esse si esauriscano come capita invece nelle disposizioni semplici dove, dopo n estrazioni, non rimangono nel sacchetto più lettere da poter estrarre.
La formula si può ottenere usando la seguente formalizzazione. 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''.
 
=== Funzioni iniettive e suriettive ===
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''.
Oltre che ricorrendo all'estrazione delle lettere da un sacchetto, per ottenere il numero di disposizioni con ripetizione di n elementi a k a k si può ricorrere all'utilizzo delle funzioni e in particolare alla '''determinazione del numero totale di tutte le funzioni siano esse iniettive o suriettive''' aventi per dominio un insieme di cardinalità k e per codominio un insieme di cardinalità n.
 
Per fissare le idee supponiamo di considerare le funzioni di 1 elemento in 4 elementi: poiché c'è una sola linea di associazione che parte dall'unico elemento presente nel dominio e poiché tale linea non può che finire in un unico elemento dei 4 presenti nel codominio, non si verificherà mai per questa condizione di avere a che fare con funzioni suriettive le quali, come detto sopra, richiedono che almeno un elemento del codominio sia interessato da almeno due linee di associazione. Pertanto anche nel caso delle disposizioni con ripetizione varrà la fig. 1 essendo le funzioni di 1 in 4 sempre di tipo iniettivo. Quindi le disposizioni semplici di 4 elementi a 1 a 1 e quelle con ripetizione di 4 elementi a 1 a 1 si identificano fra di loro, anche perché è impossibile avere delle ripetizioni se si è in presenza di un solo elemento.
=== Esempi ===
 
Passiamo ora a considerare le funzioni di 2 elementi in 4 elementi: la fig. 4 illustra tutte le 16 funzioni di tale tipo, siano esse iniettive o suriettive. In particolare si può notare come la situazione di suriettività dia vita alla ripetitività degli elementi del codominio che contraddistingue a sua volta le disposizioni con ripetizione: ad esempio la (1) di fig. 4 determina la disposizione AA mentre la (8) determina la disposizione BB.
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&times;10=10<sup>2</sup>.
 
Nel passaggio dalle funzioni di 1 elemento in 4 elementi a quella di 2 elementi in 4 elementi è come se al dominio avessimo aggiunto un altro elemento: a differenza del caso delle disposizioni semplici, ora nelle disposizioni con ripetizione consentiamo a questo secondo elemento di associarsi con uno qualunque dei 4 elementi del codominio ''anche con l'elemento del codominio già associato al primo elemento del dominio''. Pertanto le 4 associazioni dovute al primo elemento del dominio vanno moltiplicate per le 4 associazioni dovute al secondo elemento del dominio ottenendo 4x4=16 che sono proprio il totale delle funzioni iniettive e suriettive di 2 elementi in 4 elementi.
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, è 10<sup>2</sup>; 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.
<br>[[File:Funzioni2-4.png|center|upright=3.2|miniatura|<div style="text-align:center">Fig. 4: funzioni di 2 elementi in 4 elementi</div>]]<br>
 
Generalizzando, se con ''A'' denotiamo un [[insieme]] finito di [[cardinalità]] ''k'' e con ''B'' un insieme finito di cardinalità ''n'', il numero totale di funzioni ''f'': ''A'' → ''B'', iniettive o suriettive che siano, sarà pari a n<sup>k</sup> in conformità con la formula delle disposizioni con ripetizione che ci proponevamo di dimostrare:
 
:<math>D^'_{n, k} = n^k.</math>
 
=== Esempi ===
I numeri composti da due cifre sono quelli che si ottengono dalle diposizioni con ripetizione di 10 elementi (i numeri da 0 a 9) presi a 2 a 2 che sono pari a 10<sup>2</sup>=100: si tratta di 00, 01, ..., 09, 10, 11, ..., 19, 20, 21, 22, ...., 99.
 
Analogamente, ilIl numero delle possibili colonne del [[totocalcio]], composte da quattordicitredici pronostici scelti fra tre elementi (1, X o 2), è pari a: 3<sup>1413</sup> = 41.782594.969323. In questo caso k>n essendo k=13 ed n=3 a conferma del fatto che nelle disposizioni con ripetizione il numero di posti k può essere qualunque indipendentemente da n.
 
== Bibliografia ==
2 465

contributi