Lezione 9 (18 marzo 1999 h. 10.30-11.30)

Definizione di permutazione

Definizione 9.1   Sia X un insieme, una permutazione di X è una applicazione bigettiva $X\to X$.

L'insieme di tutte le permutazioni di X si denota con S_X. Se $n\in\mathbb N$ e $n\ge 1$ l'insieme delle permutazioni di $\{1,2,\dots, n\}$ si denota semplicemente con S_n.

Proposizione 9.2   L'insieme S_X con l'operazione di composizione è un gruppo. Viene chiamato il gruppo simmetrico di X.

Dim.  La composizione è associativa. Infatti per ogni $x\in X$ $f\circ(g\circ h)(x)=f(g\circ h(x))=f(g(h(x)))=f\circ g(h(x))=(f\circ g)\circ h(x)$.

L'applicazione identica $I_X\in S_X$ è l'unità.

Per definizione ogni $f\in S_X$ è bigettiva e quindi esiste l'inversa f^-1 tale che $f\circ f^{-1}=f^{-1}\circ f=I_X$. Chiaramente $f^{-1}\in S_X$.     $\square$

Numero di applicazioni iniettive e di permutazioni

Proposizione 9.3   Se $k,n\in\mathbb N$, $k\le n$ allora l'insieme delle applicazioni iniettive $\{1,\dots,k\}\to\{1,\dots, n\}$ ha esattamente n!/(n-k)! elementi.

Dim.  Un'applicazione $f:\{1,2,\dots,k\}\to\{1,2,\dots,n\}$ è univocamente determinata dalla k-upla $(f(1),\dots,f(k))$. Ora f(1) può essere scelto in n modi diversi, se si vuole che f sia iniettiva f(2) potrà essere scelto tra tutti i numeri da 1 a n tranne f(1), quindi per f(2) si hanno esattamente n-1 possibilità di scelta, analogamente per f(3) si hanno n-2 scelte possibili e così vaia, supposto di aver scelto $f(1),\dots,f(i)$, per f(i+1) si hanno n-i scelte possibili.Si arriva in tal modo fino ad f(k) per il quale si hanno f(n-k+1) scelte. In totale si ottengono quindi $n(n-1)(n-2)\dots(n-k+1)=n!/(n-k)!$ applicazioni iniettive diverse.     $\square$

Osservazione 9.4   Lo stesso modo di ragionare della dimostrazione precedente, mostra che l'insieme di tutte le funzioni $\{1,\dots,k\}\to\{1,\dots, n\}$ ha n^k elementi. Infatti, non avendo restrizioni su f, ad ogni passo della sua costruzione si hanno n possibilità di scelta. Lo stesso modo di ragionare non funziona per cercare di calcolare il numero delle applicazioni surgettive.

Proposizione 9.5   Se $n\in\mathbb N$, $n\ge 1$ allora S_n ha esattamente n! elementi.

Dim.  Segue dalla proposizione precedente applicata al caso n=k.     $\square$

Definizione di ciclo

Definizione 9.6   Una permutazione $\sigma\in S_n$ si dice un ciclo se esistono a₁, $a_2, \dots ,a_k \in \{1,2, \dots,n \}$ tali che

$$\begin{array}{rcl} \begin{array}{rcl} \sigma(a_1) & = &a_2 ... ...hbox{\rm { se }} x \notin \{a_1,a_2, \dots ,a_k\} \end{array}$$

Una tale permutazione si denota con $(a_1\ a_2 \dots a_k)$ e l'intero k si chiama la lunghezza del ciclo. I cicli di lunghezza 2 sono chiamati trasposizioni. La permutazione identica è l'unico ciclo di lunghezza 1 e viene denotata con (1). Due cicli $(a_1\dots a_k)$ e $(b_1\dots b_h)$ si dicono disgiunti se $\{a_1, \dots ,a_k\} \cap \{b_1, \dots , b_h\} = \varnothing$.

Decomposizione in cicli disgiunti

Proposizione 9.7   Siano $\sigma_1=( a_1 \dots a_k)$ e $\sigma_2= (b_1 \dots b_h)$ due cicli disgiunti, allora $\sigma_1\sigma_2=\sigma_2\sigma_1$.

Dim.  Dal fatto che i due cicli sono disgiunti, si ha che l'insieme $\{1,2,\dots, n\}$ si spezza nell'unione di tre pezzi a due a due disgiunti: $A\cup B\cup X$ essendo $A=\{a_1,\dots,a_k\}$ $B=\{b_1,\dots, b_k\}$. Ora se $x\in X$ si ha che $\sigma_1(x)=\sigma_2(x)=x$ e quindi $\sigma_1\sigma_2(x)=\sigma_1(\sigma_2(x))=\sigma_2(x)=x$ e $\sigma_2\sigma_1(x)=\sigma_2(\sigma_1(x))=\sigma_1(x)=x$, in particolare $\sigma_1\sigma_2(x)=\sigma_2\sigma_1(x)$.

Se $x\in A$ allora $\sigma_1(x)\in A$ e quindi $\sigma_2(\sigma_1(x))=\sigma_1(x)$ (si ricordi che $\sigma_2$ lascia fissi gli elementi non in B). E analogamente $\sigma_2(x)=x$ e quindi $\sigma_1(\sigma_2(x))=\sigma_1(x)$. Anche in questo caso si ha che $\sigma_1\sigma_2(x)=\sigma_2\sigma_1(x)$.

Completamente analoga è la verifica che se $x\in B$ allora $\sigma_1\sigma_2(x)=\sigma_2\sigma_1(x)$. In altre parole $\sigma_1\sigma_2(x)=\sigma_2\sigma_1(x)$ per ogni $x\in\{1,\dots,n\}$, ossia $\sigma_1\sigma_2=\sigma_2\sigma_1$.     $\square$

Teorema 9.8 (decomposizione in cicli)   Ogni permutazione di S_n si decompone nel prodotto di cicli disgiunti. Tale decomposizione è unica a meno dell'ordine dei cicli.

Osservazione 9.9   Ogni ciclo si scrive come prodotto di trasposizioni, si osservi infatti che $(a_1\ a_2\dots a_k)=(a_1\ a_k)(a_1 a_{k-1})\dots(a_1\ a_3)(a_1\ a_2)$.

Corollario 9.10   Ogni permutazione si scrive come prodotto di trasposizioni.

Dim.  Segue immediatamente dal teorema e dall'osservazione precedenti.     $\square$