Hoán vị của bốn các phần tử có 1 điểm cố định và 1 3 chu kỳ
Trong toán học, chu kỳ của một hoán vị π của một tập hợp hữu hạn S tương ứng về mặt sinh học với các quỹ đạo của nhóm phụ được tạo bởi π hoạt động trên S . Các quỹ đạo này là các tập hợp con của S có thể được viết là { c 1 …, c l }, như vậy mà
π ( c i ) = c i + 1 cho i ] = 1, …, l – 1, và π ( c l ) = c 1 .
Chu kỳ tương ứng của π được viết là ( c 1 c 2 … c [19659005] n ); biểu thức này không phải là duy nhất vì c 1 có thể được chọn là bất kỳ yếu tố nào của quỹ đạo.
Kích thước l của quỹ đạo được gọi là chiều dài của chu kỳ tương ứng; khi l = 1, phần tử đơn trong quỹ đạo được gọi là điểm cố định của hoán vị.
Một hoán vị được xác định bằng cách đưa ra một biểu thức cho mỗi chu kỳ của nó và một ký hiệu cho hoán vị bao gồm viết các biểu thức như vậy lần lượt theo thứ tự. Ví dụ: để
(2) Với mọi k > 0: s ( k 1) = ( k – 1)!.
(3) Với mọi k > j > 1, s ( k j ) = s ( k – 1, j – 1) + s ( k – 1 , j ) · ( k – 1)
Lý do cho các thuộc tính [ chỉnh sửa ]
(1) Chỉ có một cách để xây dựng hoán vị k các phần tử có chu kỳ k : Mỗi chu kỳ phải có độ dài 1 nên mọi phần tử phải là một điểm cố định.
(2.a) Mỗi chu kỳ có độ dài k có thể được viết dưới dạng hoán vị của số 1 thành k ; có k ! trong số các hoán vị này.
(2.b) Có k các cách khác nhau để viết một chu kỳ nhất định k ví dụ: (1 2 4 3) = (2 4 3 1) = (4 3 1 2) = (3 1 2 4).
(2.c) Cuối cùng: s ( k 1) = k ! / k = ( k – 1)!
(3) Có hai cách khác nhau để xây dựng một hoán vị của k với các chu kỳ j :
(3.a) Nếu chúng tôi muốn phần tử k là một điểm cố định, chúng tôi có thể chọn một trong s ( k – 1, j – 1) hoán vị với k – 1 phần tử và j – 1 chu kỳ và thêm phần tử k như một chu kỳ mới có độ dài 1.
(3.b) Nếu chúng tôi muốn phần tử k không phải là là một điểm cố định, chúng tôi có thể chọn một trong s ( k – 1, j ) hoán vị ns với k – 1 phần tử và j chu kỳ và phần tử chèn k trong một chu kỳ hiện có trước một trong k – 1 các yếu tố.
Một số giá trị [ chỉnh sửa ]
k
j
1
2
3
4
5
6
7
8
9
tổng
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
1.764
1.624
735
175
21
1
5.040
8
5.040
13.068
13.132
6.769
1.960
322
28
1
40.320
9
40.320
109,584
118.124
67.284
22,449
4.536
546
36
1
362.880
1
2
3
4
5
6
7
8
9
tổng
Đếm các hoán vị theo số điểm cố định [ chỉnh sửa ]
Giá trị f ( k j ) đếm số lượng hoán vị của k với chính xác j điểm cố định. Đối với bài viết chính về chủ đề này, xem số rencontres.
Thuộc tính [ chỉnh sửa ]
(1) Với mọi j <0 hoặc j > k : f ( k j ) = 0.
(2) f (0, 0) = 1 .
(3) Với mọi k > 1 và k ≥ j ≥ 0, f ( ] k j ) = f ( k – 1, j – 1) + f ] [ k – 1, j ) · ( k – 1 – j ) + f ( k – 1, j + 1) · ( j + 1)
Lý do cho các thuộc tính [ chỉnh sửa ] 19659196] (3) Có ba phương pháp khác nhau để xây dựng một hoán vị là k elem ents với j điểm cố định:
(3.a) Chúng tôi có thể chọn một trong f ( k – 1, j – 1) hoán vị với k – 1 yếu tố và j – 1 điểm cố định và thêm yếu tố k làm điểm cố định mới.
(3.b) Chúng tôi có thể chọn một điểm của f ( k – 1, j ) hoán vị với k – 1 yếu tố và j và chèn phần tử k trong một chu kỳ có độ dài> 1 trước một trong các phần tử ( k – 1) – j .
(3 .c) Chúng tôi có thể chọn một trong f ( k – 1, j + 1) hoán vị với k – 1 yếu tố và j + 1 điểm cố định và yếu tố tham gia k với một trong j + 1 điểm cố định cho một chu kỳ có độ dài 2.