Dati due insiemi finiti A,B
1. quante sono le funzioni surgettive da A a B (assumendo #A>=#B)?
2. [più facile] quante sono le funzioni da X sottoinsieme di A a B?
FUNZIONI
-
mistergiovax
salve
era da un po di tempo che non mi intromettevo nelle vostre discussioni.
Dati due insiemi finiti A e B si calcolano le funzioni suriettive(o surgettive che dir si voglia) con un'idea molto semplice:
tutte le funzioni possibili meno quelle non suriettive
questo calcolo diventa ''relativamente'' semplice se si conosce il principio di inclusione-esclusione. Per calcolare tutte le funzioni non suriettive si considera di volta in volta il numero di funzioni da A in B (togliendo di volta in volta a B un elemento). sicuramente non mi sono spiegato bene, ma purtroppo non ho molto tempo a disposizione
baci e abbracci
era da un po di tempo che non mi intromettevo nelle vostre discussioni.
Dati due insiemi finiti A e B si calcolano le funzioni suriettive(o surgettive che dir si voglia) con un'idea molto semplice:
tutte le funzioni possibili meno quelle non suriettive
questo calcolo diventa ''relativamente'' semplice se si conosce il principio di inclusione-esclusione. Per calcolare tutte le funzioni non suriettive si considera di volta in volta il numero di funzioni da A in B (togliendo di volta in volta a B un elemento). sicuramente non mi sono spiegato bene, ma purtroppo non ho molto tempo a disposizione
baci e abbracci
provo la 1: poniamo m=|A|>=|B|=n. Dovendo la funzione essere surgettiva, ad ogni elemento di B deve essere associato almeno un elemento di A. Quindi per il primo elemento di B abbiamo m scelte, per il secondo m-1 e così via. La totalità delle scelte è $ D_{m,n}=\frac{m!}{(m-n)!} $. Ai restanti m-n elementi di A, può essere associato un qualunque elemento tra gli n di B, quindi le scelte possibili sono $ n^{m-n} $. Quindi in tutto vi sono $ \frac{m!}{(m-n)!} \cdot n^{m-n} $ funzioni surgettive da A in B.