Funzioni tra insiemi finiti
Siano A e B due insiemi finiti ($|A|=m$, $|B|=n$, con $m, n in NN$).
Determinare:
1) il numero delle relazioni binarie da A a B;
2) il numero delle funzioni da A a B;
3) il numero delle funzioni biunivoche da A a B;
4) il numero delle funzioni iniettive da A a B;
5) il numero delle funzioni suriettive da A a B.
N.B.: distinguere, ove opportuno, i casi $m=n$, $mn$; trattare eventualmente a parte i casi in cui $m$ e/o $n$ siano uguali a zero.
Il quesito è piuttosto elementare, a livello di scuola superiore, per i primi quattro punti; il quinto punto è a livello universitario.
Oltre alle soluzioni da parte di chi intende cimentarsi, si attendono osservazioni.
Determinare:
1) il numero delle relazioni binarie da A a B;
2) il numero delle funzioni da A a B;
3) il numero delle funzioni biunivoche da A a B;
4) il numero delle funzioni iniettive da A a B;
5) il numero delle funzioni suriettive da A a B.
N.B.: distinguere, ove opportuno, i casi $m=n$, $m
Il quesito è piuttosto elementare, a livello di scuola superiore, per i primi quattro punti; il quinto punto è a livello universitario.
Oltre alle soluzioni da parte di chi intende cimentarsi, si attendono osservazioni.
Risposte
1) il numero di relazioni binarie da A a B è l'insieme di coppie (a,b) | a$in$A, b$in$B.
Quindi si hanno $m*n$ relazioni binarie da A a B.
2) una funzione da A a B è un sottoinsieme f di $AxxB$ | per ogni a$in$A, esiste uno ed un solo elemento b$in$B tale che $(a,b)$$in$f .
Per ogni elemento $a_1,a_2,a_3,...,a_m$ in A ci sono n valori del suo corrispondente in B, quindi si hanno $n*n*n*...$ (con m fattori)= $n^m$ funzioni da A a B.
3) una funzione è biunivoca se ad ogni elemento di A corrisponde uno ed uno solo elemento di B, e viceversa.
Se m
Se m=n, per l'elemento $a_1$ si hanno n possibili valori del suo corrispondente in B, per $a_2$ si hanno n-1 valori,...., per $a_m$ si ha 1 solo valore possibile.
Quindi si hanno $m!$=$n!$ funzioni biunivoche.
4) una funzione è iniettiva se ad ogni elemento di B corrisponde al più un elemento di A.
Se m>n la definizione di funzione iniettiva non vale.
Se m
Se m=n si hanno $n!$ funzioni iniettive.
5)vediamo se riesco a pensarci più tardi, ora devo scappare.
Quindi si hanno $m*n$ relazioni binarie da A a B.
2) una funzione da A a B è un sottoinsieme f di $AxxB$ | per ogni a$in$A, esiste uno ed un solo elemento b$in$B tale che $(a,b)$$in$f .
Per ogni elemento $a_1,a_2,a_3,...,a_m$ in A ci sono n valori del suo corrispondente in B, quindi si hanno $n*n*n*...$ (con m fattori)= $n^m$ funzioni da A a B.
3) una funzione è biunivoca se ad ogni elemento di A corrisponde uno ed uno solo elemento di B, e viceversa.
Se m
Se m=n, per l'elemento $a_1$ si hanno n possibili valori del suo corrispondente in B, per $a_2$ si hanno n-1 valori,...., per $a_m$ si ha 1 solo valore possibile.
Quindi si hanno $m!$=$n!$ funzioni biunivoche.
4) una funzione è iniettiva se ad ogni elemento di B corrisponde al più un elemento di A.
Se m>n la definizione di funzione iniettiva non vale.
Se m
Se m=n si hanno $n!$ funzioni iniettive.
5)vediamo se riesco a pensarci più tardi, ora devo scappare.
considera che l'insieme delle funzioni è un sottoinsieme dell'insieme delle relazioni... quindi, essendo esatti i punti 2, 3, 4, non può essere esatto il punto 1:
m*n è solo il numero di elementi del prodotto cartesiano... ciao.
m*n è solo il numero di elementi del prodotto cartesiano... ciao.
"adaBTTLS":
considera che l'insieme delle funzioni è un sottoinsieme dell'insieme delle relazioni... quindi, essendo esatti i punti 2, 3, 4, non può essere esatto il punto 1:
m*n è solo il numero di elementi del prodotto cartesiano... ciao.
Ok.
Dunque, il prodotto cartesiano è definito come $AxxB$=${(a,b) | a in A,b in B}$; la relazione binaria è un qualunque sottoinsieme del prodotto cartesiano, quindi devo contare tutti i possibili sottoinsiemi per sapere il numero di relazioni binarie.
Sapendo che ho m*n possibili coppie (a,b), devo contare il numero di modi di selezionare una coppia tra le m*n coppie, il numero di modi di selezionare 2 coppie e via dicendo.
Quindi $\sum_{k=0}^(m*n) ((m*n),(k))$, dove $((m*n),(k))$ indica i sottoinsiemi di k delle n*m coppie.
sì, ma non hai intenzione di lasciarlo così.... eppure è una formula nota.... quanti sono i sottoinsiemi di un insieme avente (mn) elementi?
"adaBTTLS":
sì, ma non hai intenzione di lasciarlo così.... eppure è una formula nota.... quanti sono i sottoinsiemi di un insieme avente (mn) elementi?
... $2^(nm)$
OK. mentre il n.5 non è così semplice... ciao.
Riguardando i miei appunti di aritmetica (e in rete) cercando i numeri di stirling, ho trovato anche il quesito 5. Potrei darvi semplicemente il link, ma dato che è per me un utile esercizio riscrivere la soluzione (senza guardare ovviamente negli appunti), eccovela.
Chiamiamo $b_1,b_2,...,b_(m-1)$ gli $m$ elementi di $B$.
il numero cercato è $n^m$ (tutte le funzioni) - $|X|$, dove $X={f:A->B|$f non suriettiva$}$.
Sia $X_i={f:A->B|b_i notin Im(f)}={f:A->B|AA a inA f(a)!=b_i}$, ossia l'insieme costituito dalle funzioni che "non raggiungono" $b_i$ (che non hanno $b_i$ nell'immagine).Il nostro insieme $X$, cioè le funzioni non suriettive, è uguale a $X_1uuX_2uu...uuX_m$.
La cardinalità di $X_1$ è $(m-1)^n$, ossia il numero di funzioni da $A$ in $B-{b_1}$, quella di $X_1nnX_2$ è $(m-2)^n$, ossia il numero di funzioni da $A$ in $B-{b_1,b_2}$. Per ogni $1<=i<=m$ si ha dunque $|X_1nn...nnX_i|=(m-i)^n$.
Per il principio di inclusione esclusione, $|X_1uu...uuX_m|=sum_{k=1}^{m} |X_i|-sum_{{i_1,i_2}sube{1,...,m}}|X_i_1nnX_i_2|+sum_{{i_1,i_2,i_3}sube{1,...,m}} |X_i_1nnX_i_2nnX_i_3|+...+(-1)^(m-1)|nnn_{i=1}^{m-1} X_i|$.
Ora per semplicità di notazione poniamo per ogni $k<=m$ $I_k={i_1,...i_k}$. Si ha che per ogni $k$
$sum_{I_ksube{1,..,m}}|nnn_{isubeI_k}X_i|$=$((m),(k))*(m-k)^n$,
ossia il numero di sottoinsiemi $I_k$ di ${1,...m}$ moltiplicato il valore costante (con k fissato) $(m-k)^n$.
Di conseguenza
$m^n-|X_1uu...uuX_m|=m^n-((m),(1))*(m-1)^n+((m),(2))*(m-2)^n+...+(-1)^n((m),(m))1^n$ che si può scrivere in modo compatto come
$sum_{k=0}^{m}(-1)^k*((m),(k))*(m-k)^n$.
Spero di essere stato utile.
ciao
Chiamiamo $b_1,b_2,...,b_(m-1)$ gli $m$ elementi di $B$.
il numero cercato è $n^m$ (tutte le funzioni) - $|X|$, dove $X={f:A->B|$f non suriettiva$}$.
Sia $X_i={f:A->B|b_i notin Im(f)}={f:A->B|AA a inA f(a)!=b_i}$, ossia l'insieme costituito dalle funzioni che "non raggiungono" $b_i$ (che non hanno $b_i$ nell'immagine).Il nostro insieme $X$, cioè le funzioni non suriettive, è uguale a $X_1uuX_2uu...uuX_m$.
La cardinalità di $X_1$ è $(m-1)^n$, ossia il numero di funzioni da $A$ in $B-{b_1}$, quella di $X_1nnX_2$ è $(m-2)^n$, ossia il numero di funzioni da $A$ in $B-{b_1,b_2}$. Per ogni $1<=i<=m$ si ha dunque $|X_1nn...nnX_i|=(m-i)^n$.
Per il principio di inclusione esclusione, $|X_1uu...uuX_m|=sum_{k=1}^{m} |X_i|-sum_{{i_1,i_2}sube{1,...,m}}|X_i_1nnX_i_2|+sum_{{i_1,i_2,i_3}sube{1,...,m}} |X_i_1nnX_i_2nnX_i_3|+...+(-1)^(m-1)|nnn_{i=1}^{m-1} X_i|$.
Ora per semplicità di notazione poniamo per ogni $k<=m$ $I_k={i_1,...i_k}$. Si ha che per ogni $k$
$sum_{I_ksube{1,..,m}}|nnn_{isubeI_k}X_i|$=$((m),(k))*(m-k)^n$,
ossia il numero di sottoinsiemi $I_k$ di ${1,...m}$ moltiplicato il valore costante (con k fissato) $(m-k)^n$.
Di conseguenza
$m^n-|X_1uu...uuX_m|=m^n-((m),(1))*(m-1)^n+((m),(2))*(m-2)^n+...+(-1)^n((m),(m))1^n$ che si può scrivere in modo compatto come
$sum_{k=0}^{m}(-1)^k*((m),(k))*(m-k)^n$.
Spero di essere stato utile.
ciao
... mamma mia... non avevo visto prima questa risposta... chi ha proposto questa soluzione?
ti sei divertito per caso a controllare l'esattezza dei risultati per qualche caso particolare?
il ragionamento che porta ad usare i numeri di Stirling è semplicissimo... ma non nel senso che uno conosce l'argomento ed associa il significato dei numeri di Stirling a quello che deve trovare.... è molto più semplice: ragionando si arriva a "ricavare" la formula ricorsiva che dà i numeri di Stirling.
sia A un insieme di n elementi, e sia B un insieme di m elementi. allora, se n
allora, se suddividiamo l'insieme A in m parti non vuote e a due a due disgiunte, possiamo definire una funzione suriettiva assegnando come immagine di ciascuno di tali sottoinsiemi un determinato sottoinsieme costituito da un unico elemento di B. dato che è indifferente quale elemento di B associamo ad un sottoinsieme della partizione di A, allora il numero delle funzioni suriettive da A a B è $m!*S(n,m)$,
dove con S(n,m) per ora intendiamo solo "il numero delle partizioni di un n-insieme in m parti". vogliamo ricavare S(n,m) al variare di n ed m.
sulle condizioni di partenza penso ci sia poco da discutere:
S(n,0)=0, S(n,1)=S(n,n)=1, S(n,k)=0 se k>n, dunque S(n,m) è diverso da 0 se m è compreso tra 1 e n.
S(1,1)=1
S(2,1)=1, S(2,2)=1
S(3,1)=1, S(3,2)=3, S(3,3)=1
abbiamo finora ottenuto solo S(3,2)=3 non banale: in quanti modi può essere suddiviso un insieme di tre elementi in due parti non vuote e disgiunte?
1\2,3 1,2\3 1,3\2
ora ci chiediamo: se siamo riusciti a riempire fino alla riga n-esima, come possiamo riempire la riga (n+1)-esima?
allora, avendo un insieme di (n+1) elementi, come lo possiamo suddividere in k parti?
possiamo rispondere a questa domanda se teniamo presente che l'elemento in più può essere inserito in uno dei k sottoinsiemi di una partizione degli altri n oppure può essere un elemento che forma un sottoinsieme a sé, andandosi ad aggiungere ad altri (k-1) sottoinsiemi di una partizione degli altri n:
di qui la formula ricorsiva $S(n+1, k)=S(n, k-1)+k*S(n, k)$
non so se è sufficientemente chiaro. non so neppure quale metodo ti possa sembrare più semplice.
pensa che se parti dalle suddivisioni di un n-insieme in (k-1) parti, aggiungi un elemento isolato; se invece parti dalle suddivisioni di un n-insieme in k parti, l'ultimo elemento lo devi inserire in uno dei sottoinsiemi già presenti, e puoi farlo in k modi.
spero di essere stata utile. ciao.
ti sei divertito per caso a controllare l'esattezza dei risultati per qualche caso particolare?
il ragionamento che porta ad usare i numeri di Stirling è semplicissimo... ma non nel senso che uno conosce l'argomento ed associa il significato dei numeri di Stirling a quello che deve trovare.... è molto più semplice: ragionando si arriva a "ricavare" la formula ricorsiva che dà i numeri di Stirling.
sia A un insieme di n elementi, e sia B un insieme di m elementi. allora, se n
allora, se suddividiamo l'insieme A in m parti non vuote e a due a due disgiunte, possiamo definire una funzione suriettiva assegnando come immagine di ciascuno di tali sottoinsiemi un determinato sottoinsieme costituito da un unico elemento di B. dato che è indifferente quale elemento di B associamo ad un sottoinsieme della partizione di A, allora il numero delle funzioni suriettive da A a B è $m!*S(n,m)$,
dove con S(n,m) per ora intendiamo solo "il numero delle partizioni di un n-insieme in m parti". vogliamo ricavare S(n,m) al variare di n ed m.
sulle condizioni di partenza penso ci sia poco da discutere:
S(n,0)=0, S(n,1)=S(n,n)=1, S(n,k)=0 se k>n, dunque S(n,m) è diverso da 0 se m è compreso tra 1 e n.
S(1,1)=1
S(2,1)=1, S(2,2)=1
S(3,1)=1, S(3,2)=3, S(3,3)=1
abbiamo finora ottenuto solo S(3,2)=3 non banale: in quanti modi può essere suddiviso un insieme di tre elementi in due parti non vuote e disgiunte?
1\2,3 1,2\3 1,3\2
ora ci chiediamo: se siamo riusciti a riempire fino alla riga n-esima, come possiamo riempire la riga (n+1)-esima?
allora, avendo un insieme di (n+1) elementi, come lo possiamo suddividere in k parti?
possiamo rispondere a questa domanda se teniamo presente che l'elemento in più può essere inserito in uno dei k sottoinsiemi di una partizione degli altri n oppure può essere un elemento che forma un sottoinsieme a sé, andandosi ad aggiungere ad altri (k-1) sottoinsiemi di una partizione degli altri n:
di qui la formula ricorsiva $S(n+1, k)=S(n, k-1)+k*S(n, k)$
non so se è sufficientemente chiaro. non so neppure quale metodo ti possa sembrare più semplice.
pensa che se parti dalle suddivisioni di un n-insieme in (k-1) parti, aggiungi un elemento isolato; se invece parti dalle suddivisioni di un n-insieme in k parti, l'ultimo elemento lo devi inserire in uno dei sottoinsiemi già presenti, e puoi farlo in k modi.
spero di essere stata utile. ciao.
Quella che ho scritto io è stata una lezione di aritmetica (la seconda mi sembra), a quel tempo non si era ancora parlato di partizioni. La relazione poi con i numeri di Stirling è come hai detto te: data una funzione $f$ surgettiva da $A$ in$B={b_1,...,b_(m-1)}$, con $|A|=n$ e $|B|=m$, resta individuata naturalmente una partizione di $A$, formata dalle $m$ immagini inverse secondo $f$ dei sottoinsiemi costituiti da un unico elemento di $B$. La partizione è più precisamente $A'={A_b_i|b_i inB}$, con $A_b_i={ain A|f(a)=b_i}$. Gli $A_b_i$ sono a due a due disgiunti per costruzione, e la loro unione da tutto $A$. Poichè però la stessa partizione così definita è individuata da $m!$ diverse funzioni suriettive, indicato con $E(n,m)$ il numero di funzioni suriettive da $A$ a $B$, si ha che il numero di m-partizioni di un insieme $A$ con $n$ elementi è $S(n,m)=(E(n,m))/(m!)$.
In questo modo si ottengono i numeri di Stirling (che prima ignoravo cosa fossero) senza formule ricorsive, usando la formula del mio post precedente.
Ripeto, ho proposto quella soluzione perchè mi è più naturale pensarla così: trovare il numero di funzioni suriettive, poi introdurre il concetto di partizione, e poi sfruttare quel risultato per trovare il numero di m-partizioni di un insieme.
Ciao
In questo modo si ottengono i numeri di Stirling (che prima ignoravo cosa fossero) senza formule ricorsive, usando la formula del mio post precedente.
Ripeto, ho proposto quella soluzione perchè mi è più naturale pensarla così: trovare il numero di funzioni suriettive, poi introdurre il concetto di partizione, e poi sfruttare quel risultato per trovare il numero di m-partizioni di un insieme.
Ciao
grazie mille. ciao.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo