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
X
j
=
{
p
j
1
,
p
j
2
…
,
p
j
l
j
}
⊆
X
j
=
1
,
2
,
…
,
r
r
<
|
X
|
=
n
;
⋃
⋅
j
=
1
r
X
j
=
X
{\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
π
(
p
j
i
)
=
{
p
j
i
+
1
,
i
=
1
,
2
,
…
,
l
j
−
1
p
j
1
,
i
=
l
j
{\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
π
j
=
(
p
j
1
p
j
2
⋯
p
j
l
j
)
=
(
p
j
2
p
j
3
⋯
p
j
l
j
p
j
1
)
=
…
{\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 1 può essere qualsiasi elemento dell'orbita. La dimensione
l
j
{\displaystyle l_{j}}
dell'orbita viene detta la lunghezza del ciclo corrispondente e si dice un lj -ciclo; quando
l
=
1
{\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
π
=
π
1
π
2
⋯
π
r
=
∏
j
=
1
r
π
j
∑
j
=
1
r
l
j
=
|
X
|
=
n
{\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
r
=
|
X
|
=
n
{\displaystyle r=|X|=n}
otteniamo l'elemento neutro della legge di composizione, cioè la permutazione identica con n 1-ciclo:
π
I
=
(
1
)
(
2
)
…
(
n
)
.
{\displaystyle \ \pi _{I}=(1)(2)\ldots (n).}
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
π
=
(
1
4
2
3
4
2
1
3
)
=
(
1
2
3
4
4
1
3
2
)
=
⋯
{\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
π
=
(
1
4
2
)
(
3
)
=
(
4
2
1
)
(
3
)
=
(
2
1
4
)
(
3
)
{\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
[
1
1
3
1
]
=
(
1
,
3
)
.
{\displaystyle \left[1^{1}\ 3^{1}\right]=(1,3).}
La matrice di permutazione
P
π
{\displaystyle P_{\pi }}
corrispondente alla permutazione
π
{\displaystyle \pi }
, è
P
π
=
[
e
π
(
1
)
e
π
(
2
)
e
π
(
3
)
e
π
(
4
)
]
=
[
e
4
e
1
e
3
e
2
]
=
[
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
0
]
≠
P
π
−
1
=
P
π
T
{\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:
π
=
(
1
6
7
2
5
4
8
3
2
8
7
4
5
3
6
1
)
=
(
1
2
3
4
5
6
7
8
2
4
1
3
5
8
7
6
)
=
⋯
{\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
π
=
(
1
2
4
3
)
(
5
)
(
6
8
)
(
7
)
=
(
7
)
(
1
2
4
3
)
(
6
8
)
(
5
)
=
(
4
3
1
2
)
(
8
6
)
(
5
)
(
7
)
=
…
{\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
[
1
2
2
1
4
1
]
=
(
1
,
1
,
2
,
4
)
{\displaystyle \left[1^{2}\ 2^{1}\ 4^{1}\right]=(1,1,2,4)}
, quindi si hanno 2 punti fissi o 1-ciclo.
π
(
5
)
=
5
,
π
(
7
)
=
7
{\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 S16 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
s
(
n
,
k
)
=
[
n
k
]
n
,
k
∈
Z
+
1
⩽
k
⩽
n
{\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)
∀
k
>
0
s
(
n
,
n
)
=
1
{\displaystyle \quad \forall k>0\quad s(n,\ n)=1}
(2)
∀
k
>
0
s
(
n
,
1
)
=
(
n
−
1
)
!
{\displaystyle \quad \forall k>0\quad s(n,\ 1)=(n-1)!}
(3)
∀
n
>
k
>
1
s
(
n
,
k
)
=
s
(
n
−
1
,
k
−
1
)
+
s
(
n
−
1
,
k
)
(
n
−
1
)
{\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 Sn :
σ
I
=
(
1
)
(
2
)
⋯
(
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
s
(
n
,
1
)
=
n
!
/
n
=
(
n
−
1
)
!
.
{\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
s
(
n
−
1
,
k
−
1
)
{\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
s
(
n
−
1
,
n
)
{\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.
n
{\displaystyle n}
k
{\displaystyle k}
∑
k
=
1
n
[
n
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
s
(
4
,
1
)
=
6
=
|
C
o
(
σ
1
)
|
[
4
1
]
(
⋅
⋅
⋅
⋅
)
4
-ciclo
s
(
4
,
2
)
=
3
+
8
=
|
C
o
(
σ
2
)
|
+
|
C
o
(
σ
3
)
|
[
2
2
]
,
[
1
1
3
1
]
(
⋅
⋅
)
(
⋅
⋅
)
,
(
⋅
)
(
⋅
⋅
⋅
)
2
-ciclo
,
1
-ciclo
3
-ciclo
s
(
4
,
3
)
=
6
=
|
C
o
(
σ
4
|
[
1
2
2
1
]
(
⋅
)
(
⋅
)
(
⋅
⋅
)
1
-ciclo
2
-ciclo
s
(
4
,
4
)
=
1
=
|
C
o
(
σ
I
)
|
[
1
4
]
(
⋅
)
(
⋅
)
(
⋅
)
(
⋅
)
σ
I
=
(
1
)
(
2
)
(
3
)
(
4
)
{\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 :
s
(
4
,
1
)
+
s
(
4
,
2
)
+
s
(
4
,
3
)
+
s
(
4
,
4
)
=
6
+
11
+
6
+
1
=
24
=
|
S
4
|
=
n
!
=
4
!
{\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 è
G
csr
=
{
σ
I
,
σ
1
,
σ
2
,
σ
3
,
σ
4
}
⊆
S
4
{\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 .
Numero di dismutazioni parziali con k punti fissi [ modifica | modifica wikitesto ]
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
∈
Z
+
0
⩽
k
⩽
n
{\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
D
(
n
,
k
)
=
n
!
k
!
∑
i
=
0
n
−
k
(
−
1
)
i
i
!
{\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)
f
(
n
,
0
)
=
D
(
n
,
0
)
=
n
!
∑
i
=
0
n
(
−
1
)
i
i
!
{\displaystyle f(n,0)=D(n,0)=n!\ \sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}}
[note 3]
(1)
∀
n
<
k
<
0
f
(
n
,
k
)
=
0
{\displaystyle \quad \forall n<k<0\quad f(n,\ k)=0}
(2)
f
(
0
,
0
)
=
1
{\displaystyle \quad f(0,\ 0)=1}
(3)
∀
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
)
{\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
f
(
n
−
1
,
k
−
1
)
{\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
f
(
n
−
1
,
k
)
{\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
f
(
n
−
1
,
k
+
1
)
{\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.
n
{\displaystyle n}
k
{\displaystyle k}
∑
k
=
0
n
D
(
n
,
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
D
(
4
,
0
)
=
9
=
6
+
3
=
|
C
o
(
σ
1
)
|
+
|
C
o
(
σ
2
)
|
[
4
1
]
,
[
2
2
]
(
⋅
⋅
⋅
⋅
)
,
(
⋅
⋅
)
(
⋅
⋅
)
0
-fix
dismutazioni
D
(
4
,
1
)
=
8
=
|
C
o
(
σ
3
)
|
[
1
1
3
1
]
(
⋅
)
(
⋅
⋅
⋅
)
1
-fix
D
(
4
,
2
)
=
6
=
|
C
o
(
σ
4
|
[
1
2
2
1
]
(
⋅
)
(
⋅
)
(
⋅
⋅
)
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
]
(
⋅
)
(
⋅
)
(
⋅
)
(
⋅
)
4
-fix
{\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:
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
!
{\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
f
(
n
,
1
)
=
∑
i
=
1
n
(
−
1
)
i
+
1
(
n
i
)
i
(
n
−
i
)
!
{\displaystyle f(n,1)\ =\sum _{i=1}^{n}(-1)^{i+1}{n \choose i}i(n-i)!}
f
(
5
,
1
)
=
(
−
1
)
2
(
5
1
)
1
(
5
−
1
)
!
+
(
−
1
)
3
(
5
2
)
2
(
5
−
2
)
!
+
(
−
1
)
4
(
5
3
)
3
(
5
−
3
)
!
+
(
−
1
)
5
(
5
4
)
4
(
5
−
4
)
!
+
(
−
1
)
6
(
5
5
)
5
(
5
−
5
)
!
=
5
4
!
−
20
3
!
+
30
2
!
−
20
1
!
+
5
0
!
=
120
−
120
+
60
−
20
+
5
=
45.
{\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}}}
f
(
n
,
0
)
=
n
!
−
∑
i
=
1
n
(
−
1
)
i
+
1
(
n
i
)
(
n
−
i
)
!
{\displaystyle f(n,0)\ =n!-\sum _{i=1}^{n}(-1)^{i+1}{n \choose i}(n-i)!}
f
(
5
,
0
)
=
120
−
(
5
⋅
4
!
−
10
⋅
3
!
+
10
⋅
2
!
−
5
⋅
1
!
+
1
⋅
0
!
)
=
120
−
(
120
−
60
+
20
−
5
+
1
)
=
120
−
76
=
44.
{\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}}}
∀
n
>
1
{\displaystyle \forall n>1}
f
(
n
,
0
)
=
(
n
−
1
)
[
f
(
n
−
1
,
0
)
+
f
(
n
−
2
,
0
)
]
{\displaystyle f(n,0)\ =(n-1)\ {\bigl [}f(n-1,0)\ +f(n-2,0){\bigr ]}}
f
(
5
,
0
)
=
4
⋅
(
9
+
2
)
=
4
⋅
11
=
44
{\displaystyle f(5,0)=4\cdot (9+2)=4\cdot 11=44}
f
(
n
,
0
)
≈
n
!
e
{\displaystyle f(n,0)\approx {\frac {n!}{e}}}
[note 4]
f
(
5
,
0
)
≈
5
!
e
≈
120
2.71828
≈
44
,
1455
=
44
{\displaystyle f(5,0)\approx {\frac {5!}{e}}\approx {\frac {120}{2.71828}}\approx 44,1455=44}
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
^ Con la notazione
|
C
o
(
σ
)
|
{\displaystyle |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
{\displaystyle D_{n,k}}
numero delle disposizioni semplici
D
(
n
,
k
)
{\displaystyle D(n,k)}
numero delle dismutazioni parziali
^ Ad esempio per n=5
f
(
5
,
0
)
=
120
⋅
[
(
−
1
)
0
0
!
+
(
−
1
)
1
1
!
+
(
−
1
)
2
2
!
+
(
−
1
)
3
3
!
+
(
−
1
)
4
4
!
+
(
−
1
)
5
5
!
]
=
120
⋅
(
1
−
1
+
1
/
2
−
1
/
6
+
1
/
24
−
1
/
120
)
=
120
⋅
(
60
/
120
−
20
/
120
+
5
/
120
−
1
/
120
)
=
120
⋅
44
/
120
=
44
{\displaystyle {\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
e
{\displaystyle {\color {Blue}e}}
≈
2.71828
{\displaystyle \approx 2.71828}