Permutazioni
Salve uno studente al primo anno di matematica e sto avendo qualche difficolta con questa dimostrazione di geometria:
bisogna dimostrare che la cardinalita dell'insieme Sn è n! dove Sn={A:Nm-->Nm biunivoca}
indicando con #Sn la cardinalita dell'insieme cerchiamo di dimostrarlo per induzione:
per n=1 S1={1}=Id quindi #S1=1=1!
passo induttivo: #Sn-1=(n-1)!
per ogni K=1,2,....,n I(K)={A che appartiene ad Sn/A(k)=n}
Sn=I(1)uI(2)uI(3)...uI(n) insieme disgiunti
allora #Sn=\sum da 1 a n di #I(K)=n(n-1)!
NON riesco proprio a capirla...me la potete spiegare?? non riesco in particolare a capire gli ultimi passaggi
da quanto ho capito I(K) indica un posto per un elemento e per ipotesi #Sn-1=(n-1)! ma non riesco a capire come fa a dire che Sn=n!
grazie in anticipo!
bisogna dimostrare che la cardinalita dell'insieme Sn è n! dove Sn={A:Nm-->Nm biunivoca}
indicando con #Sn la cardinalita dell'insieme cerchiamo di dimostrarlo per induzione:
per n=1 S1={1}=Id quindi #S1=1=1!
passo induttivo: #Sn-1=(n-1)!
per ogni K=1,2,....,n I(K)={A che appartiene ad Sn/A(k)=n}
Sn=I(1)uI(2)uI(3)...uI(n) insieme disgiunti
allora #Sn=\sum da 1 a n di #I(K)=n(n-1)!
NON riesco proprio a capirla...me la potete spiegare?? non riesco in particolare a capire gli ultimi passaggi
da quanto ho capito I(K) indica un posto per un elemento e per ipotesi #Sn-1=(n-1)! ma non riesco a capire come fa a dire che Sn=n!
grazie in anticipo!
Risposte
Ti prego la prossima volta scrivi con http://www.matematicamente.it/forum/come-si-scrivono-le-formule-asciimathml-e-tex-t26179.html perché è una fatica leggere quello che hai scritto! 
Se capisco bene Nm (ma perché indicarlo così???) dovrebbe indicare l'insieme $\{1,...,n\}$. $I_k$ è l'insieme delle funzioni biunivoche da $\{1,...,n\}$ in $\{1,...,n\}$ che mappano $k$ in $n$. Per suriettività, una qualunque funzione di $S_n$ deve mappare un qualche $k\in\{1,...,n\}$ in $n$, dunque $S_n=I_1\cup...\cup I_n$; l'unione è disgiunta perché se $A\in I_k\cap I_j$, manda $k$ e $j$ in $n$, e quindi per iniettività $k=j$.
$\forall k$, $I_k$ ha la stessa cardinalità di $S_{n-1}$ (l'elemento $k$ è mandato sempre in $n$, quindi si tratta di una permutazione tra gli altri $n-1$ elementi). Quindi per ipotesi induttiva
$|S_n|=\sum_{k=1}^n |I_k|=\sum_{k=1}^n (n-1)! =n(n-1)! =n!$
Se capisco bene Nm (ma perché indicarlo così???) dovrebbe indicare l'insieme $\{1,...,n\}$. $I_k$ è l'insieme delle funzioni biunivoche da $\{1,...,n\}$ in $\{1,...,n\}$ che mappano $k$ in $n$. Per suriettività, una qualunque funzione di $S_n$ deve mappare un qualche $k\in\{1,...,n\}$ in $n$, dunque $S_n=I_1\cup...\cup I_n$; l'unione è disgiunta perché se $A\in I_k\cap I_j$, manda $k$ e $j$ in $n$, e quindi per iniettività $k=j$.
$\forall k$, $I_k$ ha la stessa cardinalità di $S_{n-1}$ (l'elemento $k$ è mandato sempre in $n$, quindi si tratta di una permutazione tra gli altri $n-1$ elementi). Quindi per ipotesi induttiva
$|S_n|=\sum_{k=1}^n |I_k|=\sum_{k=1}^n (n-1)! =n(n-1)! =n!$
penso di aver capito ma non ho capito benissimo perchè l'unione è disgiunta..perchè A è biunivoca??
L'hai scritto tu che dev'essere biunivoca, mica io 
:
In ogni caso è la definizione di $S_n$, che è l'insieme delle permutazioni su $n$ oggetti, ovvero delle funzioni biunivoche da $\{1,...,n\}$ in sé.
Per dimostrare che l'unione è disgiunta (che ti serve per poter dire che la cardinalità di $S_n$ è la somma delle cardinalità degli $I_k$): supponi per assurdo che due insiemi $I_j$ e $I_k$, con $j!=k$ altrimenti sono lo stesso insieme, non siano disgiunti. Allora esiste un elemento $A\in S_n$ (quindi biunivoca!!) che sta sia in $I_j$ sia in $I_k$. Allora $A(j)=n=A(k)$, e per l'iniettività di $A$ abbiamo $j=k$. Assurdo, perché avevamo supposto $j!=k$.
:bisogna dimostrare che la cardinalita dell'insieme Sn è n! dove Sn={A:Nm-->Nm biunivoca}
In ogni caso è la definizione di $S_n$, che è l'insieme delle permutazioni su $n$ oggetti, ovvero delle funzioni biunivoche da $\{1,...,n\}$ in sé.
Per dimostrare che l'unione è disgiunta (che ti serve per poter dire che la cardinalità di $S_n$ è la somma delle cardinalità degli $I_k$): supponi per assurdo che due insiemi $I_j$ e $I_k$, con $j!=k$ altrimenti sono lo stesso insieme, non siano disgiunti. Allora esiste un elemento $A\in S_n$ (quindi biunivoca!!) che sta sia in $I_j$ sia in $I_k$. Allora $A(j)=n=A(k)$, e per l'iniettività di $A$ abbiamo $j=k$. Assurdo, perché avevamo supposto $j!=k$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo