Funzioni suriettive

Catraga · Messaggio da **Catraga** » 01 gen 1970, 01:33

Siano A e B due insiemi finiti. Quante sono le funzioni suriettive da A a B?

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

Siano A e B due insiemi finiti. Poniamo m := card(A), n := card(B), assumendo min{m, n} > 0. Sussistono allora le seguenti proposizioni:
 
 i) L\'insieme F(A,B) di tutte le possibili funzioni f(-): A --> B è finito, e in particolare: card[F(A,B)] = nm.
 
 ii) Se m = n, allora le possibili suriezioni (ovvero iniezioni ovvero biezioni) di A in B sono tante quante le permutazioni semplici di m oggetti, e quindi in numero pari ad m!.
 
 iii) C.N.S. affinché una generica funzione f(-): A --> B sia una suriezione è che esista un sottoinsieme X cardinalmente minimale di A tale che card(X) = card(B) = n e la restrizione di f(-) su X sia una biezione di X in B.
 
 Soluz. del problema: in base alla iii), il numero delle suriezioni di A in B è nullo se m < n. Supposto pertanto m = n, sia f(-) una funzione suriettiva di A su B: l\'esistenza di una relazione siffatta risulta garantita dalla iii), sì come pure l\'esistenza di un sottoinsieme X di A, equipotente a B, tale che la restrizione di f(-) ad X sia una biezione di X su B. Ora, l\'insieme X può essere scelto in tanti modi diversi quante sono le possibili combinazioni semplici di m
 elementi di classe n, ovvero m!/[n!(m-n)!]. E poiché f(-), ristretta su X, costituisce una biezione di X in B, ne fa seguito - per cagione della ii) - che f(-) potrà esser definita globalmente in n! modi distinti. Ché d\'altra parte: A = X U (A/X), ove \"U\" e \"/\" indicano qui, rispettivamente, le ordinarie operazioni insiemistiche di somma (unione) e differenza. Sicché, se f(-) è una suriezione di A in B, allora essa può scegliersi in tanti modi quante sono le possibili determinazioni di X qual sottoinsieme di A equipotente a B - si è detto m!/[n!(m-n)!] - moltiplicate per il numero delle possibili biezioni di X in B - si è detto n! - e ancora per il numero delle possibili corrispondenze realizzate fra gli m-n elementi residui dell\'insieme differenza A/X e gli m elementi fissi dell\'insieme B, ossia per un ulteriore coefficiente nm-n, sì come stabilito dalla i)...
 
 Riassumendo, se ne trae dunque che il numero complessivo delle possibili funzioni suriettive di A in B è pari ad [m!/(m-n)!]*nm-n.
 
 N.B.: ho appena realizzato che, almeno in un passaggio, la soluzione che ho proposto non è massimamente rigorosa. Qualcuno si prenderebbe la briga di apportarvi la dovuta correzione? Grazie...

LB · Messaggio da LB » 01 gen 1970, 01:33

Sono purtroppo costretto a rilevare, con sommo dispiacere, che, oltre ad eventuali mancanze di rigore, sono riscontrabili dei problemi assai piu\' gravi, dovuti certamente ad una momentanea distrazione esterna, invece che ad un\'intrinseca incapacita\' che, come noto, non e\' certamente attribuibile a persone abili e capaci, nonche\' rigorose, come il nostro Euler_25.
 
 Anziche\' esporre la questione nei dettagli, mi limito a far notare che, essendo per definizione l\'insieme delle funzioni suriettive A -> B un sottoinsieme delle funzioni A -> B, quest\'ultimo non puo\' avere cardinalita\' maggiore del primo.
 
 Tuttavia e\' facile vedere che se per valori sufficientemente grandi di a, dipendentemente da b, si ha che a!/(a - b)! * b^(a - b) > b^a.
 
 Ad esempio, per |A| = 3 e |B| = 2, la presunta soluzione suggerirebbe l\'esistenza di ben 12 funzioni suriettive A -> B, cosa che risulta perlomeno bizzarra, dato che tutte le possibili funzioni A -> B sono solo 2^3 = 8.
 [ Questo Messaggio è stato Modificato da: LB il 20-02-2004 21:08 ]

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

...qualcuno può dirmi qual è l\'equivalente onomatopeico di uno sbadiglio annoiato? Ne avrei giusto bisogno in questo mentre... <IMG SRC="images/forum/icons/icon_biggrin.gif">

Alex85 · Messaggio da **Alex85** » 01 gen 1970, 01:33

classico esempio da stage, sull\'argomento incl-escl
 
 Siano A e B due insiemi finiti. Quante sono le funzioni suriettive da A a B?
 
 intanto #A=a, #B=b, a>b
 la faccio poco formale <IMG SRC="images/forum/icons/icon_razz.gif">
 suriettiva significa che becca tutti gli elementi di B
 le funzioni F_tot da A a B sono b^a
 chiamiamo F_1 l\'insieme di funzioni che lascia libero almeno il primo elemento di B
 chiamiamo F_(1,2) l\'insieme di funz. che lascia libero almeno il primo e il secondo elemento di B
 chiamiamo F_2 ecc.
 #(F_1) = (b-1)^a
 #(F_(1,2)) = (b-2)^a
 ecc.
 facciamo che \'i\' è intersezione
 F_1 i F_2 = F_(1,2)
 l\'insieme di funz che lasciano almeno un elemento libero è F_1 U F_2 .. U F_b
 calcoliamo la cardinalità, incl-escl
 
 |F_1 U F_2 .. U F_b| =
 + |F_1| + |F_2| ... |F_b| +
 - |F_(1,2)| - ...
 + |F_(1,2,3)| + ...
 =
 (b 1)(b-1)^a
 -(b 2)(b-2)^a
 ...
 =
 - sum(e da 1 a b) (-1)^e (b e)(b-e)^a =
 - sum(e da 1 a b) (-1)^e (b b-e)(b-e)^a =
 - sum(e da 0 a b-1) (-1)^(b-e) (b e)(e)^a =
 - sum(e da 0 a b-1) (-1)^b / ((-1)^e) (b e)(e)^a =
 -(-1)^b sum(e da 0 a b-1) (-1)^e (b e)(e)^a =|F_lib|
 [se b>1]
 -(-1)^b sum(e da 1 a b-1) (-1)^e (b e)(e)^a = |F_lib|
 le funzioni suriettive sono |F_tot - F_lib|
 
 alex
 
 ps. incl escl si usa quasi solo per funzioni suriettive, e combinazioni senza ripetizione.