Ingegneria Energetica - Analisi e Geometria 1

Permutazioni

Divided by topic

Insiemi inniti - insiemi niti - applicazioni tra insiemi niti Denizione 1.Si dice che un insiemeXeinnitose esiste un'applicazione ingettiva ma non surgettiva diXinX. Esempio 1.Sicuramente l'insiemeNdei numeri naturali e innito: infattti si puo considerare, per esempio, l'applicazionef:N!Ntale che per ognin2N,f(n) = 2n. Si vede facilmente chefe ingettiva ma non surgettiva. Osservazione 1.Se un insieme innitoXe contenuto in un insiemeY, allora anche Ye innito. Denizione 2.Si dice che un insiemeXenitose e vuoto o se non e innito. Teorema 1.SiaXun insieme nito non vuoto. Al lora esiste un sottoinsiemeJ n= f1;2; : : : ; ngdiNed esiste un'applicazione bigettiva :J n! X. Osservazione 2.Nelle condizioni del Teorema 4, si puo scrivere X=f (1); (2); : : : ; (n)g: Inoltre si dice cheXeequipotenteaJ ne che ha cardinalitane si scrive: jXj=n: In parole povere la cardinalita diXe il numero degli elementi diX. Inoltre, seYe un altro insieme bigettivo aJ n, si dice anche che XeYsono equipotenti. Si osservi inne che per dimostrare che due insiemi nitiXeYhanno la stessa cardinalita, basta provare che esiste un'applicazione bigettiva traXeY. Osservazione 3.SianoX; Ydue insiemi niti. Allora puo esistere un'applicazione ingettiva aventeXcome insieme di partenza eYcome insieme di arrivo solo sejXj  jYj; invece puo esistere un'applicazione surgettiva solo sejXj  jYj. Inne, sejXj=jYj allora un'applicazionef:X!Ye ingettiva se e soltanto se e surgettiva e quindi se e soltanto se e bigettiva. Denizione 3.Un'applicazione bigettiva di un insieme nito in se si dicepermu- tazione. PostoA=fa 1; : : : ; a ng , una permutazionefdiAsi puo rappresentare tramite una matrice di tipo (2; n) (avvero avente 2 righe e n colonne) ponendo sulla prima riga gli elementi diAin un ordine qualunque e sulla seconda riga gli elementi diAin maniera tale chef(a i) stia nella stessa colonna di a i, i= 1; : : : ; n. Cioe: f= a1a 2a 3: : : a n1a n f(a 1) f(a 2) f(a 3) : : : f(a n1) f(a n) : Esempio 2.SianoA=f1;2;3;4;5g, eh:A!Atale cheh(1) = 3; h(2) = 1; h(3) = 2; h(4) = 5; h(5) = 4. Si puo scrivere: h= 1 2 3 4 5 3 1 2 5 4 Esempio 3.SiaX=f1;2;3;4;5;6;7;8g. Allora la matrice 1 2 3 4 5 6 7 8 8 7 3 1 6 2 5 4 individua immediatamente l'applicazionef:X!Xtale che f(1) = 8; f(2) = 7; f(3) = 3; f(4) = 1; f(5) = 6; f(6) = 2; f(7) = 5; f(8) = 4: Osservazione 4. E molto facile calcolare l'applicazione composta di due permutazioni su un insieme nito, se si scrivono sotto forma di matrice. Ad esempio, siano: f= 1 2 3 4 5 6 7 8 9 4 9 8 3 7 2 1 6 5 g= 1 2 3 4 5 6 7 8 9 6 5 8 1 9 2 4 3 7 : 1 2 Allora si ha:gf= 1 2 3 4 5 6 7 8 9 1 7 3 8 4 5 6 2 9 fg= 1 2 3 4 5 6 7 8 9 2 7 6 4 5 9 3 8 1 : SiaS nl'insieme delle permutazioni su noggetti e non e lesivo della generalita consid- erare i primi numeri naturali non nulli f1;2; : : : ; ng: Denizione 4.Si sice che una permutazionefmuoveun elementoasef(a)6 =a; si dice chessaasef(a) =a. Denizione 5.Si diceciclo di lunghezzar, e si indica con il simbolo (c 1c 2: : : c r), rnla permutazionef2S ntale che f(c 1) = c 2; f (c 2) = c 3; : : : ; f (c r1) = c r; f (c r) = c 1 e tutti gli altri elementi vengono ssati daf. Un ciclo di lunghezza 2 si chiama scambio. Si osservi che si ha (c 1c 2: : : c r) = ( c 2: : : c rc 1) = ( c 3: : : c rc 1c 2) = : : :(c rc 1: : : c r1). Denizione 6.Si dice che due permutazionifegsonodisgiuntese gli elementi mossi dafsono ssati dag. Osservazione 5.Si puo dimostrare che: se due permutazionifegsono disgiunte, allora fg=gf : Teorema 2.Siaf2S n. Allora fe un ciclo oppure puo essere scritta, in modo unico a meno dell'ordine, come prodotto (ovvero come composizione) di cicli disgiunti. Osservazione 6.Si puo scrivere il ciclo (c 1c 2: : : c r) come (c 1c 2: : : c r) = ( c 1c r) 


(c 1c 3) (c 1c 2) : Quindi ogni ciclo puo essere scritto come prodotto di scambi e dunque ogni permutazione puo essere scritta prima come prodotto di cicli e poi come prodotto di scambi. La scomposizione in scambi non e unica. Per esempio: f= 1 2 3 4 5 3 1 2 5 4 = (1 3 2)(4 5) = (1 2)(1 3)(4 5) (1) = (1 2)(3 4)(3 4)(1 3)(4 5): Teorema 3.Due scomposizioni in scambi di una stessa permutazione hanno la stessa parita. Osservazione 7.Il Teorema 3 vuol dire che se si hanno due scomposizioni in scambi di una stessa permutazione, il numero degli scambi che le compongono sono entrambi pari o entrambi dispari: in (1) si vede una scomposizione in 3 scambi e una scomposizione in 5 scambi della permutazionef. Denizione 7.Si dice che una permutazione edi classe pari(rispettivamentedispari) se una sua qualunque scomposizione e costituita da un numero pari (rispettivamente dispari) di scambi.