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

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^[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.

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.^[2]^[3]

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]$
$n$	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}}

^{[note 1]}

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

^{[note 2]}

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!}}

^{[note 3]}

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)$
$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)\ {\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}}$ ^{[note 4]}	$f(5,0)\approx {\frac {5!}{e}}\approx {\frac {120}{2.71828}}\approx 44,1455=44$

Note

^ Gerstein L. J., 1987, p. 240
^ Cameron P. J., 1994, p. 80
^ Brualdi R. A., 2010, p. 290

Postille

^ Con la notazione $|Co(\sigma )|$ s'intende il numero di elementi coniugati alla permutazione σ, anche detti aventi stessa struttura ciclica o tipo.
^ Attenzione alla notazione:
$D_{n,k}$ numero delle disposizioni semplici

$D(n,k)$ numero delle dismutazioni parziali
^ Ad esempio per n=5
${\begin{aligned}f(5,0)&=120\cdot \left[{\frac {(-1)^{0}}{0!}}+{\frac {(-1)^{1}}{1!}}+{\frac {(-1)^{2}}{2!}}+{\frac {(-1)^{3}}{3!}}+{\frac {(-1)^{4}}{4!}}+{\frac {(-1)^{5}}{5!}}\right]\\&=120\cdot (1-1+1/2-1/6+1/24-1/120)=120\cdot (60/120-20/120+5/120-1/120)=120\cdot 44/120=44\\\end{aligned}}$
^ La costante ${\color {Blue}e}$ $\approx 2.71828$

Bibliografia

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

Voci correlate

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] Gerstein L. J., 1987, p. 240

[2] Cameron P. J., 1994, p. 80

[3] Brualdi R. A., 2010, p. 290

[4] Con la notazione $|Co(\sigma )|$ s'intende il numero di elementi coniugati alla permutazione σ, anche detti aventi stessa struttura ciclica o tipo.

[5] Attenzione alla notazione:
$D_{n,k}$ numero delle disposizioni semplici

$D(n,k)$ numero delle dismutazioni parziali

[6] Ad esempio per n=5
${\begin{aligned}f(5,0)&=120\cdot \left[{\frac {(-1)^{0}}{0!}}+{\frac {(-1)^{1}}{1!}}+{\frac {(-1)^{2}}{2!}}+{\frac {(-1)^{3}}{3!}}+{\frac {(-1)^{4}}{4!}}+{\frac {(-1)^{5}}{5!}}\right]\\&=120\cdot (1-1+1/2-1/6+1/24-1/120)=120\cdot (60/120-20/120+5/120-1/120)=120\cdot 44/120=44\\\end{aligned}}$

[7] La costante ${\color {Blue}e}$ $\approx 2.71828$

[1]

[2]

[3]

[note 1]

[note 2]

[note 3]

[note 4]