Differenze tra le versioni di "Disposizione"

4 049 byte aggiunti ,  2 anni fa
 
== Disposizioni semplici ==
Per dare una spiegazione della formula sulle disposizioni semplici si può ricorrere all'estrazione degli elementi da un sacchetto oppure alle funzioni iniettive.
 
=== Estrazione degli elementi ===
Il numero di disposizioni semplici, denotate con il simbolo <math>D_{n, k},</math> di <math>n</math> elementi a <math>k</math> a <math>k</math> è:
Supponiamo di voler estrarre 3 elementi a partire da un insieme di 5 elementi: in altri termini supponiamo di voler considerare le disposizioni di 5 elementi a 3 a 3.
 
A tale proposito supponiamo di mettere in un sacchetto le 5 lettere A, B, C, D ed E e di volerne estrarre 3 a caso. La prima lettera che andremo ad estrarre sarà indifferentemente una delle 5 e quindi avremo 5 possibilità di estrazione. La seconda lettera che andremo ad estrarre sarà una delle 4 rimaste nel sacchetto e quindi avremo 4 possibilità di estrazione. La terza lettera infine che andremo ad estrarre sarà una delle 3 rimaste nel sacchetto e quindi avremo 3 possibilità di estrazione. Se moltiplichiamo tutte le possibilità fra loro avremo 5x4x3 = 60 possibili gruppi. Tali gruppi sono tutti quelli che è possibile considerare prendendo 3 elementi dall'insieme di 5 elementi e comprendono anche i gruppi costituiti dagli stessi elementi ma ordinati diversamente: si tratta evidentemente di tutte le 60 possibili disposizioni ottenibili raggruppando 5 elementi a 3 a 3. Le 60 disposizioni sono riportate di seguito:
:<math>D_{n, k} = n(n-1)(n-2) \cdot \cdot \cdot (n-k+1) = \frac{n!}{(n-k)!}.</math>
 
:ABC ABD ABE ACB ACD ACE ADB ADC ADE AEB AEC AED
La formula si può ottenere usando la seguente formalizzazione. Siano ''A'' un [[insieme]] finito di [[cardinalità]] ''k'' e ''B'' un insieme finito di cardinalità ''n'', con 0 ≤ ''k'' ≤ ''n''. Sia inoltre ''F''<sub>k</sub> l'insieme delle [[funzione iniettiva|funzioni iniettive]] ''f'': ''A'' → ''B''. Sia ''F''<sub>k-1</sub> 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 [[Coppia (matematica)|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 |''F''<sub>k-1</sub>| 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 [[relazione di ricorrenza|ricorrenza]]:
: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
 
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.
:<math>\begin{align}|F_k|&=(n-k+1)|F_{n-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>
 
Generalizzando, se le lettere in totale sono ''n'' e le estrazioni da effettuare sono ''k'', si nota che si parte con una probabilità n per la prima lettera estratta, si scende a n-1 per la seconda lettera estratta e così via fino ad arrivare a n-k+1 per la k-ma lettera estratta. Ripetendo il ragionamento fatto sopra avremo:
essendo |''F''<sub>1</sub>| = ''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:
:<math>(n)_k=\frac{n!}{(n-k)!}</math>
 
:<math>D_{n, k} = n(n-1)(n-2) \cdot \cdot \cdotcdots (n-k+1) = \frac{n!}{(n-k)!}.</math>
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''.
 
cioèovvero un prodotto di ''k'' fattori, ciascuno pari a ''n'' diminuito via via 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 <math>k</math> sia uguale a <math>n</math> si avrebbe:
 
:<math>\begin{align}D_{n,nk} &= 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!}{0(n-k)!}=\fracend{n!align}{1}=n!</math>
 
È da notare infine che quando viene estratta una lettera dal sacchetto, '''quest'ultima non viene rimessa dentro''': questo fatto garantisce che la stessa lettera non può essere estratta più volte e che quindi non ci possono essere elementi ripetuti nel sottoinsieme estratto in conformità alla definizione di disposizione semplice. L'esempio del sacchetto spiega anche '''perché deve risultare necessariamente k≤n''': al massimo possono essere effettuate n estrazioni, dopodiché non rimangono altre lettere nel sacchetto da poter estrarre.
cioè le [[Permutazione|permutazioni]] di <math>n</math> elementi.
 
=== EsempioFunzioni iniettive ===
Oltre che ricorrendo all'estrazione delle lettere da un sacchetto, per ottenere il numero di disposizioni di n elementi a k a k si può ricorrere all'utilizzo delle funzioni iniettive e in particolare alla '''determinazione del numero totale di tutte le funzioni iniettive aventi per dominio un insieme di cardinalità k e per codominio un insieme di cardinalità n'''.
 
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 '''arriva una sola linea di associazione'''. Nel caso di [[Funzione suriettiva|funzioni suriettive]], fermo restando che da ogni elemento del dominio parte una sola linea, capita invece che su uno o più elementi del codominio arrivi più di una linea di associazione.
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:
<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 fig. 1. Indichiamo con '''|''F''<sub>1</sub>|=4''' il numero totale di tali funzioni dove il pedice 1 sta a ricordare che il dominio è costituito da un solo elemento.
<br>[[File:Iniettiva1-4.png|center|upright=3.2|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 '''|''F''<sub>2</sub>|=|''F''<sub>1</sub>|x(4-1)=4x3=12''' il numero totale di tali funzioni dove il pedice 2 a primo membro e il pedice 1 a secondo membro stanno a ricordare che il dominio è costituito rispettivamente da due elementi e da un elemento conformemente alla nostra esposizione.
<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 '''|''F''<sub>3</sub>|=|''F''<sub>2</sub>|x(4-2)=12x2=24''' il numero totale di tali funzioni dove il pedice 3 a primo membro e il pedice 2 a secondo membro stanno a ricordare che il dominio è costituito rispettivamente da tre elementi e da due elementi conformemente alla nostra esposizione.
<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 ''A'' un [[insieme]] finito di [[cardinalità]] ''k'' e ''B'' un insieme finito di cardinalità ''n'', con 0 ≤ ''k'' ≤ ''n''. Sia inoltre ''F''<sub>k</sub> l'insieme delle [[funzione iniettiva|funzioni iniettive]] ''f'': ''A'' → ''B''. Vale la seguente [[relazione di ricorrenza|ricorrenza]]:
 
:<math>\begin{align}|F_k|&=(n-k+1)|F_{nk-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>
:ABC ABD ABE ACB ACD ACE ADB ADC ADE AEB AEC AED
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.
: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
 
essendo |''F''<sub>1</sub>| = ''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 dadi un insieme di cardinalità ''k'' in uno di cardinalità ''n'' si indica anche col simbolo:
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&times;4&times;3 = 60 possibili gruppi.
:<math>(n)_k=\frac{n!}{(n-k)!}</math>
 
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:
 
:<math>D_{n,k} = n(n-1)(n-2) \cdots (n-k+1),</math>
 
cioè 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:
 
:<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>
 
== Disposizioni con ripetizione ==
2 465

contributi