# Cicli e punti fissi

In matematica, i cicli di una permutazione $\pi$ di un insieme finito X corrispondono biunivocamente alle orbite, cioè ai sottogruppi generati da $\pi$ quando agisce su X. Tali orbite sono sottoinsiemi di X che si possono scrivere come
    $X_{j}=\{p_{j1},p_{j2}\ldots ,p_{jl_{j}}\}\subseteq X\quad j=1,2,\ldots ,r\quad r<|X|=n\ ;\qquad \operatorname {{\bigcup }\!\!\!\!{\cdot }\,} _{\ j=1}^{\ r}X_{j}\ =\ X$,
e la loro unione, di tipo disgiunta, fornisce l'intero insieme X; ogni j-orbita verifica le relazioni
    $\pi (p_{ji})={\begin{cases}p_{j\ i+1},&\quad i=1,2,\ldots ,l_{j-1}\\p_{j1},&\quad i=l_{j}\end{cases}}$.
e per indicare ciò useremo la notazione ciclica per la j-orbita
    $\pi _{j}=(p_{j1}\ p_{j2}\ \cdots \ p_{jl_{j}})=(p_{j2}\ p_{j3}\ \cdots \ p_{jl_{j}}\ p_{j1})=\ldots$;
cioè tale espressione non è unica in quanto p$_1$ può essere qualsiasi elemento dell'orbita. La dimensione $l_{j}$ dell'orbita viene detta la lunghezza del ciclo corrispondente e si dice un l$_j$-ciclo; quando $l=1$, l'unico elemento nell'orbita viene detto un punto fisso della permutazione. Quindi la permutazione $\pi$ viene decomposta in cicli disgiunti come
    $\pi =\pi _{1}\,\pi _{2}\cdots \pi _{r}=\prod _{j=1}^{r}\,\pi _{j}\qquad \sum _{j=1}^{r}l_{j}=|X|=n$
nel caso $r=|X|=n$ otteniamo l'elemento neutro della legge di composizione, cioè la permutazione identica con n 1-ciclo: $\ \pi _{I}=(1)(2)\ldots (n).$

## Notazioni equivalenti

Una permutazione viene determinata dando un'espressione per ciascuno dei suoi cicli, e una notazione per le permutazioni consiste nello scrivere tali espressioni una dopo l'altra in un certo ordine. Ad esempio in notazione 2-linea si possono avere più scritture equivalenti
    $\pi ={\begin{pmatrix}1&4&2&3\\4&2&1&3\end{pmatrix}}={\begin{pmatrix}1&2&3&4\\4&1&3&2\end{pmatrix}}=\cdots$
in notazione ciclica le scritture diventano
    $\pi =(1\ 4\ 2)(3)=(4\ 2\ 1)(3)=(2\ 1\ 4)(3)$
cioè con 1 1-ciclo e 1 3-ciclo, quindi il tipo $\left[1^{1}\ 3^{1}\right]=(1,3).$ La matrice di permutazione $P_{\pi }$ corrispondente alla permutazione $\pi$, è
    $P_{\pi }={\begin{bmatrix}\mathbf {e} _{\pi (1)}\\\mathbf {e} _{\pi (2)}\\\mathbf {e} _{\pi (3)}\\\mathbf {e} _{\pi (4)}\end{bmatrix}}={\begin{bmatrix}\mathbf {e} _{4}\\\mathbf {e} _{1}\\\mathbf {e} _{3}\\\mathbf {e} _{2}\end{bmatrix}}={\begin{bmatrix}0&0&0&1\\1&0&0&0\\0&0&1&0\\0&1&0&0\end{bmatrix}}\neq P_{\pi ^{-1}}={P_{\pi }}^{T}$
La stessa può essere rappresentata come trasformazione geometrica attiva nella forma di un quadrato, come a destra. Tale quadrato ha:
* gli 1 della matrice P$_π$ rappresentati dalle caselle in rosso.
* i valori iniziali 1,2,3,4 da permutare sono i puntini neri nella diagonale principale
* le frecce curve indicano il 3-ciclo 1→4→2 nella notazione postfissa o azione destra.
Vediamo un esempio dove sono presenti cicli di lunghezza diversi:
    $\pi ={\begin{pmatrix}1&6&7&2&5&4&8&3\\2&8&7&4&5&3&6&1\end{pmatrix}}={\begin{pmatrix}1&2&3&4&5&6&7&8\\2&4&1&3&5&8&7&6\end{pmatrix}}=\cdots$
e in notazione ciclica
    $\pi =(1\ 2\ 4\ 3)(5)(6\ 8)(7)=(7)(1\ 2\ 4\ 3)(6\ 8)(5)=(4\ 3\ 1\ 2)(8\ 6)(5)(7)=\ldots$
cioè una struttura ciclica o tipo $\left[1^{2}\ 2^{1}\ 4^{1}\right]=(1,1,2,4)$, quindi si hanno 2 punti fissi o 1-ciclo.
    $\pi (5)=5,\ \pi (7)=7$
È comune, ma non necessario, non scrivere i cicli di lunghezza uno in tale espressione. Dunque, un modo appropriato per esprimerla sarebbe π = (1 2 4 3)(6 8).
Infine un esempio di S$_{16}$ dove si usa la legge di composizione nell'uso del codice Gray in dispositivi elettronici di acquisizione di posizione, codificando il valore digitale della posizione chiudendo o aprendo una serie di contatti elettrici o barriere ottiche.
Questi tre esempi evidenziano i diversi modi per scrivere una permutazione come una lista dei suoi cicli, ma il numero di cicli e il loro contenuto sono dati dalla partizione di X in orbite, e questi insiemi sono quindi gli stessi per tutte queste espressioni.

## Numero permutazioni con k cicli disgiunti

Il valore assoluto del numero di Stirling del tipo uno senza segno che denotiamo
       $s(n,\ k)\ =\ \left[{\begin{matrix}n\\k\end{matrix}}\right]\quad n,k\in \mathbb {Z} ^{+}\ 1\leqslant k\leqslant n$
conta il numero di permutazioni di n elementi con un numero di k cicli disgiunti.

### Proprietà

    (1) $\quad \forall k>0\quad s(n,\ n)=1$
    (2) $\quad \forall k>0\quad s(n,\ 1)=(n-1)!$
    (3) $\quad \forall n>k>1\quad s(n,\ k)=s(n-1,\ k-1)+s(n-1,\ k)(n-1)$

### Dimostrazioni

    (1) Esiste un solo modo per ottenere una permutazione di n elementi con n cicli disgiunti: ogni ciclo ha lunghezza 1 e quindi ogni elemento è un punto fisso. Questa permutazione è quella identica rispetto alla legge di composizione in S$_n$:
       $\sigma _{I}=(1)(2)\cdots (n)$
    (2) Esiste una espressione semplice per il numero di permutazioni con un solo ciclo disgiunto
       (2.a) Ogni ciclo di lunghezza l si può scrivere come permutazione dei numeri da 1 a l; cioè l!.
       (2.b) Vi sono l modi diversi per scrivere un ciclo di lunghezza l, ad esempio per l=4 abbiamo le 4 scritture equivalenti: ( 1 2 4 3 ) = ( 2 4 3 1 ) = ( 4 3 1 2 ) = ( 3 1 2 4 ).
       (2.c) Infine $s(n,1)=n!/n=(n-1)!.$
    (3) Esistono due modi diversi per costruire una permutazione di n elementi con k cicli:
       (3.a) Se vogliamo che l'elemento n sia un punto fisso possiamo scegliere una delle $s(n-1,\ k-1)$ permutazioni con n − 1 elementi e k − 1 cicli e aggiungere l'elemento n come nuovo ciclo di lunghezza 1.
       (3.b) Se vogliamo che l'elemento n non sia punto fisso possiamo scegliere una delle $s(n-1,\ n)$ permutazioni con n − 1 elementi ed n cicli ed inserire l'elemento n in un ciclo esistente di fronte a uno degli n − 1 elementi.

### Numeri Stirling tipo uno con n da 1 a 9

| $n$ | $k$ | $k$ | $k$ | $k$ | $k$ | $k$ | $k$ | $k$ | $k$ | $\sum _{k=1}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]$ |
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | $\sum _{k=1}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]$ |
| 1 | 1 | | | | | | | | | 1 |
| 2 | 1 | 1 | | | | | | | | 2 |
| 3 | 2 | 3 | 1 | | | | | | | 6 |
| 4 | 6 | 11 | 6 | 1 | | | | | | 24 |
| 5 | 24 | 50 | 35 | 10 | 1 | | | | | 120 |
| 6 | 120 | 274 | 225 | 85 | 15 | 1 | | | | 720 |
| 7 | 720 | 1764 | 1624 | 735 | 175 | 21 | 1 | | | 5040 |
| 8 | 5040 | 13068 | 13132 | 6769 | 1960 | 322 | 28 | 1 | | 40320 |
| 9 | 40320 | 109584 | 118124 | 67284 | 22449 | 4536 | 546 | 36 | 1 | 362880 |
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
Ad esempio, se prendiamo n=4 abbiamo
    ${\begin{aligned}s(4,1)&=6=|Co(\sigma _{1})|&\left[4^{1}\right]&&(\cdot ~\cdot ~\cdot ~\cdot )&&4{\mbox{-ciclo}}\\s(4,2)&=3+8=|Co(\sigma _{2})|+|Co(\sigma _{3})|&\left[2^{2}\right],\ \left[1^{1}3^{1}\right]&&(\cdot ~\cdot )(\cdot ~\cdot ),(\cdot )(\cdot ~\cdot ~\cdot )&&2{\mbox{-ciclo}},1{\mbox{-ciclo }}3{\mbox{-ciclo}}\\s(4,3)&=6=|Co(\sigma _{4}|&\left[1^{2}2^{1}\right]&&(\cdot )(\cdot )(\cdot ~\cdot )&&1{\mbox{-ciclo }}2{\mbox{-ciclo}}\\s(4,4)&=1=|Co(\sigma _{I})|&\left[1^{4}\right]&&(\cdot )(\cdot )(\cdot )(\cdot )&&\sigma _{I}=(1)(2)(3)(4)\\\end{aligned}}$
che soddisfa l'equazione delle classi:
    $s(4,1)+s(4,2)+s(4,3)+s(4,4)=6+11+6+1=24=|S_{4}|=n!=4!$
dove l'insieme degli elementi rappresentativi delle singole classi è
    $G_{\mbox{csr}}=\{\sigma _{I},\ \sigma _{1},\ \sigma _{2},\ \sigma _{3},\ \sigma _{4}\}\subseteq S_{4}$
con csr le iniziali di complete system of rapresentatives.

## Numero di dismutazioni parziali con k punti fissi

Il valore delle dismutazioni parziali, anche detto numero di rincontri, del numero di permutazioni di n elementi con k punti fissi che denotiamo
       $f(n,\ k)\ =\ D(n,k)\quad n,k\in \mathbb {Z} ^{+}\quad 0\leqslant k\leqslant n$
dove l'insieme permutato è { 1, ..., n }. Si dimostra che ha forma esplicita
    $D(n,k)\ =\ {\frac {n!}{k!}}\ \sum _{i=0}^{n-k}{\frac {(-1)^{i}}{i!}}$
in particolare si hanno le dismutazioni per k=0 (vedi la colonna in grigio scuro nella tabella seguente)
    $f(n,0)=D(n,0)=n!\ \sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}$

### Proprietà

    (1) $\quad \forall n<k<0\quad f(n,\ k)=0$
    (2) $\quad f(0,\ 0)=1$
    (3) $\quad \forall n>1,\ 0\leqslant k\leqslant n\quad f(n,\ k)\ =\ f(n-1,\ k-1)+f(n-1,\ k)(n-1-k)\ +f(n-1,\ k+1)(k+1)$

### Dimostrazioni

(3) Esistono tre metodi diversi per costruire una permutazione di n elementi con k punti fissi:
    (3.a) Possiamo scegliere una delle $f(n-1,\ k-1)$ permutazioni con n − 1 elementi e k − 1 punti fissi ed aggiungere n come un altro punto fisso.
    (3.b) Possiamo scegliere una delle $f(n-1,\ k)$ permutazioni con n − 1 elementi e k punti fissi ed inserire l'elemento n in un ciclo esistente con lunghezza > 1 davanti a uno degli (n − 1) − k elementi.
    (3.c) Possiamo scegliere una delle $f(n-1,\ k+1)$ permutazioni con n − 1 elementi e k + 1 punti fissi e unire l'elemento n con uno dei k + 1 punti fissi a un 2-ciclo.

### Numero dismutazioni parziali con n da 1 a 9

| $n$ | $k$ | $k$ | $k$ | $k$ | $k$ | $k$ | $k$ | $k$ | $k$ | $k$ | $\sum _{k=0}^{n}D(n,k)$ |
| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | $\sum _{k=0}^{n}D(n,k)$ |
| 1 | 0 | 1 | | | | | | | | | 1 |
| 2 | 1 | 0 | 1 | | | | | | | | 2 |
| 3 | 2 | 3 | 0 | 1 | | | | | | | 6 |
| 4 | 9 | 8 | 6 | 0 | 1 | | | | | | 24 |
| 5 | 44 | 45 | 20 | 10 | 0 | 1 | | | | | 120 |
| 6 | 265 | 264 | 135 | 40 | 15 | 0 | 1 | | | | 720 |
| 7 | 1854 | 1855 | 924 | 315 | 70 | 21 | 0 | 1 | | | 5040 |
| 8 | 14833 | 14832 | 7420 | 2464 | 630 | 112 | 28 | 0 | 1 | | 40320 |
| 9 | 133496 | 133497 | 66744 | 22260 | 5544 | 1134 | 168 | 36 | 0 | 1 | 362880 |
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
Ritornando all'esempio n=4 abbiamo
    ${\begin{aligned}D(4,0)&=9=6+3=|Co(\sigma _{1})|+|Co(\sigma _{2})|&\left[4^{1}\right],\ \left[2^{2}\right]&&(\cdot ~\cdot ~\cdot ~\cdot ),(\cdot ~\cdot )(\cdot ~\cdot )&&0{\mbox{-fix}}&&{\mbox{dismutazioni}}\\D(4,1)&=8=|Co(\sigma _{3})|&\left[1^{1}3^{1}\right]&&(\cdot )(\cdot ~\cdot ~\cdot )&&1{\mbox{-fix}}&&\\D(4,2)&=6=|Co(\sigma _{4}|&\left[1^{2}2^{1}\right]&&(\cdot )(\cdot )(\cdot ~\cdot )&&2{\mbox{-fix}}&&\\D(4,3)&=0&\nexists \ l_{2}:\left[1^{3}\ {l_{2}}^{k_{2}}\right],\ k_{2}\geqslant 2&&&&3{\mbox{-fix}}&&\\D(4,4)&=1=|Co(\sigma _{I})|&\left[1^{4}\right]&&(\cdot )(\cdot )(\cdot )(\cdot )&&4{\mbox{-fix}}&&\\\end{aligned}}$
che soddisfa l'equazione delle classi rispetto ai punti fissi:
    $D(4,0)+D(4,1)+D(4,2)+D(4,3)+D(4,4)=9+8+6+0+1=24=|S_{4}|=n!=4!$
dove l'insieme degli elementi rappresentativi delle singole classi è come definito prima.

### Relazioni per k=0,1 e valore asintotico

| Equazioni | Esempi |
| $f(n,1)\ =\sum _{i=1}^{n}(-1)^{i+1}{n \choose i}i(n-i)!$ | ${\begin{aligned}f(5,1)&=(-1)^{2}{5 \choose 1}1(5-1)!+(-1)^{3}{5 \choose 2}2(5-2)!+(-1)^{4}{5 \choose 3}3(5-3)!+(-1)^{5}{5 \choose 4}4(5-4)!+(-1)^{6}{5 \choose 5}5(5-5)!\\&=5\ 4!-20\ 3!+30\ 2!-20\ 1!+5\ 0!=120-120+60-20+5=45.\\\end{aligned}}$ |
| $f(n,0)\ =n!-\sum _{i=1}^{n}(-1)^{i+1}{n \choose i}(n-i)!$ | ${\begin{aligned}f(5,0)&=120-(5\cdot 4!-10\cdot 3!+10\cdot 2!-5\cdot 1!+1\cdot 0!)\\&=120-(120-60+20-5+1)=120-76=44.\\\end{aligned}}$ |
| $\forall n>1$ $f(n,0)\ =(n-1)\ {\biglf(n-1,0)\ +f(n-2,0){\bigr ]}$ | $f(5,0)=4\cdot (9+2)=4\cdot 11=44$ |
| $f(n,0)\approx {\frac {n!}{e}}$ | $f(5,0)\approx {\frac {5!}{e}}\approx {\frac {120}{2.71828}}\approx 44,1455=44$ |