Disposizione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
evitare "pari a" visto che in matematica pari è un termine tecnico |
tolgo grassetti inopportuni e sistemo notazione math |
||
Riga 2:
{{Nota disambigua|la disposizione in senso filosofico|Abito (filosofia)}}
Nel [[calcolo combinatorio]], se
Se nei sottoinsiemi ''non sono ammessi'' elementi ripetuti si parla di '''disposizioni semplici''' altrimenti di '''disposizioni con ripetizione''': nel primo caso deve essere <math>k \le n.</math>
Riga 26:
Tra di esse ritroviamo anche ABC, ACB, BAC, BCA, CAB e CBA: pur essendo disposizioni costituite dagli stessi elementi esse sono da considerarsi differenti perché ordinate diversamente in conformità alla stessa definizione di disposizione.
Generalizzando, se le lettere in totale sono
:<math>D_{n,k} = n(n-1)(n-2) \cdots (n-k+1),</math>
:<math>\begin{align}D_{n,k} &= n(n-1)(n-2) \cdots (n-k+1)\\&= \frac{n(n-1)(n-2) \cdots (n-k+1)(n-k)(n-k-1)\cdots 1}{(n-k)(n-k-1)\cdots 1}\\&=\frac{n!}{(n-k)!}.\end{align}</math>
È da notare infine che quando viene estratta una lettera dal sacchetto,
=== Funzioni iniettive ===
Oltre che ricorrendo all'estrazione delle lettere da un sacchetto, per ottenere il numero di disposizioni di <math>n</math> elementi a <math>k</math> a <math>k</math> si può ricorrere all'utilizzo delle funzioni iniettive e in particolare alla
Una [[funzione iniettiva]] è una legge che associa a ogni elemento del dominio un differente elemento del codominio. Considerando il caso di un dominio e di un codominio costituiti da due insiemi di elementi, ciò significa che da ogni elemento del dominio parte una sola linea di associazione (questo fatto è sempre vero per la definizione stessa di funzione sia essa iniettiva, suriettiva o biiettiva) e che su ogni elemento del codominio
<br>[[File:Iniettiva-Suriettiva.png|center|upright=3.2|miniatura|<div style="text-align:center">Differenza tra funzione iniettiva-suriettiva</div>]]<br>
Per fissare le idee supponiamo di considerare le funzioni iniettive di 1 elemento in 4 elementi: in totale saranno solo 4 tali funzioni rappresentate tutte nella
<br>[[File:Iniettiva1-4.png|center|upright=4.0|miniatura|<div style="text-align:center">Fig. 1: funzioni di un elemento in un insieme di 4 elementi</div>]]<br>
Le funzioni iniettive di 2 elementi in 4 elementi sono in totale 12: in fig. 2 sono riportati due diversi esempi delle 12 funzioni possibili. Da notare che nel passaggio dalle funzioni iniettive di 1 in 4 a quelle di 2 in 4 si è passati da 4 funzioni possibili a 12 funzioni possibili: ciò si spiega con il fatto che a ciascuna delle funzioni di 1 in 4 (ad esempio la 1-A di fig. 1) è come se si fosse aggiunto un altro elemento al dominio (ad esempio l'elemento "2") e da questo è possibile far partire 3 diverse associazioni (2-B, 2-C e 2-D). Ciò porta il totale a 4x3=12. Indichiamo con
<br>[[File:Iniettiva2-4.png|center|upright=3.2|miniatura|<div style="text-align:center">Fig. 2: esempi di funzioni iniettive di due elementi in un insieme di 4 elementi</div>]]<br>
Ripetendo il ragionamento, le funzioni iniettive di 3 in 4 elementi sono in totale 24: in figura 3 sono riportati due diversi esempi delle 24 funzioni possibili. Da notare che nel passaggio dalle funzioni iniettive di 2 in 4 a quelle di 3 in 4 si è passati da 12 funzioni possibili a 24 funzioni possibili: ciò si spiega con il fatto che a ciascuna delle funzioni di 2 in 4 (ad esempio la 1-A, 2-B di fig. 2) è come se si fosse aggiunto un altro elemento al dominio (ad esempio l'elemento "3") e da questo è possibile far partire 2 diverse associazioni (3-C e 3-D). Ciò porta il totale a 12x2=24. Indichiamo con
<br>[[File:Iniettiva3-4.png|center|upright=3.2|miniatura|<div style="text-align:center">Fig. 3: esempi di funzioni iniettive di tre elementi in un insieme di 4 elementi</div>]]<br>
Generalizzando, siano
:<math>\begin{align}|F_k|&=(n-k+1)|F_{k-1}|\\&=(n-k+1)(n-k+2)\cdots(n-1)|F_1|\\&=(n-k+1)(n-k+2)\cdots(n-1)(n)=\frac{n!}{(n-k)!},\end{align}</math>
essendo in generale '''|''F''<sub>1</sub>|=''n''''' in conformità con l'esempio sopra delle funzioni di 1 in 4 dove '''|''F''<sub>1</sub>|=4''' avendosi nella fattispecie '''n=4'''. Siamo così giunti alla conclusione enunciata sopra che il numero di funzioni iniettive di un insieme di cardinalità k in un insieme di cardinalità n si identifica con quello delle disposizioni semplici di n elementi a k a k.▼
▲essendo in generale
Il numero delle funzioni iniettive di un insieme di cardinalità ''k'' in uno di cardinalità ''n'' si indica anche col simbolo:▼
:<math>(n)_k=\frac{n!}{(n-k)!}</math>▼
▲Il numero delle funzioni iniettive di un insieme di cardinalità
▲:<math>(n)_k=\frac{n!}{(n-k)!}.</math>
== 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> è:
:<math>D^'_{n, k} = n^k.</math>
Line 64 ⟶ 67:
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,
Tali disposizioni sono riportate di seguito:
Line 79 ⟶ 82:
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
:<math>D^'_{n, k} = n^k.</math>
Line 86 ⟶ 89:
=== Funzioni iniettive e suriettive ===
Oltre che ricorrendo all'estrazione delle lettere da un sacchetto, per ottenere il numero di disposizioni con ripetizione di <math>n</math> elementi a <math>k</math> a <math>k</math> si può ricorrere all'utilizzo delle funzioni e in particolare alla
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
Passiamo ora a considerare le funzioni di 2 elementi in 4 elementi: la
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 relative al primo elemento del dominio vanno moltiplicate per le 4 associazioni relative al secondo elemento del dominio ottenendo 4x4=16 che sono proprio il totale delle funzioni iniettive e suriettive di 2 elementi in 4 elementi.
<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
:<math>D^'_{n, k} = n^k.</math>
=== Esempi ===
I numeri
Il numero delle possibili colonne del [[totocalcio]] composte da tredici pronostici scelti fra tre elementi (1, X o 2) è uguale a 3<sup>13</sup> = 1.594.323. In questo caso <math>k>n</math> essendo <math>k=13</math>
== Permutazione: caso particolare di disposizione semplice ==
Si può notare che c'è una relazione tra le disposizioni semplici e le permutazioni. Infatti nel caso in cui <math>k</math> sia uguale a <math>n</math> si ha:
:<math>D_{n,n} = \frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n!,</math>
che è uguale al numero di [[Permutazione|permutazioni]] di <math>n</math> elementi.
D'altronde ciò è ovvio se si ricorre all'esempio dell'estrazione delle lettere da un sacchetto: le permutazioni possono essere viste come le estrazioni delle lettere con la condizione che vengano effettuate tante estrazioni quante sono le lettere stesse, fino ad esaurimento, senza che ce ne rimangano delle altre nel sacchetto.
|