Funzioni iniettive e suriettive
Quante funzioni iniettive ci sono $ f[3] rarr [4] $ ci sono?
Sinceramente non so bene come muovermi con questi esercizi, io credo ci siano 4 funzioni, perché sono 4 gli elementi del codominio.
Quante funzioni suriettive ci sono $ f[4] rarr [3] $ ci sono?
Per essere suriettiva ogni elemento del codominio deve essere l'immagine di qualche elemento del dominio, quindi anche in questo caso direi 4.
Sono giusti?
(forse ho sbagliato categoria, ma è un esercizio che mi è capitato preparando l'esame di Matematica Discreta)
Sinceramente non so bene come muovermi con questi esercizi, io credo ci siano 4 funzioni, perché sono 4 gli elementi del codominio.
Quante funzioni suriettive ci sono $ f[4] rarr [3] $ ci sono?
Per essere suriettiva ogni elemento del codominio deve essere l'immagine di qualche elemento del dominio, quindi anche in questo caso direi 4.
Sono giusti?
(forse ho sbagliato categoria, ma è un esercizio che mi è capitato preparando l'esame di Matematica Discreta)
Risposte
Il numero di funzioni iniettive tra due insiemi finiti si ottiene così: diciamo che $f : [m] \to [n]$ e $m\le n$ (altrimenti ce ne sono zero). $f$ induce una biiezione con la sua immagine, quindi scegliere la sua immagine equivale a scegliere un sottoinsieme di $[n]$ che ha $[m]$ elementi. Questo si fa in
\[
\binom{n}{m} = \frac{n!}{m!(n-m)!}
\] modi. Adesso, chiaramente, ogni permutazione di questi $m$ elementi (che sono precisamente \(f(1),\dots, f(m)\)) dà luogo a una funzione differente, e ancora iniettiva: devi quindi moltiplicare quel numero per $m!$. La risposta è dunque
\[
m!\binom{n}{m} = \frac{n!}{(n-m)!}
\]
\[
\binom{n}{m} = \frac{n!}{m!(n-m)!}
\] modi. Adesso, chiaramente, ogni permutazione di questi $m$ elementi (che sono precisamente \(f(1),\dots, f(m)\)) dà luogo a una funzione differente, e ancora iniettiva: devi quindi moltiplicare quel numero per $m!$. La risposta è dunque
\[
m!\binom{n}{m} = \frac{n!}{(n-m)!}
\]
Senza scomodare il coefficiente binomiale, potrebbe funzionare questo ragionamento ?
Per determinare il numero di funzioni iniettive.
Dati i due insiemi $\mathbb{A}$ e $\mathbb{B}$ con cardinalità rispettivamente $m$ e $n$, $m<=n$.
Allora posso scegliere $n$ elementi di $\mathbb{B}$ come immagine del primo elemento di $\mathbb{A}$, poi posso scegliere $n-1$ (perché escludo quello già preso, altrimenti perdo l'iniettività) elementi di $\mathbb{B}$ come immagine del secondo elemento di $\mathbb{A}$, e cosi via...
Cosi ho $n(n-1)(n-2) \cdot \cdot \cdot (n-m+1)$ possibili funzioni iniettive $f:\mathbb{A} \rightarrow \mathbb{B}$
Nel caso specifico $4(4-1)(4-2)=24$
Per determinare il numero di funzioni iniettive.
Dati i due insiemi $\mathbb{A}$ e $\mathbb{B}$ con cardinalità rispettivamente $m$ e $n$, $m<=n$.
Allora posso scegliere $n$ elementi di $\mathbb{B}$ come immagine del primo elemento di $\mathbb{A}$, poi posso scegliere $n-1$ (perché escludo quello già preso, altrimenti perdo l'iniettività) elementi di $\mathbb{B}$ come immagine del secondo elemento di $\mathbb{A}$, e cosi via...
Cosi ho $n(n-1)(n-2) \cdot \cdot \cdot (n-m+1)$ possibili funzioni iniettive $f:\mathbb{A} \rightarrow \mathbb{B}$
Nel caso specifico $4(4-1)(4-2)=24$
l'argomento che hai dato tu dimostra elementarmente lo stesso asserto.E' solo un'opinione personale, ma fare una dimostrazione nasconendo la nomenclatura inserita nelle definizioni è essere tonti, non è "non scomodare i coefficienti binomiali". Le definizioni sono fatte, in fin dei conti, proprio per semplificare il discorso di una dimostrazione.
Ok, capisco. Volevo solo comprendere se la questione potesse essere risolta con questo approccio. Grazie comunque 
Oh, riprendendo in mano un testo mi è capitato di leggere questo esempio:
Per $|A|=3=n$ e $|B|=5=m$ ci sono $5 \cdot 4 = 20$ funzioni iniettive da $A$ in $B$.
Ora, probabilmente ho la vista appannata, perché le funzioni iniettive da $A$ in $B$, per quanto dicevamo sopra, dovrebbero essere
$m(m-1)(m-2) \cdot\cdot\cdot (m-n+1)$ quindi
$5 \cdot (5-1) \cdot (5-2) = 5 \cdot 4 \cdot 3 = 60$
Eppure non può esserci un errore nel testo !?
Per $|A|=3=n$ e $|B|=5=m$ ci sono $5 \cdot 4 = 20$ funzioni iniettive da $A$ in $B$.
Ora, probabilmente ho la vista appannata, perché le funzioni iniettive da $A$ in $B$, per quanto dicevamo sopra, dovrebbero essere
$m(m-1)(m-2) \cdot\cdot\cdot (m-n+1)$ quindi
$5 \cdot (5-1) \cdot (5-2) = 5 \cdot 4 \cdot 3 = 60$
Eppure non può esserci un errore nel testo !?
"algibro":
funzioni inattive [...] funzioni infettive
Nessuna di queste due cose sembra un attributo molto bello per una funzione...
hahahaha ommiodio, correggo immediatamente.
ps. come si disattiva questo maledetto correttore automatico ?
ps. come si disattiva questo maledetto correttore automatico ?
"algibro":
Oh, riprendendo in mano un testo mi è capitato di leggere questo esempio:
Per $|A|=3=n$ e $|B|=5=m$ ci sono $5 \cdot 4 = 20$ funzioni iniettive da $A$ in $B$.
Ora, probabilmente ho la vista appannata, perché le funzioni iniettive da $A$ in $B$, per quanto dicevamo sopra, dovrebbero essere
$m(m-1)(m-2) \cdot\cdot\cdot (m-n+1)$ quindi
$5 \cdot (5-1) \cdot (5-2) = 5 \cdot 4 \cdot 3 = 60$
Eppure non può esserci un errore nel testo !?
Se dice questo, il libro sbaglia
Ok, grazie 
Giusto come nota, si tratta di "Un invito all'algebra" di Leonesi Toffalori, pag.30.
Giusto come nota, si tratta di "Un invito all'algebra" di Leonesi Toffalori, pag.30.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo