Cykle i punkty stałe

16-bitowa permutacja kodu Graya G pomnożona przez permutację bit-odwrócenie B G ma 2 punkty stałe, 1 2-taktowy i 3 4-cyklowe B ma 4 stałe punkty i 6 2-cyklowych GB ma 2 stałe punkty i 2 7-cyklowe

P * (1,2,3,4) ^T = (4,1,3,2) ^T Permutacja czterech elementów z 1 punktem stałym i 1 3 cyklami

W matematyce cykle permutacji π skończonego zbioru S odpowiadają bijektywnie orbitom podgrupy generowanej przez π działające na S . _ Te orbity są podzbiorami S , które można zapisać jako ${c 1, ..., c n} takie$ , że

π (do ja) = do ja + 1

dla

ja = 1, ..., n - 1

, i

π (do n) = do 1

.

Odpowiedni cykl π jest zapisany jako ( c ₁ c ₂ ... c _n ); to wyrażenie nie jest unikalne, ponieważ _c1 można wybrać jako dowolny element orbity.

Rozmiar $n$ orbity nazywany jest długością odpowiedniego cyklu; gdy $n = 1$ , pojedynczy element na orbicie nazywany jest stałym punktem permutacji.

Permutacja jest określana przez podanie wyrażenia dla każdego z jej cykli, a jedna notacja dla permutacji polega na zapisywaniu takich wyrażeń jeden po drugim w określonej kolejności. Na przykład niech

{\ Displaystyle \ pi = {\ rozpocząć {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}}}

będzie permutacją, która odwzorowuje 1 na 2, 6 na 8 itd. Wtedy można pisać

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

Tutaj 5 i 7 są stałymi punktami π , ponieważ π (5)=5 i π (7)=7. Typowe, ale niekonieczne jest nie zapisywanie cykli o długości jeden w takim wyrażeniu. Zatem π = (1 2 4 3)(6 8) byłoby odpowiednim sposobem wyrażenia tej permutacji.

Istnieją różne sposoby zapisania permutacji jako listy jej cykli, ale liczba cykli i ich zawartość są określone przez podział S na orbity, a zatem są one takie same dla wszystkich takich wyrażeń.

Zliczanie permutacji przez liczbę cykli

Liczba Stirlinga bez znaku pierwszego rodzaju, s ( k , j ) zlicza liczbę permutacji k elementów z dokładnie j rozłącznymi cyklami.

Nieruchomości

(1) Dla każdego k > 0 :

s (k, k) = 1.

(2) Dla każdego k > 0 :

s (k, 1) = (k - 1)!.

(3) Dla każdego k > j > 1,

s (k, j) = s (k - 1, j - 1) + s (k - 1, j)\cdot(k - 1)

Przyczyny właściwości

(1) Jest tylko jeden sposób skonstruowania permutacji k elementów z k cyklami: Każdy cykl musi mieć długość 1, więc każdy element musi być punktem stałym.

(2.a) Każdy cykl o długości k można zapisać jako permutację liczby 1 do k ; jest k ! z tych permutacji.

(2.b) Istnieje k różnych sposobów zapisania danego cyklu o długości k , np. ( 1 2 4 3 ) = ( 2 4 3 1 ) = ( 4 3 1 2 ) = ( 3 1 2 4 ).

(2.c) Wreszcie:

s (k, 1) = k!/ k = (k - 1)!.

(3) Istnieją dwa różne sposoby konstruowania permutacji k elementów z j cyklami:

(3.a) Jeśli chcemy, aby element k był punktem stałym, możemy wybrać jeden z

s (k - 1, j - 1)

permutacje z

k - 1

elementami i

j - 1

cyklami i dodaj element k jako nowy cykl o długości 1.

(3.b) Jeśli chcemy, aby element k nie był stałym punktem, możemy wybrać jeden z

s (k - 1 , j)

permutacje z

k - 1

elementami i j cyklami oraz wstaw element k w istniejącym cyklu przed jednym z

k - 1

elementów.

Niektóre wartości

$k$	$J$
$k$	1	2	3	4	5	6	7	8	9	suma
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	109 584	118124	67284	22449	4536	546	36	1	362.880
	1	2	3	4	5	6	7	8	9	suma

Zliczanie permutacji przez liczbę stałych punktów

Wartość $f (k, j)$ zlicza liczbę permutacji k elementów z dokładnie j stałymi punktami. Aby zapoznać się z głównym artykułem na ten temat, zobacz numery rencontres .

Nieruchomości

(1) Dla każdego j < 0 lub j > k :

f (k, j) = 0.

(2) f (0, 0) = 1.

(3) Dla każdego k > 1 i k ≥ j ≥ 0,

f (k, jot) = fa (k - 1, jot - 1) + fa (k - 1, jot) \cdot (k - 1 - jot) + fa (k - 1, jot + 1) \cdot (jot + 1)

Przyczyny właściwości

(3) Istnieją trzy różne metody konstruowania permutacji k elementów z j punktami stałymi:

(3.a) Możemy wybrać jedną z permutacji

f (k - 1, j - 1)

z

k - 1

elementami i

j - 1

punktami stałymi i dodać element k jako nowy punkt stały.

(3.b) Możemy wybrać jedną z permutacji

f (k - 1, j)

z

k - 1

elementami i j stałymi punktami i wstawić element k w istniejącym cyklu o długości > 1 przed jednym z

(k - 1) - j

elementów.

(3.c) Możemy wybrać jedną z permutacji

f (k - 1, j + 1)

z elementami

k - 1

i

j + 1

punktami stałymi i połączyć element k z jednym z punktów stałych

j + 1

w cykl długość 2.

Niektóre wartości

$k$	$J$
$k$	0	1	2	3	4	5	6	7	8	9	suma
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	133 496	133 497	66744	22260	5544	1134	168	36	0	1	362.880
	0	1	2	3	4	5	6	7	8	9	suma

Alternatywne obliczenia

równania	Przykłady
${\ Displaystyle f (k, 1) = \ suma _ {i = 1} ^ {k} (-1) ^ {i + 1} {k \ wybierz i} i (ki)!}$	${\ Displaystyle {\ rozpocząć {wyrównane} f (5,1) i = 5 \ razy 1 \ razy 4! -10 \ razy 2 \ razy 3! + 10 \ razy 3\razy 2!-5\razy 4\razy 1!+1\razy 5\razy 0!\\&=120-120+60-20+5=45.\end{wyrównane}}}$
${\ Displaystyle f (k, 0) = k! - \ suma _ {i = 1} ^ {k} (-1) ^ {i + 1} {k \ wybierz i} (ki)!}$	${\ Displaystyle {\ rozpocząć {wyrównane} f (5,0) i = 120 - (5 \ razy 4! -10 \ razy 3! + 10 \ razy 2! -5 \ razy 1! + 1 \ razy 0!)\\&=120-(120-60+20-5+1)=120-76=44.\end{wyrównane}}}$
Dla każdego k > 1: ${\ Displaystyle f (k, 0) = (k-1) ( f(k-1,0)+f(k-2,0))}$	${\ Displaystyle f (5,0) = 4 \ razy (9 + 2) = 4 \ razy 11 = 44}$
Dla każdego k > 1: ${\ Displaystyle f (k, 0) = k! \ suma _ {i = 2} ^ {k} (-1) ^ {i} / i!}$	${\ Displaystyle {\ rozpocząć {wyrównane} f (5,0) i = 120 \ razy (1/2-1/6 + 1/24-1/120) \\& = 120 \ razy (60/ 120-20/120+5/120-1/120)=120\razy 44/120=44\end{wyrównane}}}$
${\ Displaystyle f (k, 0) \ około k! / e}$ gdzie e jest liczbą Eulera ≈ 2,71828

Zobacz też

Notatki

Brualdi, Richard A. (2010), Kombinatoryka wprowadzająca (wyd. 5), Prentice-Hall, ISBN 978-0-13-602040-0
Cameron, Peter J. (1994), Kombinatoryka: tematy, techniki, algorytmy , Cambridge University Press, ISBN 0-521-45761-0
Gerstein, Larry J. (1987), Matematyka dyskretna i struktury algebraiczne , WH Freeman and Co., ISBN 0-7167-1804-9