Cicli e punti fissi

Template:Organizzare In matematica, i cicli di una permutazione $π$ di un insieme finito X corrispondono biunivocamente alle orbite, cioè ai sottogruppi generati da $π$ quando agisce su X. Tali orbite sono sottoinsiemi di X che si possono scrivere come

X_{j} = {p_{j 1}, p_{j 2} \dots, p_{j l_{j}}} \subseteq X j = 1, 2, \dots, r r < | X | = n; {⋃ \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

π (p_{j i}) = {\begin{matrix} p_{j i + 1}, & i = 1, 2, \dots, l_{j - 1} \\ p_{j 1}, & i = l_{j} \end{matrix}

.

e per indicare ciò useremo la notazione ciclica per la j-orbita

π_{j} = (p_{j 1} p_{j 2} \dots p_{j l_{j}}) = (p_{j 2} p_{j 3} \dots p_{j l_{j}} p_{j 1}) = \dots

;

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 $π$ viene decomposta in cicli disgiunti come

π = π_{1} π_{2} \dots π_{r} = \prod_{j = 1}^{r} π_{j} \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: $π_{I} = (1) (2) \dots (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

π = (\begin{matrix} 1 & 4 & 2 & 3 \\ 4 & 2 & 1 & 3 \end{matrix}) = (\begin{matrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 3 & 2 \end{matrix}) = \dots

in notazione ciclica le scritture diventano

π = (1 4 2) (3) = (4 2 1) (3) = (2 1 4) (3)

cioè con 1 1-ciclo e 1 3-ciclo, quindi il tipo $[1^{1} 3^{1}] = (1, 3) .$ La matrice di permutazione $P_{π}$ corrispondente alla permutazione $π$ , è

P_{π} = [\begin{matrix} 𝐞_{π (1)} \\ 𝐞_{π (2)} \\ 𝐞_{π (3)} \\ 𝐞_{π (4)} \end{matrix}] = [\begin{matrix} 𝐞_{4} \\ 𝐞_{1} \\ 𝐞_{3} \\ 𝐞_{2} \end{matrix}] = [\begin{matrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{matrix}] \neq P_{π^{- 1}} = {P_{π}}^{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:

π = (\begin{matrix} 1 & 6 & 7 & 2 & 5 & 4 & 8 & 3 \\ 2 & 8 & 7 & 4 & 5 & 3 & 6 & 1 \end{matrix}) = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 4 & 1 & 3 & 5 & 8 & 7 & 6 \end{matrix}) = \dots

e in notazione ciclica

π = (1 2 4 3) (5) (6 8) (7) = (7) (1 2 4 3) (6 8) (5) = (4 3 1 2) (8 6) (5) (7) = \dots

cioè una struttura ciclica o tipo $[1^{2} 2^{1} 4^{1}] = (1, 1, 2, 4)$ , quindi si hanno 2 punti fissi o 1-ciclo.

π (5) = 5, π (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. Template:Clear

Numero permutazioni con k cicli disgiunti

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

s (n, k) = [\begin{matrix} n \\ k \end{matrix}] n, k \in ℤ^{+} 1 ⩽ k ⩽ n

conta il numero di permutazioni di n elementi con un numero di k cicli disgiunti.^[2]^[3]

Proprietà

(1)

\forall k > 0 s (n, n) = 1

(2)

\forall k > 0 s (n, 1) = (n - 1)!

(3)

\forall n > k > 1 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:

σ_{I} = (1) (2) \dots (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} [\begin{matrix} n \\ k \end{matrix}]$
$n$	1	2	3	4	5	6	7	8	9	$\sum_{k = 1}^{n} [\begin{matrix} n \\ k \end{matrix}]$
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{matrix} s (4, 1) & = 6 = | C o (σ_{1}) | & [4^{1}] & (\cdot \cdot \cdot \cdot) & 4 -ciclo \\ s (4, 2) & = 3 + 8 = | C o (σ_{2}) | + | C o (σ_{3}) | & [2^{2}], [1^{1} 3^{1}] & (\cdot \cdot) (\cdot \cdot), (\cdot) (\cdot \cdot \cdot) & 2 -ciclo, 1 -ciclo 3 -ciclo \\ s (4, 3) & = 6 = | C o (σ_{4} | & [1^{2} 2^{1}] & (\cdot) (\cdot) (\cdot \cdot) & 1 -ciclo 2 -ciclo \\ s (4, 4) & = 1 = | C o (σ_{I}) | & [1^{4}] & (\cdot) (\cdot) (\cdot) (\cdot) & σ_{I} = (1) (2) (3) (4) \end{matrix}

^{[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_{csr} = {σ_{I}, σ_{1}, σ_{2}, σ_{3}, σ_{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) n, k \in ℤ^{+} 0 ⩽ k ⩽ 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)

\forall n < k < 0 f (n, k) = 0

(2)

f (0, 0) = 1

(3)

\forall n > 1, 0 ⩽ k ⩽ n 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{matrix} D (4, 0) & = 9 = 6 + 3 = | C o (σ_{1}) | + | C o (σ_{2}) | & [4^{1}], [2^{2}] & (\cdot \cdot \cdot \cdot), (\cdot \cdot) (\cdot \cdot) & 0 -fix & dismutazioni \\ D (4, 1) & = 8 = | C o (σ_{3}) | & [1^{1} 3^{1}] & (\cdot) (\cdot \cdot \cdot) & 1 -fix \\ D (4, 2) & = 6 = | C o (σ_{4} | & [1^{2} 2^{1}] & (\cdot) (\cdot) (\cdot \cdot) & 2 -fix \\ D (4, 3) & = 0 & ∄ l_{2} : [1^{3} {l_{2}}^{k_{2}}], k_{2} ⩾ 2 & 3 -fix \\ D (4, 4) & = 1 = | C o (σ_{I}) | & [1^{4}] & (\cdot) (\cdot) (\cdot) (\cdot) & 4 -fix \end{matrix}

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} (\binom{n}{i}) i (n - i)!$	$\begin{matrix} f (5, 1) & = (- 1)^{2} (\binom{5}{1}) 1 (5 - 1)! + (- 1)^{3} (\binom{5}{2}) 2 (5 - 2)! + (- 1)^{4} (\binom{5}{3}) 3 (5 - 3)! + (- 1)^{5} (\binom{5}{4}) 4 (5 - 4)! + (- 1)^{6} (\binom{5}{5}) 5 (5 - 5)! \\ = 5 4! - 20 3! + 30 2! - 20 1! + 5 0! = 120 - 120 + 60 - 20 + 5 = 45 . \end{matrix}$
$f (n, 0) = n! - \sum_{i = 1}^{n} (- 1)^{i + 1} (\binom{n}{i}) (n - i)!$	$\begin{matrix} 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{matrix}$
$\forall n > 1$ $f (n, 0) = (n - 1) [f (n - 1, 0) + f (n - 2, 0)]$	$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

Postille

↑ Con la notazione $| C o (σ) |$ 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{matrix} f (5, 0) & = 120 \cdot [\frac{(- 1)^{0}}{0!} + \frac{(- 1)^{1}}{1!} + \frac{(- 1)^{2}}{2!} + \frac{(- 1)^{3}}{3!} + \frac{(- 1)^{4}}{4!} + \frac{(- 1)^{5}}{5!}] \\ = 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{matrix}$
↑ La costante $e$ $\approx 2.71828$

Bibliografia

Voci correlate

Template:Portale

[1] Template:Cita

[2] Template:Cita

[3] Template:Cita

[4] Con la notazione $| C o (σ) |$ 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{matrix} f (5, 0) & = 120 \cdot [\frac{(- 1)^{0}}{0!} + \frac{(- 1)^{1}}{1!} + \frac{(- 1)^{2}}{2!} + \frac{(- 1)^{3}}{3!} + \frac{(- 1)^{4}}{4!} + \frac{(- 1)^{5}}{5!}] \\ = 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{matrix}$

[7] La costante $e$ $\approx 2.71828$

[1]

[2]

[3]

[note 1]

[note 2]

[note 3]

[note 4]

Cicli e punti fissi

Indice

Notazioni equivalenti

Numero permutazioni con k cicli disgiunti

Proprietà

Dimostrazioni

Numeri Stirling tipo uno con n da 1 a 9

Numero di dismutazioni parziali con k punti fissi

Proprietà

Dimostrazioni

Numero dismutazioni parziali con n da 1 a 9

Relazioni per k=0,1 e valore asintotico

Note

Bibliografia

Voci correlate

Menu di navigazione

Cicli e punti fissi

Notazioni equivalenti

Numero permutazioni con k cicli disgiunti

Proprietà

Dimostrazioni

Numeri Stirling tipo uno con n da 1 a 9

Numero di dismutazioni parziali con k punti fissi

Proprietà

Dimostrazioni

Numero dismutazioni parziali con n da 1 a 9

Relazioni per k=0,1 e valore asintotico

Note

Bibliografia

Voci correlate

Menu di navigazione

Ricerca