Esercizio algebra/combinatoria
We 
si considerino due insiemi $A,B$ di elementi rispettivamente $n,m$.
Se è $nleqm$(si spieghi perché) si contino le funzioni iniettive tra $A$ e $B$
Il 'si spieghi perché' è abbastanza semplice, infatti se $n>m$ dovendo assegnare ad ogni $ainA$ l'unico elemento $binB$ si avrebbe che una volta assegnati $m$ elementi dell'insieme $A$, ne rimarrebbero ancora $n-m$ e dovendo assegnare anche quelli, si verrebbe meno alla definizione di funzione.
Per contare le funzioni iniettive, ho pensato di ragionare così:
$A={1,2,3,...,n}$ e $B={1,2,3,...,m}$
Dovendo essere ogni elemento di $B$ immagine di un solo elemento di $A$ voglio che ogni volta scelto un $binB$ io possa avere a disposizione $n-1$ elementi di $B$ per ogni $b$ che scelgo.
Questo equivale a $D_(m,n)=(m!)/((m-n)!)$
ovvero le funzioni iniettive tra due insiemi sono esattamente:
$(m!)/((m-n)!)=m(m-1)(m-2)*....*(m-n+1)$
si considerino due insiemi $A,B$ di elementi rispettivamente $n,m$.
Se è $nleqm$(si spieghi perché) si contino le funzioni iniettive tra $A$ e $B$
Il 'si spieghi perché' è abbastanza semplice, infatti se $n>m$ dovendo assegnare ad ogni $ainA$ l'unico elemento $binB$ si avrebbe che una volta assegnati $m$ elementi dell'insieme $A$, ne rimarrebbero ancora $n-m$ e dovendo assegnare anche quelli, si verrebbe meno alla definizione di funzione.
Per contare le funzioni iniettive, ho pensato di ragionare così:
$A={1,2,3,...,n}$ e $B={1,2,3,...,m}$
Dovendo essere ogni elemento di $B$ immagine di un solo elemento di $A$ voglio che ogni volta scelto un $binB$ io possa avere a disposizione $n-1$ elementi di $B$ per ogni $b$ che scelgo.
Questo equivale a $D_(m,n)=(m!)/((m-n)!)$
ovvero le funzioni iniettive tra due insiemi sono esattamente:
$(m!)/((m-n)!)=m(m-1)(m-2)*....*(m-n+1)$
Risposte
"anto_zoolander":
Il 'si spieghi perché' è abbastanza semplice, infatti se $n>m$ dovendo assegnare ad ogni $ainA$ l'unico elemento $binB$ si avrebbe che una volta assegnati $m$ elementi dell'insieme $A$, ne rimarrebbero ancora $n-m$ e dovendo assegnare anche quelli, si verrebbe meno alla definizione di funzione.
\( A = \{ a,b,c \} \)
\( B = \{ 0,1 \} \)
\( f \colon A \to B \) t.c. \( f(a) = f(b) = 0 \land f(c) = 1 \)
Questa dunque non è una funzione?
Ma la funzione deve essere iniettiva 
PS: obv quello che hai citato, da me scritto, vale solo per il caso $f$ iniettiva eh.
PS: obv quello che hai citato, da me scritto, vale solo per il caso $f$ iniettiva eh.
Hai [tex]\binom{m}{n}[/tex] scelte per l'immagine
e ci sono $n!$ biiezioni sull'immagine,
quindi il numero è [tex]\binom{m}{n} n![/tex] cioè quello che hai scritto.
e ci sono $n!$ biiezioni sull'immagine,
quindi il numero è [tex]\binom{m}{n} n![/tex] cioè quello che hai scritto.
"anto_zoolander":
Ma la funzione deve essere iniettiva
PS: obv quello che hai citato, da me scritto, vale solo per il caso $f$ iniettiva eh.
Lo so.
Tu però hai scritto
"anto_zoolander":
verrebbe meno alla definizione di funzione.
Chiedo che mi venga accordato il perdono 
sapete dove posso prendere delle ottime dispense sul calcolo combinatorio? Sopratutto con qualche teorema.
E come si contano quelle suriettive? Ricordo che ci avevo pensato ma è un problema difficile?
"Martino":
E come si contano quelle suriettive? Ricordo che ci avevo pensato ma è un problema difficile?
Se si è alle prime armi sì, si può risolvere applicando il principio di inclusione-esclusione.
Come?
Non vorrei dire una fesseria, però 'penso' sia:
Dati due insiemi $A,B$ con rispettivamente $n,m$ elementi e $mleqn$ le funzioni suriettive sono:
$D'_(m,n)-sum_{p=1}^{m-1}D'_(p,n)$
Non ne sono sicurissimo, penso ci sia qualcosa da sistemare.
aggiunta
Sì infatti ho guardato sbirciando la formula e si avvicina in maniera approssimativa, domani la sistemo a mente lucida.
Dati due insiemi $A,B$ con rispettivamente $n,m$ elementi e $mleqn$ le funzioni suriettive sono:
$D'_(m,n)-sum_{p=1}^{m-1}D'_(p,n)$
Non ne sono sicurissimo, penso ci sia qualcosa da sistemare.
aggiunta
Sì infatti ho guardato sbirciando la formula e si avvicina in maniera approssimativa, domani la sistemo a mente lucida.
Ciao 
metto in spoiler la 'soluzione':
"Martino":
Come?
metto in spoiler la 'soluzione':
.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo