Cicli e punti fissi

In matematica, i cicli di una permutazione ${\displaystyle \pi }$ di un insieme finito X corrispondono biunivocamente alle orbite, cioè ai sottogruppi generati da ${\displaystyle \pi }$ quando agisce su X. Tali orbite sono sottoinsiemi di X che si possono scrivere come

${\displaystyle 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

${\displaystyle \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

${\displaystyle \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₁ può essere qualsiasi elemento dell'orbita. La dimensione ${\displaystyle l_{j}}$ dell'orbita viene detta la lunghezza del ciclo corrispondente e si dice un l_j-ciclo; quando ${\displaystyle l=1}$, l'unico elemento nell'orbita viene detto un punto fisso della permutazione. Quindi la permutazione ${\displaystyle \pi }$ viene decomposta in cicli disgiunti come

${\displaystyle \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 ${\displaystyle r=|X|=n}$ otteniamo l'elemento neutro della legge di composizione, cioè la permutazione identica con n 1-ciclo: ${\displaystyle \ \pi _{I}=(1)(2)\ldots (n).}$

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

${\displaystyle \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

${\displaystyle \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 ${\displaystyle \left[1^{1}\ 3^{1}\right]=(1,3).}$ La matrice di permutazione ${\displaystyle P_{\pi }}$ corrispondente alla permutazione ${\displaystyle \pi }$, è

${\displaystyle 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:

${\displaystyle \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

${\displaystyle \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 ${\displaystyle \left[1^{2}\ 2^{1}\ 4^{1}\right]=(1,1,2,4)}$, quindi si hanno 2 punti fissi o 1-ciclo.

${\displaystyle \pi (5)=5,\ \pi (7)=7}$

È comune, ma non necessario, non scrivere i cicli di lunghezza uno in tale espressione^[1]. Dunque, un modo appropriato per esprimerla sarebbe π = (1 2 4 3)(6 8).

Infine un esempio di S₁₆ 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.

Il valore assoluto del numero di Stirling del tipo uno senza segno che denotiamo

${\displaystyle 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.^[2][3]

(1) ${\displaystyle \quad \forall k>0\quad s(n,\ n)=1}$

(2) ${\displaystyle \quad \forall k>0\quad s(n,\ 1)=(n-1)!}$

(3) ${\displaystyle \quad \forall n>k>1\quad s(n,\ k)=s(n-1,\ k-1)+s(n-1,\ k)(n-1)}$

(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:

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.

${\displaystyle n}$	${\displaystyle k}$									${\displaystyle \sum _{k=1}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]}$
	1	2	3	4	5	6	7	8	9
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

${\displaystyle {\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}}}$^{[note 1]}

che soddisfa l'equazione delle classi:

${\displaystyle 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 è

${\displaystyle 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.

Il valore delle dismutazioni parziali, anche detto numero di rincontri, del numero di permutazioni di n elementi con k punti fissi che denotiamo

${\displaystyle f(n,\ k)\ =\ D(n,k)\quad n,k\in \mathbb {Z} ^{+}\quad 0\leqslant k\leqslant n}$^{[note 2]}

dove l'insieme permutato è { 1, ..., n }. Si dimostra che ha forma esplicita

${\displaystyle 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)

${\displaystyle f(n,0)=D(n,0)=n!\ \sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}}$^{[note 3]}

(1) ${\displaystyle \quad \forall n<k<0\quad f(n,\ k)=0}$

(2) ${\displaystyle \quad f(0,\ 0)=1}$

(3) ${\displaystyle \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)}$

(3) Esistono tre metodi diversi per costruire una permutazione di n elementi con k punti fissi:

(3.a) Possiamo scegliere una delle ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.

${\displaystyle n}$	${\displaystyle k}$										${\displaystyle \sum _{k=0}^{n}D(n,k)}$
	0	1	2	3	4	5	6	7	8	9
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

${\displaystyle {\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:

${\displaystyle 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.

Equazioni	Esempi
${\displaystyle f(n,1)\ =\sum _{i=1}^{n}(-1)^{i+1}{n \choose i}i(n-i)!}$	${\displaystyle {\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}}}$
${\displaystyle f(n,0)\ =n!-\sum _{i=1}^{n}(-1)^{i+1}{n \choose i}(n-i)!}$	${\displaystyle {\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}}}$
${\displaystyle \forall n>1}$ ${\displaystyle f(n,0)\ =(n-1)\ {\bigl [}f(n-1,0)\ +f(n-2,0){\bigr ]}}$	${\displaystyle f(5,0)=4\cdot (9+2)=4\cdot 11=44}$
${\displaystyle f(n,0)\approx {\frac {n!}{e}}}$[note 4]	${\displaystyle f(5,0)\approx {\frac {5!}{e}}\approx {\frac {120}{2.71828}}\approx 44,1455=44}$

Postille

• (EN) Larry J. Gerstein, Discrete Mathematics and Algebraic Structures, W.H. Freeman and Co., 1987, ISBN 0-7167-1804-9.
• (EN) Peter J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge, CUP, 1994, ISBN 0-521-45761-0.
• (EN) Richard A. Brualdi, Introductory Combinatorics, 5ª ed., Upper Saddle River, PH, 2010, ISBN 978-0-13-602040-0.

• Permutazione ciclica
• Notazione ciclica