Chu kỳ và điểm cố định – Wikipedia

Các khái niệm toán học liên quan

P * (1,2,3,4) T = (4,1,3,2) T

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ụ: để

Số Stirling không dấu của loại thứ nhất, s ( k j ) đếm số lượng hoán vị của k với chính xác j tách rời các chu kỳ. [2][3]

Thuộc tính [ chỉnh sửa 19659075] (1) Với mọi k > 0: s ( k k ) = 1.

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

Một số giá trị [ chỉnh sửa ]

k j
0 1 2 3 4 5 6 7 8 9 tổng
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 1.854 1.855 924 315 70 21 0 1 5.040
8 14.833 14.832 7.420 2.464 630 112 28 0 1 40.320
9 133.496 133.497 66.744 22.260 5,544 1.134 168 36 0 1 362.880
0 1 2 3 4 5 6 7 8 9 tổng

Tính toán thay thế [ chỉnh sửa ]

Ví dụ: f (5, 1) = 5 × 1 × 4! – 10 × 2 × 3! + 10 × 3 × 2! – 5 × 4 × 1! + 1 × 5 × 0!

= 120 – 120 + 60 – 20 + 5 = 45.

Ví dụ: f (5, 0) = 120 – (5 × 4! – 10 × 3! + 10 × 2! – 5 × 1! + 1 × 0!)

= 120 – (120 – 60 + 20 – 5 + 1) = 120 – 76 = 44.
Với mọi k > 1: