2 Insiemi : Trovare le funzioni Surgettive.
Data la Vostra grande competenza e disponibilità chiedo: A = { cardinalità = 8 } , B { cardinalità = 3} Contare le funzioni surgettive. E le funzioni iniettive
Non avendo fatto il Numero di Stirling pensavo di contare le surgettive come differenza.
Mentre le iniettive sicuramente sono $ 0$ in quanto l'insieme B ha cardinalità < di A .
Le surgettive:
Tutte le funzioni $ 3^8 $ da A a B
ci togliamo : $ 3!$ cioè tutte le permutazioni del secondo insieme piu' piccolo.
Risultato finale : $3^8 - 6 $ = 6555
Non sono sicuro che il ragionamento sia giusto. Grazie dell'eventuale aiuto che mi vorrete dare.
Gdlan
Non avendo fatto il Numero di Stirling pensavo di contare le surgettive come differenza.
Mentre le iniettive sicuramente sono $ 0$ in quanto l'insieme B ha cardinalità < di A .
Le surgettive:
Tutte le funzioni $ 3^8 $ da A a B
ci togliamo : $ 3!$ cioè tutte le permutazioni del secondo insieme piu' piccolo.
Risultato finale : $3^8 - 6 $ = 6555
Non sono sicuro che il ragionamento sia giusto. Grazie dell'eventuale aiuto che mi vorrete dare.
Gdlan
Risposte
Ciao.
Purtroppo non ci siamo.
Chiama $A={1,2,3,4,5,6,7,8}$ e $B={x,y,z}$.
La cosa che ti conviene fare è contare le funzioni $A to B$ non suriettive. Poi togliendo questo numero da $3^8$ troverai il numero di quelle suriettive.
Una funzione $A to B$ non suriettiva ha sei possibili immagini: ${x},\ {y},\ {z},\ {x,y},\ {x,z},\ {y,z}$. Quante sono le funzioni in ciascun caso?
Purtroppo non ci siamo.
Chiama $A={1,2,3,4,5,6,7,8}$ e $B={x,y,z}$.
La cosa che ti conviene fare è contare le funzioni $A to B$ non suriettive. Poi togliendo questo numero da $3^8$ troverai il numero di quelle suriettive.
Una funzione $A to B$ non suriettiva ha sei possibili immagini: ${x},\ {y},\ {z},\ {x,y},\ {x,z},\ {y,z}$. Quante sono le funzioni in ciascun caso?
Giusto; le funzioni non surgettive sono quelle in cui il codominio non comprende tutti gli elementi di B e pertanto basta andare a considerare tutti i sottoinsiemi di 3 escludento l'insieme pieno (altrimenti sarebbero surgettive) e l'insieme vuoto e cioè :
$ (2^3) - 2$ = 6 insiemi dei codomini delle funzioni non surgettive. Ora devo pensare a quante funzioni vanno in ciascun insieme immagine. Sicuramente gli insiemi dei 6 non surgettivi di cardinalita' 1 hanno ciscuno 1 funzione : pertanto 1+1+1 = 3. Mentre le funzioni che vanno in insiemi con codominio non completo e che quindi danno funzioni non surgettive sono quelle che vanno nei tre insiemi composti da 2 elementi e che sono per ciascun insieme 2 (almeno credo) e quindi 3 * 2 = 6 .
Allora il risultato finale dovrebbe essere :
$ 3^8 - 3 - 6 $
Pero' non so ?
Gdlan grazie
Grazie Gdal
$ (2^3) - 2$ = 6 insiemi dei codomini delle funzioni non surgettive. Ora devo pensare a quante funzioni vanno in ciascun insieme immagine. Sicuramente gli insiemi dei 6 non surgettivi di cardinalita' 1 hanno ciscuno 1 funzione : pertanto 1+1+1 = 3. Mentre le funzioni che vanno in insiemi con codominio non completo e che quindi danno funzioni non surgettive sono quelle che vanno nei tre insiemi composti da 2 elementi e che sono per ciascun insieme 2 (almeno credo) e quindi 3 * 2 = 6 .
Allora il risultato finale dovrebbe essere :
$ 3^8 - 3 - 6 $
Pero' non so ?
Gdlan grazie
Grazie Gdal
3 va bene ma 6 decisamente no! rifletti!
i numeri di Stirling ti costringerebbero a contare le partizioni di un insieme di 8 elementi in tre parti.
ricondurti a questi sottocasi ti aiuta perché in tre parti è difficile contarle, ma comunque in due parti, cosa più semplice, devi farlo! in quanti modi puoi dividere in due parti un insieme di 8 elementi?
i numeri di Stirling ti costringerebbero a contare le partizioni di un insieme di 8 elementi in tre parti.
ricondurti a questi sottocasi ti aiuta perché in tre parti è difficile contarle, ma comunque in due parti, cosa più semplice, devi farlo! in quanti modi puoi dividere in due parti un insieme di 8 elementi?
Allora dovrebbe essere : Numero di Funzioni totali dedotto numero funzioni per sottoinsiemi di cardinalità (n-2) (quindi non suriettive) = 1 dedotto numero funzioni per sottoinsiemi di cardinalità (n-1) (ancora funzioni non suriettive) = 2.
Ed allora :
$ 3^(8) - 3( 1^(8)) - 3( 2^(8) ) = 3^(8) - 3 - 3*256 = 6561 - 3 - 768 = 6561- 771 = 5790 $ ?
Gdlan . ?
Ed allora :
$ 3^(8) - 3( 1^(8)) - 3( 2^(8) ) = 3^(8) - 3 - 3*256 = 6561 - 3 - 768 = 6561- 771 = 5790 $ ?
Gdlan . ?
aspetta, siccome il numero esatto è 5796, tu così stai applicando il principio d'inclusione-esclusione, dunque $3^8-3*2^8+3*1^8$, perché le prime comprendono anche le seconde e terze, tu ci togli le seconde che comprendono anche le terze, ci devi rimettere le terze... però è abbastanza cervellotico!
come diceva Martino e come tentavo di suggerirti io forse è più semplice...
come diceva Martino e come tentavo di suggerirti io forse è più semplice...
3^8 - 3 *1(8) -3*2^(8) = 5790 a questa cifra si riaggiungono il numero dei sottoinsiemi totali che vengono fuori dalla cardinalità dell'insieme di arrivo deducendo però l'insieme vuoto e l'insieme completo e quindi :
5790 + 2^(3) - 2 = 5796
Gentilmente volevo però capire bene il suo ragionamento al posto di quello del Sig. Martino.
Grazie per la sua spiegazione e per la sua eventuale conforme di quanto da me scritto sopra.
Infiniti ringraziamenti.
Gdlan
5790 + 2^(3) - 2 = 5796
Gentilmente volevo però capire bene il suo ragionamento al posto di quello del Sig. Martino.
Grazie per la sua spiegazione e per la sua eventuale conforme di quanto da me scritto sopra.
Infiniti ringraziamenti.
Gdlan
tre funzioni costanti, con immagini {x}, {y}, {z}, le hai sapute trovare da te.
per trovare quante funzioni hanno immagini di due elementi devi contare in quanti modi puoi suddividere l'insieme A in due parti.
se conti tutti i sottoinsiemi, $2^8$, questi li devi prendere "a coppie", un sottoinsieme con il suo complementare, dunque devi dividere per 2.
tieni conto che anche $A$ e $phi$ sono tra loro complementari, dunque, o li togli prima entrambi o togli 1 dal risultato della divisione: le partizioni di A in due parti sono $2^8 : 2 -1=2^7-1=127$ oppure $(2^8-2) : 2=254 : 2=127$. per ogni coppia della partizione, ci sono due scelte per l'immagine {x,y}, ad esempio,
dunque 127 va moltiplicato per 2 e per 3 (numero di sottoinsiemi di B di 2 elementi): $127*2*3=762$
in totale quindi $3^8-3-762=5796$
spero sia chiaro.
P.S.: qui al forum si usa darsi del tu...
ciao.
per trovare quante funzioni hanno immagini di due elementi devi contare in quanti modi puoi suddividere l'insieme A in due parti.
se conti tutti i sottoinsiemi, $2^8$, questi li devi prendere "a coppie", un sottoinsieme con il suo complementare, dunque devi dividere per 2.
tieni conto che anche $A$ e $phi$ sono tra loro complementari, dunque, o li togli prima entrambi o togli 1 dal risultato della divisione: le partizioni di A in due parti sono $2^8 : 2 -1=2^7-1=127$ oppure $(2^8-2) : 2=254 : 2=127$. per ogni coppia della partizione, ci sono due scelte per l'immagine {x,y}, ad esempio,
dunque 127 va moltiplicato per 2 e per 3 (numero di sottoinsiemi di B di 2 elementi): $127*2*3=762$
in totale quindi $3^8-3-762=5796$
spero sia chiaro.
P.S.: qui al forum si usa darsi del tu...
ciao.
Sei stata chiarissima e molto precisa. Grazie ancora. Ma comunque il mio ultimo ragionamento con il principio di inclusione-esclusione ( cioè il togliere e il riaggiungere l'insieme vuoto e quello completo) ti sembra giusto?
Grazie Gdlan.
Grazie Gdlan.
Io pensavo a una dimostrazione così:
Le funzioni con immagine contenuta in ${x,y}$ sono $2^8$.
Le funzioni con immagine contenuta in ${x,z}$ e non già considerate sono $2^8-1$ (ho tolto la funzione costante $x$).
Le funzioni con immagine contenuta in ${y,z}$ e non già considerate sono $2^8-2$ (ho tolto le funzioni costanti $y$ e $z$).
Quindi
il numero di funzioni non suriettive è $2^8+(2^8-1)+(2^8-2)=3(2^8-1)$,
il numero di funzioni suriettive è $3^8-3(2^8-1)$.
Ciao
Le funzioni con immagine contenuta in ${x,y}$ sono $2^8$.
Le funzioni con immagine contenuta in ${x,z}$ e non già considerate sono $2^8-1$ (ho tolto la funzione costante $x$).
Le funzioni con immagine contenuta in ${y,z}$ e non già considerate sono $2^8-2$ (ho tolto le funzioni costanti $y$ e $z$).
Quindi
il numero di funzioni non suriettive è $2^8+(2^8-1)+(2^8-2)=3(2^8-1)$,
il numero di funzioni suriettive è $3^8-3(2^8-1)$.
"GDLAN":Molto obbligato
Sig. Martino
Ciao
"GDLAN":
Sei stata chiarissima e molto precisa. Grazie ancora. Ma comunque il mio ultimo ragionamento con il principio di inclusione-esclusione ( cioè il togliere e il riaggiungere l'insieme vuoto e quello completo) ti sembra giusto?
Grazie Gdlan.
prego!
il ragionamento di togliere l'insieme vuoto e A è corretto.
io per inclusione-esclusione intendevo sull'insieme delle funzioni con diverse immagini.
più o meno è il discorso che ha fatto Martino quando nell'ultimo post non è partito dal contare le funzioni costanti ma quelle con "due immagini" e poi ha tolto quelle che si ripetevano.
più in grande, riprendendo la formula che avevi scritto tu e che io ho poi corretto cambiando un segno, prendiamo la totalità delle funzioni da A a B, poi ci togliamo le funzioni da A a {x,y}, quelle da A a {x,z}, quelle da A a {y,z}, così quelle costanti da A a {x} le abbiamo tolte 2 volte, e così pure da A a {y} e così pure da A a {z}, dunque ce le dobbiamo "ricontare una volta".
... francamente ho qualche dubbio che si possa fare altrettanto facilmente quando aumenta il numero degli elementi di B, perché così non servirebbero i numeri di Stirling ...
o magari il calcolo diventa talmente complicato che è meglio una formula ricorsiva...
cia!
Esiste una simpatica formula per calcolare le funzioni suriettive da un insieme $A$ di cardinalità finita $n$ ad un insieme $B$ di cardinalità finita $m$ con la condizione $m
$E(n,m)=\sum_{i=0}^{m-1}(-1)^{i}((m),(i))(m-i)^{n}$.
$E(n,m)=\sum_{i=0}^{m-1}(-1)^{i}((m),(i))(m-i)^{n}$.
è proprio questa del principio d'inclusione-esclusione!
allora funziona!
si trova in rete? dove l'hai trovata?
forse è nell'Oliforum? o l'hai studiata?
non è per caso quella di cui parlava Alvinlee88 un bel po' di tempo fa, no?
dal punto di vista pratico, è migliore della formula ricorsiva che fa uso dei numeri di Stirling?
allora funziona!
si trova in rete? dove l'hai trovata?
forse è nell'Oliforum? o l'hai studiata?
non è per caso quella di cui parlava Alvinlee88 un bel po' di tempo fa, no?
dal punto di vista pratico, è migliore della formula ricorsiva che fa uso dei numeri di Stirling?
Non è esattamente la formula del principio di inclusione esclusione: la formula del principio di inclusione-esclusione è quella nella mia firma. Questa formula è però strattamente legata a quella del principio di inclusione-esclusione e con esso si prova. L'ho studiata diversi mesi fa, ma per conto mio. Nel corso delle mie navigazioni per il web alla ricerca di appunti di ogni tipo, mi imbattei in questa simpatica dispensa, dove credo dovrebbe esserci risposta alle tue curiosità. La fomrula è a pag. 5 e la dimostrazione a pag. 6.
Sig. Martino e altri per cui se l'insieme di arrivo fosse di cardinalità 4 e quello di partenza sempre di 8 il totale delle surgettive sarebbe:
$ 4^(8) - 4*(3^8) - 4*(2^8)- 4 *(1^8) + 2^4 - 2 $
Torna?
Gdlan
$ 4^(8) - 4*(3^8) - 4*(2^8)- 4 *(1^8) + 2^4 - 2 $
Torna?
Gdlan
No: $4^8 - 4\cdot3^8 + 6\cdot2^8 - 4$.
[mod="Fioravante Patrone"]Mi spiace, ma i "furbi" qui non sono graditi:
https://www.matematicamente.it/forum/aa- ... tml#318587
[/mod]
https://www.matematicamente.it/forum/aa- ... tml#318587
[/mod]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo