Numero delle applicazioni suriettive
Ciao a tutti, il prof di algebra1 ci ha dato il seguente esercizio:
Dati due insiemi $A$ e $B$, la cui cardinalità è $|A|=m$ e $|B|=n$, trovare il numero di tutte le applicazioni suriettive $f:AtoB$.
Io ho pensato di fare così: prendo il numero di tutte le applicazioni $AtoB$ e sottraggo tutte quelle non suriettive, quindi $m^n-X$. Ora però non riesco a trovare un modo per enumerare tutte quelle non suriettive! Come si potrebbe fare??
Grazie..
Dati due insiemi $A$ e $B$, la cui cardinalità è $|A|=m$ e $|B|=n$, trovare il numero di tutte le applicazioni suriettive $f:AtoB$.
Io ho pensato di fare così: prendo il numero di tutte le applicazioni $AtoB$ e sottraggo tutte quelle non suriettive, quindi $m^n-X$. Ora però non riesco a trovare un modo per enumerare tutte quelle non suriettive! Come si potrebbe fare??
Grazie..
Risposte
sicuro che il testo dell'esercizietto sia questo, con m ed n generici? In ogni caso puoi sbirciare i numeri di Stirling della seconda forma
Si si m ed n sono generici... Ma questo punto ho come il sospetto che non si è reso conto di cosa c'ha dato da fare! Ho dato un'occhiata a questi numeri di Stirling, ma non ho idea nè di cosa siano nè di cosa sia l'n-esimo numero di Bell........... 
Ponendo $n<=m$ (altrimenti la funzione non è suriettiva) , il numero di funzioni $= m^(n)$
Si ma queste sono TUTTE le funzioni $AtoB$, incluse quelle non surettive (tipo quelle costanti, che sono $n$, e in generale tutte quelle che lasciano qualche elemento di $B$ senza controimmagine...)
"gygabyte017":
Si ma queste sono TUTTE le funzioni $AtoB$, incluse quelle non surettive (tipo quelle costanti, che sono $n$, e in generale tutte quelle che lasciano qualche elemento di $B$ senza controimmagine...)
Ma le funzioni costanti sono suriettive... o sbaglio?
Dunque: una funzione è suriettiva quando per ogni elemento dell'insieme di arrivo corrisponde almeno un elemento dell'insieme di partenza.
Se $n<=m$ le funzioni sono necessariamente tutte suriettive...
Se $n<=m$ le funzioni sono necessariamente tutte suriettive...
"klarence":
Se $n<=m$ le funzioni sono necessariamente tutte suriettive...
No. Per esempio la funzione $\{1,2,3\} to \{1,2\}$ che manda tutto in 1 non è suriettiva.
La definizione di funzione suriettiva dovrebbe essere:
"La funzione $f:AtoB$ è suriettiva se $AAbinB" "EEainA|f(a)=b$."
Quindi le funzioni costanti hanno elementi che non hanno controimmagine in A quindi non sono suriettive!
"La funzione $f:AtoB$ è suriettiva se $AAbinB" "EEainA|f(a)=b$."
Quindi le funzioni costanti hanno elementi che non hanno controimmagine in A quindi non sono suriettive!
"Martino":
[quote="klarence"]Se $n<=m$ le funzioni sono necessariamente tutte suriettive...
No. Per esempio la funzione $\{1,2,3\} to \{1,2\}$ che manda tutto in 1 non è suriettiva.[/quote]
Ora ho capito l'errore che ho fatto ! grazie
https://www.matematicamente.it/f/viewtop ... 339#164339
O con i numeri di Stirling di seconda specie, $n!S_n^{(m)}$.
O con i numeri di Stirling di seconda specie, $n!S_n^{(m)}$.
Allora puoi fare così. Dividi il problema in due parti: se $n=m$ e la funzione deve essere suriettiva, dovrà necessariamente essere iniettiva, quindi in numero di funzioni : $n(n-1)*...*1$ (è il fattoriale ma non so come si scrive).
Se $n < m$ , $n$ termini dell'insieme $m$ avranno una scelta obbligata (andare su tutti gli elementi dell'insieme $m$), mentre gli altri $m-n$ potranno fare ciò che vogliono : $n(n-1)*...*1*n^(m-n)$.
Se $n>m$ il problema non si può fare perchè altrimenti alcuni elementi di $n$ non sarebbero coperti da elementi di $m$
Se $n < m$ , $n$ termini dell'insieme $m$ avranno una scelta obbligata (andare su tutti gli elementi dell'insieme $m$), mentre gli altri $m-n$ potranno fare ciò che vogliono : $n(n-1)*...*1*n^(m-n)$.
Se $n>m$ il problema non si può fare perchè altrimenti alcuni elementi di $n$ non sarebbero coperti da elementi di $m$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo