Differenze tra le versioni di "Disposizione"

nessun oggetto della modifica
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.
<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, tutte rappresentate tutte nellain figura 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=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.figura 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") da cui è 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") da cui è 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 <math>A</math> un [[insieme]] finito di [[cardinalità]] <math>k</math> e <math>B</math> un insieme finito di cardinalità <math>n,</math> con <math>0 \le k\le n.</math> Sia inoltre <math>F_k</math> l'insieme delle [[funzione iniettiva|funzioni iniettive]] <math>f\colon A\to B.</math> Vale la seguente [[relazione di ricorrenza|ricorrenzaformula ricorsiva]]:
 
:<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>
che coincide con il 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 adallo esaurimento,svuotamento senza che ce ne rimangano delle altre neldel sacchetto.
 
== Bibliografia ==
2 486

contributi