Calcolare il numero di tutte le funzioni
Salve,
vorrei un aiuto con questi esercizi.
Siano $X$ e $Y$ due insiemi con $#X=k$, $#Y=n$ e $n, k$ appartenenti a $N$.
Calcolare il numero di tutte le funzioni $f: X rarr Y$ [$n^k$]
Iniettive ($k<=n$) [$n-k+1$]
Calcolare il numero di tutti i sottoinsiemi di $Y$ di $k$ elementi ($k<=n$) [ $ ( (n), (k) ) $ ]
Trovo difficoltà nel dover dimostrare rigorosamente queste "proprietà". Come posso procedere?
vorrei un aiuto con questi esercizi.
Siano $X$ e $Y$ due insiemi con $#X=k$, $#Y=n$ e $n, k$ appartenenti a $N$.
Calcolare il numero di tutte le funzioni $f: X rarr Y$ [$n^k$]
Iniettive ($k<=n$) [$n-k+1$]
Calcolare il numero di tutti i sottoinsiemi di $Y$ di $k$ elementi ($k<=n$) [ $ ( (n), (k) ) $ ]
Trovo difficoltà nel dover dimostrare rigorosamente queste "proprietà". Come posso procedere?
Risposte
Hai fatto un po' di combinatoria?
p.s. Il risultato delle funzioni iniettive mi sembra sbagliato.
p.s. Il risultato delle funzioni iniettive mi sembra sbagliato.
"Vulplasir":
Hai fatto un po' di combinatoria?
p.s. Il risultato delle funzioni iniettive mi sembra sbagliato.
Ho omesso un pezzo senza volerlo, $n(n-1).....(n-k+1)$ Ora va bene?
Si, ho fatto un po di pratica con la combinatoria. Il mio problema qui è costruire una "struttura" per la dimostrazione
Io partirei dal terzo che mi sembra il più standard:
$Y$ ha $n$ elementi, e bisogna determinare tutti i sottoinsiemi di $k$ elementi, questo corrisponde in combinatoria alle combinazioni di $n$ elementi a gruppi di $k$, ossia a $((n),(k))$
Riguardo al primo:
Io partirei dalla definizione di funzione:
Una funzione $f: X->Y$ è un sottoinsieme di $XxxY$ tale che per qualsiasi $a in X$ esiste uno e un solo $b in Y$ tale che $(a,b) in f$
Pertanto se $X$ ha $k$ elementi e $Y$ ne ha $n$ una funzione da $X$ in $Y$ è costituita da tutte le coppie $(a,b)$ tali che $a$ è presente una e una sola volta in tutte queste coppie mentre i $b$ possono essere qualsiasi (secondo la definizione), pertanto fissato un certo $a_i$, le possibili coppie che hanno quell'$a_i$ sono del tipo $(a_i,x)$ dove $x$ varia tra i $b$ in $Y$, esse in numero sono $n$ dato che $x$ può assumere $n$ valori. Per qualsiasi altro $a_j $ si hanno altrettante coppie $(a_j,x)$. Dato che gli $a$ sono $k$, tutte le possibili coppie $(a,b)$ non sono altro che il prodotto cartesiano dei $k$ insiemi di $n$ coppie, ciascuno per ogni $a$, ossia $n^k$
Per il secondo il procedimento è lo stesso, solo che bisogna tenere presente che la funzione è iniettiva, ossia che se $a_i!=a_j$ allora $f(a_i)!=f(a_j)$
Questo significa che se con $a_1$ possiamo determinare $n$ coppie del tipo $(a_1, b)$, allora con $a_2$ ne possiamo determinare al più $n-1$, dato che non possiamo assegnare ad $a_2$ lo stesso valore dato ad $a_1$, con $a_3$ possiamo determinarne $n-2$...con $a_k$ ne possiamo determinare $n-k+1$, il loro prodotto cartesiano è $n*(n-1)*(n-2)*...(n-k+1)=(n!)/((n-k)!$
$Y$ ha $n$ elementi, e bisogna determinare tutti i sottoinsiemi di $k$ elementi, questo corrisponde in combinatoria alle combinazioni di $n$ elementi a gruppi di $k$, ossia a $((n),(k))$
Riguardo al primo:
Io partirei dalla definizione di funzione:
Una funzione $f: X->Y$ è un sottoinsieme di $XxxY$ tale che per qualsiasi $a in X$ esiste uno e un solo $b in Y$ tale che $(a,b) in f$
Pertanto se $X$ ha $k$ elementi e $Y$ ne ha $n$ una funzione da $X$ in $Y$ è costituita da tutte le coppie $(a,b)$ tali che $a$ è presente una e una sola volta in tutte queste coppie mentre i $b$ possono essere qualsiasi (secondo la definizione), pertanto fissato un certo $a_i$, le possibili coppie che hanno quell'$a_i$ sono del tipo $(a_i,x)$ dove $x$ varia tra i $b$ in $Y$, esse in numero sono $n$ dato che $x$ può assumere $n$ valori. Per qualsiasi altro $a_j $ si hanno altrettante coppie $(a_j,x)$. Dato che gli $a$ sono $k$, tutte le possibili coppie $(a,b)$ non sono altro che il prodotto cartesiano dei $k$ insiemi di $n$ coppie, ciascuno per ogni $a$, ossia $n^k$
Per il secondo il procedimento è lo stesso, solo che bisogna tenere presente che la funzione è iniettiva, ossia che se $a_i!=a_j$ allora $f(a_i)!=f(a_j)$
Questo significa che se con $a_1$ possiamo determinare $n$ coppie del tipo $(a_1, b)$, allora con $a_2$ ne possiamo determinare al più $n-1$, dato che non possiamo assegnare ad $a_2$ lo stesso valore dato ad $a_1$, con $a_3$ possiamo determinarne $n-2$...con $a_k$ ne possiamo determinare $n-k+1$, il loro prodotto cartesiano è $n*(n-1)*(n-2)*...(n-k+1)=(n!)/((n-k)!$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo