Notifiche
Cancella tutti

[Risolto] Calcolare il numero di funzioni suriettive

  

0

Dati gli insiemi $A=\left\{a,b,c,d,e,f\right\}$, $B=\left\{x,y,z,w\right\}$

trovare il numero di funzioni suriettive $A \rightarrow B$.

Come si svolge un esercizio del genere?

Poco fa ne ho fatto uno simile ma il codominio aveva tre elementi ed ho ragionato con il complementare. Ho trovato il numero totale di funzioni ed ho calcolato tutte le funzioni non suriettive applicando il principio di inclusione-esclusione. Con la differenza ho trovato tutte le funzioni suriettive.

Ma qui gli elementi del codominio sono 4, non so dove mettere mano 🤔.

Come si procede?
Grazie in anticipo

Autore

In giro su internet ho trovato il principio di inclusione-esclusione per 4 insiemi.

$\begin{align} &|A\cup B\cup C\cup D|\\[3pt] &=|A|+|B|+|C|+|D|\Big\}\text{ all singletons}\\ &-(|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+|B\cap D|+|C\cap D|)\Big\}\text{ all pairs}\\ &+(|A\cap B\cap C|+|A\cap B\cap D|+|A\cap C\cap D|+|B\cap C\cap D|)\Big\}\text{ all triples}\\ &-|A\cap B\cap C\cap D|\Big\}\text{ all quadruples}\\ \end{align}$

Dovrei applicare tutta sta roba? 🤨 

Etichette discussione
3 Risposte
2

Ti occorrono tutte le funzioni che da 6 elementi ti mandino in 4 elementi.

Allora hai C(6,4) modi in cui puoi scegliere in A gli elementi a cui attribuire una immagine in B

e per ognuno di questi puoi permutare le 4 immagini in 4! = 24 modi. E 15 x 24 = 360.

Al quinto e sesto elemento rimasto in A puoi associare una qualunque delle 4 immagini di B

ma ( a rigore ) anche nessuna perché ciò non contraddice la definizione di funzione.

 

Allora 5*5 * 360 = 9000

Se la traccia insiste che ogni elemento deve avere una immagine, allora 16*360 = 5760.




0

Nella frase definitoria di A → B
* "ogni elemento del codominio è immagine di almeno un elemento del dominio"
la costruzione con l'avverbio è un'alternativa a quella con la disgiunzione (vel, non aut!)
* "ogni elemento del codominio è immagine di uno o più elementi del dominio"; e, se si tratta di "più elementi", è irrilevante l'ordine in cui li si elenca.
---------------
Con
* A = {a, b, c, d, e, f}
* |A| = 6
* B = {w, x, y, z}
* |B| = 4
per ciascun elemento immagine (|B|*) ci può essere, come insieme argomento, un qualsiasi sottinsieme non vuoto di A (quasi tutto l'insieme delle parti: 2^|A| - 1).
In tutto
* |B|*(2^|A| - 1) = 4*(2^6 - 1) = 252

0

 

@iloveyou

Per definizione di funzione: tutti gli elementi di A quindi n=6 devono essere impegnati nel legame

A--->B con 1 solo elemento di B; per essere suriettiva la funzione deve essere tale per cui ogni elemento di B quindi m= 4 deve essere immagine di almeno un elemento di A.

A ha cardinalità pari a 6

B ha cardinalità pari a 4

L’idea di calcolare tutte le funzione suriettive ovviamente con n ≥ m è quella di introdurre

la funzione   Sur (n,m) . Tale funzione calcola il numero delle funzioni suriettive f di A in B con le seguenti relazioni:

Sur(n,1)=1

Sur(n,2)=2^n-2

Sur(n,3)=3^n-3*2^n+3

Sur(n,4)=4^n-4*3^n+6*2^n-4

Sur(n,5)=5^n-5*4^n+10*3^n-10*2^n+5

N.B. Osservare che appare il triangolo di Tartaglia

Nel nostro caso:

Sur(6,4)= 4^6 - 4·3^6 + 6·2^6 - 4 = 1560

Vedi articolo:






About SosMatematica

Seguici su:

Scarica la nostra App Ufficiale

SOS Matematica

GRATIS
Download