Utente:Grasso Luigi/sandbox4/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₁ 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

P_π * (1,2,3,4)^T = (4,1,3,2)^T

Permutazione G del codice Gray 16 bit
composta con la permutazione inversione bit B

G ha 2 punti fissi, 1 2-ciclo e 3 4-cicli
B ha 4 punti fissi e 6 2-cicli
GB ha 2 punti fissi e 2 7-cicli

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₁₆ 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$									$\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

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

Per approfondire vedi Dismutazione parziale.

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

${\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 x:\left[1^{3}x^{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)\ {\bigl [}f(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$

Note

Libri con riferimenti

• (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.

Postille

Voci correlate

• Permutazione ciclica
• Notazione ciclica