2 Insiemi : Trovare le funzioni Surgettive.

[GDLAN]

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 \( \displaystyle {0} \) in quanto l'insieme B ha cardinalità < di A .

Le surgettive:

Tutte le funzioni \( \displaystyle {{3}}^{{8}} \) da A a B

ci togliamo : \( \displaystyle {3}! \) cioè tutte le permutazioni del secondo insieme piu' piccolo.

Risultato finale : \( \displaystyle {{3}}^{{8}}-{6} \) = 6555

Non sono sicuro che il ragionamento sia giusto. Grazie dell'eventuale aiuto che mi vorrete dare.

Gdlan

[Martino]

Ciao.

Purtroppo non ci siamo.

Chiama \( \displaystyle {A}={\left\lbrace{1},{2},{3},{4},{5},{6},{7},{8}\right\rbrace} \) e \( \displaystyle {B}={\left\lbrace{x},{y},{z}\right\rbrace} \).

La cosa che ti conviene fare è contare le funzioni \( \displaystyle {A}\to{B} \) non suriettive. Poi togliendo questo numero da \( \displaystyle {{3}}^{{8}} \) troverai il numero di quelle suriettive.

Una funzione \( \displaystyle {A}\to{B} \) non suriettiva ha sei possibili immagini: \( \displaystyle {\left\lbrace{x}\right\rbrace},\ {\left\lbrace{y}\right\rbrace},\ {\left\lbrace{z}\right\rbrace},\ {\left\lbrace{x},{y}\right\rbrace},\ {\left\lbrace{x},{z}\right\rbrace},\ {\left\lbrace{y},{z}\right\rbrace} \). Quante sono le funzioni in ciascun caso?

[GDLAN]

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è :

\( \displaystyle {\left({{2}}^{{3}}\right)}-{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 :

\( \displaystyle {{3}}^{{8}}-{3}-{6} \)

Pero' non so ?
Gdlan grazie

Grazie Gdal

[adaBTTLS]

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?

[GDLAN]

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 :

\( \displaystyle {{3}}^{{{8}}}-{3}{\left({{1}}^{{{8}}}\right)}-{3}{\left({{2}}^{{{8}}}\right)}={{3}}^{{{8}}}-{3}-{3}\cdot{256}={6561}-{3}-{768}={6561}-{771}={5790} \) ?

Gdlan . ?

[adaBTTLS]

aspetta, siccome il numero esatto è 5796, tu così stai applicando il principio d'inclusione-esclusione, dunque \( \displaystyle {{3}}^{{8}}-{3}\cdot{{2}}^{{8}}+{3}\cdot{{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...

[GDLAN]

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

[adaBTTLS]

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, \( \displaystyle {{2}}^{{8}} \), questi li devi prendere "a coppie", un sottoinsieme con il suo complementare, dunque devi dividere per 2.
tieni conto che anche \( \displaystyle {A} \) e \( \displaystyle \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 \( \displaystyle {{2}}^{{8}}:{2}-{1}={{2}}^{{7}}-{1}={127} \) oppure \( \displaystyle {\left({{2}}^{{8}}-{2}\right)}:{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): \( \displaystyle {127}\cdot{2}\cdot{3}={762} \)
in totale quindi \( \displaystyle {{3}}^{{8}}-{3}-{762}={5796} \)
spero sia chiaro.

P.S.: qui al forum si usa darsi del tu...
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.

[Martino]

Io pensavo a una dimostrazione così:

Le funzioni con immagine contenuta in \( \displaystyle {\left\lbrace{x},{y}\right\rbrace} \) sono \( \displaystyle {{2}}^{{8}} \).

Le funzioni con immagine contenuta in \( \displaystyle {\left\lbrace{x},{z}\right\rbrace} \) e non già considerate sono \( \displaystyle {{2}}^{{8}}-{1} \) (ho tolto la funzione costante \( \displaystyle {x} \)).

Le funzioni con immagine contenuta in \( \displaystyle {\left\lbrace{y},{z}\right\rbrace} \) e non già considerate sono \( \displaystyle {{2}}^{{8}}-{2} \) (ho tolto le funzioni costanti \( \displaystyle {y} \) e \( \displaystyle {z} \)).

Quindi
il numero di funzioni non suriettive è \( \displaystyle {{2}}^{{8}}+{\left({{2}}^{{8}}-{1}\right)}+{\left({{2}}^{{8}}-{2}\right)}={3}{\left({{2}}^{{8}}-{1}\right)} \),
il numero di funzioni suriettive è \( \displaystyle {{3}}^{{8}}-{3}{\left({{2}}^{{8}}-{1}\right)} \).

Sig. Martino

Molto obbligato
Ciao