Bài giảng Một số thuật toán tổ hợp - Bài 3: Phân hoạch - Lê Hồng Phương

phân hoạch Bài giảng chuyên đề “Một số thuật toán tổ hợp” Lê Hồng Phương1 1Khoa Toán–Cơ–Tin học Trường Đại học Khoa học Tự nhiên, ĐHQG Hà Nội 08/2012 Lê Hồng Phương (HUS, VNU) 08/2012 1 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 2 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 3 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 4 / 75 Phân hoạch Thuật ngữ phân hoạch Các số liên quan tới phân hoạch: số Bell, số Stirling loại hai và loại một. Thuật toán sinh các phân hoạch Lê Hồng Phương (HUS, VNU) 08/2012 5 / 75 Giới thiệu Thuật ngữ “phân hoạch” định nghĩa hai kiểu đối tượng tổ hợp khác nhau: Phân hoạch tập hợp (set partition) Phân hoạch nguyên (integer partition) Phân hoạch tập hợp chia các phần tử của tập {1, 2, . . . , n} thành các tập con khác rỗng. Ví dụ, có 15 phân hoạch với n = 4. {1234}, {123, 4}, {124, 3}, {12, 34}, {12, 3, 4}, {134, 2}, {13, 24}, {13, 2, 4}, {14, 23}, {1, 234}, {1, 23, 4}, {14, 2, 3}, {1, 24, 3}, {1, 2, 34}, {1, 2, 3, 4} : Lê Hồng Phương (HUS, VNU) 08/2012 6 / 75 Giới thiệu Phân hoạch nguyên của số tự nhiên n là các tập số nguyên khác 0 cộng lại đúng bằng n. Ví dụ, có 7 phân hoạch nguyên khác nhau của 5 là {5}, {4, 1}, {3, 2}, {3, 1, 1}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}. Một ứng dụng lí thú của phân hoạch nguyên trong mô phỏng phân rã hạt nhân: Khi một nguyên tử bị va chạm mạnh các proton và neutron bị phân rã thành một tập các cụm hạt nhỏ hơn. Tổng các hạt trong các cụm này phải bằng khối lượng ban đầu của hạt nhân. Như vậy, các phân hoạch nguyên của khối lượng ban đầu này biểu diễn mọi cách phân rã nguyên tử. Lê Hồng Phương (HUS, VNU) 08/2012 7 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 8 / 75 Phân hoạch tập hợp Gọi S là tập có n phần tử. Mỗi phân hoạch của tập S được định nghĩa là tập k tập con S1, S2, . . . , Sk khác rỗng của S đôi một rời nhau và hợp của chúng là S: S = k⋃ i=1 Si, Si 6= ∅, Si ∩ Sj = ∅, ∀i, j = 1, 2, . . . , k. Có nhiều bài toán được quy về bài toán phân hoạch tập hợp: tô màu các đỉnh của đồ thị, tìm các thành phần liên thông của đồ thị. . . 1 1S. S. Skiena, The Algorithm Design Manual, 2nd ed. Springer-Verlag London, 2008. Lê Hồng Phương (HUS, VNU) 08/2012 9 / 75 Phân hoạch tập hợp Các phân hoạch của 5 phần tử: Lê Hồng Phương (HUS, VNU) 08/2012 10 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 11 / 75 Các số Bell Số Bell thứ n2 là số phân hoạch của một tập hợp có n phần tử. Đây chính là số các quan hệ tương đương xác định trên tập này. Các số Bell đầu tiên là 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975 . . . Gọi Bn là số Bell thứ n. Với n = 3, và tập S = {a, b, c}, ta có B3 = 5 vì có 5 cách phân hoạch {{a}, {b}, {c}} {{a}, {b, c}} {{b}, {a, c}} {{c}, {a, b}} {{a, b, c}}. 2Được đặt tên theo tên nhà toán học Mỹ Eric Temple Bell (1883–1960). Lê Hồng Phương (HUS, VNU) 08/2012 12 / 75 Các số Bell B0 = 1 vì chỉ có 1 phân hoạch của tập rỗng. Mọi tập con của một tập rỗng là tập rỗng và hợp của chúng là tập rỗng. Do đó tập rỗng chính là phân hoạch duy nhất của chính nó. Chú ý rằng ở trên ta dùng kí hiệu tập hợp ({, }) để biểu diễn các phân hoạch nên thứ tự của các phân hoạch cũng như thứ tự của các phần tử trong mỗi phân hoạch là không quan trọng. Các cách phân hoạch dưới đây đều tương đương nhau: {{b}, {a, c}} {{a, c}, b} {{b}, {c, a}} {{c, a}, {b}}. Lê Hồng Phương (HUS, VNU) 08/2012 13 / 75 Các số Bell – Công thức truy hồi Các số Bell thỏa mãn công thức truy hồi sau: Bn+1 = n∑ k=0 ( n k ) Bk. Ta có thể chứng minh công thức này bằng lập luận như sau: Bn+1 là số cách phân hoạch tập {1, 2, . . . , n, n + 1}. Mỗi phân hoạch đều có chứa một tập A nào đó chứa phần tử n+ 1. Bn+1 chính là số cách phân hoạch tập S trong đó có chứa khối A. Nói cách khác, Bn+1 chính là số cách phân hoạch tập S \A. Tập S \ A có thể có các lực lượng k chạy từ 0 tới n, tương ứng với các trường hợp A ≡ S hoặc A ≡ {n+ 1}. Với mỗi k ta có ( n k ) cách chọn tập con k phần tử của tập S \A và Bk cách phân hoạch tập con đó nên ta có công thức trên. Lê Hồng Phương (HUS, VNU) 08/2012 14 / 75 Các số Bell – Công thức truy hồi Các số Bell thỏa mãn công thức truy hồi sau: Bn+1 = n∑ k=0 ( n k ) Bk. Ta có thể chứng minh công thức này bằng lập luận như sau: Bn+1 là số cách phân hoạch tập {1, 2, . . . , n, n + 1}. Mỗi phân hoạch đều có chứa một tập A nào đó chứa phần tử n+ 1. Bn+1 chính là số cách phân hoạch tập S trong đó có chứa khối A. Nói cách khác, Bn+1 chính là số cách phân hoạch tập S \A. Tập S \ A có thể có các lực lượng k chạy từ 0 tới n, tương ứng với các trường hợp A ≡ S hoặc A ≡ {n+ 1}. Với mỗi k ta có ( n k ) cách chọn tập con k phần tử của tập S \A và Bk cách phân hoạch tập con đó nên ta có công thức trên. Lê Hồng Phương (HUS, VNU) 08/2012 14 / 75 Các số Bell – Công thức Dobinski Các số Bell cũng thỏa mãn công thức Dobinski: Bn = 1 e ∞∑ k=1 kn k! . Đây chính là moment bậc n của phân phối Poisson với kì vọng bằng 1. Xem chứng minh các công thức này trong các tài liệu: G. Dobinski, “Summirung der reihe ∑ nm n! fu¨r m = 1, 2, 3, 4, 5, . . . ,,” Grunert’s Archiv, vol. 61, pp. 333–336, 1877. G.-C. Rota, “The number of partitions of a set,” American Mathematical Monthly, vol. 71, no. 5, pp. 498–504, 1964. Lê Hồng Phương (HUS, VNU) 08/2012 15 / 75 Các số Bell – Công thức Dobinski Các số Bell cũng thỏa mãn công thức Dobinski: Bn = 1 e ∞∑ k=1 kn k! . Đây chính là moment bậc n của phân phối Poisson với kì vọng bằng 1. Xem chứng minh các công thức này trong các tài liệu: G. Dobinski, “Summirung der reihe ∑ nm n! fu¨r m = 1, 2, 3, 4, 5, . . . ,,” Grunert’s Archiv, vol. 61, pp. 333–336, 1877. G.-C. Rota, “The number of partitions of a set,” American Mathematical Monthly, vol. 71, no. 5, pp. 498–504, 1964. Lê Hồng Phương (HUS, VNU) 08/2012 15 / 75 Tam giác Bell Các số Bell được tính từ lược đồ tam giác như sau: 1 1 2 2 3 5 5 7 10 15 15 20 27 37 52 · · · · · · · · · Quy tắc điền? Lê Hồng Phương (HUS, VNU) 08/2012 16 / 75 Tam giác Bell Tam giác này được điền theo lược đồ sau: Hàng đầu tiên chứa số 1, là số Bell đầu tiên; Với mọi i ≥ 1, hàng thứ i+ 1 được điền như sau: Chép số cuối cùng của hàng thứ i đặt lên đầu hàng i+ 1; Với mọi j > 1, số thứ j của hàng i+ 1 là tổng của số thứ j − 1 của hàng i+ 1 và số thứ j − 1 của hàng i. Số cuối cùng của hàng i+ 1 là số Bell của hàng đó. a b a+ b Lê Hồng Phương (HUS, VNU) 08/2012 17 / 75 Các giới hạn và cận của các số Bell D. Berend và T. Tassa3 đưa ra các cận sau: Bn < ( 0.792n ln(n+ 1) )n . Ngoài ra, nếu ǫ > 0, thì ∀n > n0(ǫ): Bn < ( e−0.6+ǫn ln(n+ 1) )n , trong đó n0(ǫ) = max { e4, d−1(ǫ) } , d(x) = ln ln(x+ 1)− ln lnx+ 1 + e −1 lnx . 3D. Berend and T. Tassa, “Improved bounds on Bell numbers and on moments of sums of random variables,” Probability and Mathematical Statistics, vol. 30, no. 2, pp. 185–205, 2010. Lê Hồng Phương (HUS, VNU) 08/2012 18 / 75 Các giới hạn và cận của các số Bell L. Lovász đưa ra xấp xỉ của các số Bell như sau4: Bn ≈ 1√ n [λ(n)]n+ 1 2 eλ(n)−n−1, với λ(n) = n W (n) , trong đó W là hàm Lambert W .5 Tham khảo thêm một số tính chất khác của số Bell ở địa chỉ: 4L. Lovász, Combinatorial Problems and Exercises, 2nd ed. Amsterdam, Neitherlands: North-Holland, 1993. 5Hàm Lambert W , còn gọi là hàm Omega, là một tập hàm W (z) thoả mãn z = W (z)eW (z),∀z ∈ Z. Lê Hồng Phương (HUS, VNU) 08/2012 19 / 75 Bài tập Bài tập 1. Viết chương trình tính và hiển thị tam giác Bell. Bài tập 2. Viết chương trình in ra bảng xấp xỉ cận của các số Bell dựa trên công thức của D. Berend và T. Tassa. Lê Hồng Phương (HUS, VNU) 08/2012 20 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 21 / 75 Các số Stirling loại hai Các số Stirling6, xuất hiện trong nhiều bài toán tổ hợp. Có hai tập số mang tên ông là các số Stirling loại một và các số Stirling loại hai. Các số Stirling loại hai đếm số cách phân hoạch của một tập thành k tập con khác rỗng. Số này thường được kí hiệu là { n k } hoặc S(n, k). Các số này có thể được tính bởi công thức 1 k! k∑ j=0 (−1)k−j ( k j ) jn. 6Được đặt theo tên nhà toán học James Stirling người Scotland, 1692–1770. Lê Hồng Phương (HUS, VNU) 08/2012 22 / 75 Các số Stirling loại hai Các số Stirling6, xuất hiện trong nhiều bài toán tổ hợp. Có hai tập số mang tên ông là các số Stirling loại một và các số Stirling loại hai. Các số Stirling loại hai đếm số cách phân hoạch của một tập thành k tập con khác rỗng. Số này thường được kí hiệu là { n k } hoặc S(n, k). Các số này có thể được tính bởi công thức 1 k! k∑ j=0 (−1)k−j ( k j ) jn. 6Được đặt theo tên nhà toán học James Stirling người Scotland, 1692–1770. Lê Hồng Phương (HUS, VNU) 08/2012 22 / 75 Các số Stirling loại hai Sơ đồ Hasse: S(4, 1) = 1, S(4, 2) = 7, S(4, 3) = 6, S(4, 4) = 1. Lê Hồng Phương (HUS, VNU) 08/2012 23 / 75 Các số Stirling loại hai Mỗi số Bell là tổng của các số Stirling loại hai : Bn = n∑ k=0 { n k } = n∑ k=0 1 k! k∑ j=0 (−1)k−j ( k j ) jn. Các số Stirling loại hai thỏa mãn công thức truy hồi sau:{ n+ 1 k } = k { n k } + { n k − 1 } , với k > 0 và điều kiện ban đầu là{ 0 0 } = 1, { n 0 } = { 0 n } = 0 với n > 0. Lê Hồng Phương (HUS, VNU) 08/2012 24 / 75 Các số Stirling loại hai Mỗi số Bell là tổng của các số Stirling loại hai : Bn = n∑ k=0 { n k } = n∑ k=0 1 k! k∑ j=0 (−1)k−j ( k j ) jn. Các số Stirling loại hai thỏa mãn công thức truy hồi sau:{ n+ 1 k } = k { n k } + { n k − 1 } , với k > 0 và điều kiện ban đầu là{ 0 0 } = 1, { n 0 } = { 0 n } = 0 với n > 0. Lê Hồng Phương (HUS, VNU) 08/2012 24 / 75 Các số Stirling loại hai Chứng minh công thức này bằng lập luận: Mỗi phân hoạch của tập n+ 1 phần tử thành k tập con khác rỗng có hai khả năng, hoặc chứa tập con {n+ 1} hoặc không chứa. Số cách phân hoạch trong đó có chứa tập con {n + 1} là { n k−1 } vì ta phân hoạch n phần tử còn lại thành k − 1 tập con. Số cách phân hoạch trong đó không chứa tập con {n + 1} là k{n k } vì ta phân hoạch mọi phần tử khác n+ 1 thành k tập con và sau đó có k cách để chèn phần tử n+ 1 vào một trong các tập con này. Tổng của hai giá trị ứng với hai khả năng trên cho ta kết quả cần chứng minh. { n+ 1 k } = k { n k } + { n k − 1 } . Lê Hồng Phương (HUS, VNU) 08/2012 25 / 75 Các số Stirling loại hai Từ công thức truy hồi này, ta có thể tính các số Stirling dựa vào “tam giác Stirling”: n \ k 0 1 2 3 4 5 6 7 8 9 10 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1 7 0 1 63 301 350 140 21 1 8 0 1 127 966 1701 1050 266 28 1 9 0 1 255 3025 7770 6951 2646 462 36 1 10 0 1 511 9330 34105 42525 22827 5880 750 45 1 Bài tập 3. Viết chương trình tính và hiển thị tam giác Stirling loại hai. Lê Hồng Phương (HUS, VNU) 08/2012 26 / 75 Một số đẳng thức Ta có: { n n− 1 } = ( n 2 ) . Dễ thấy đẳng thức này đúng vì việc phân chia một tập n phần tử thành n− 1 tập con chính là việc phân chia tập đó thành một tập có 2 hai phần tử và n− 2 tập con khác. Vì vậy, số cách phân chia chính là số cách chọn 2 phần tử trong số n phần tử. Lê Hồng Phương (HUS, VNU) 08/2012 27 / 75 Một số đẳng thức Ta có: { n 2 } = 2n−1 − 1. Công thức này được lí giải như sau: Mỗi cách phân hoạch tập X gồm n phần tử thành hai tập con A và B thì hai tập con đó là các tập bù của nhau, tức là A = X \ B. Có 2n cặp tập (A,B) có thứ tự, bao gồm cả hai cặp (∅,B) và (A, ∅). Như vậy, nếu không tính hai cặp này thì có 2n − 2 cặp tập bù nhau có thứ tự. Vì trong phân hoạch ta không xét thứ tự các cặp nên số cặp không có thứ tự là (2n − 2)/2 = 2n−1 − 1. Lê Hồng Phương (HUS, VNU) 08/2012 28 / 75 Tham khảo thêm Các số Stirling loại hai xuất hiện trong nhiều bài toán tổ hợp và có ứng dụng trong lí thuyết thống kê, xem thêm một số ứng dụng của chúng trong A. H. Joarder and M. Mahmood, “An inductive derivation of Stirling numbers of the second kind and their applications in statistics,” Journal of Applied Mathematics and Decision Sciences, vol. 1, no. 2, pp. 151–157, 1997. P. L. Butzer and M. Hauss, “Stirling functions of the first and second kinds; some new applications,” in Israel Mathematical Conference Proceedings: Approximation, Interpolation, and Summability, in Honor of Amnon Jakimovski on his Sixty-Fifth Birthday, Ramat Gan, Israel, 1991, pp. 89–108. Lê Hồng Phương (HUS, VNU) 08/2012 29 / 75 Nội dung 1 Giới thiệu Phân hoạch 2 Phân hoạch tập hợp Các số Bell Các số Stirling loại hai Các số Stirling loại một Sinh các phân hoạch tập hợp 3 Phân hoạch nguyên Hàm phân hoạch Lược đồ Ferrers Sinh các phân hoạch nguyên 4 Tóm lược Lê Hồng Phương (HUS, VNU) 08/2012 30 / 75 Các số Stirling loại một Các số Stirling (không dấu) loại một, kí hiệu bởi [ n k ] hoặc s(n, k), là số hoán vị của n phần tử với k chu trình rời nhau. Chu trình của mỗi hoán vị? Định nghĩa (Định nghĩa số 1 về hoán vị vòng tròn) Mỗi hoán vị σ trên tập S gồm k phần tử được gọi là một hoán vị vòng tròn với độ lệch t khi và chỉ khi có thể sắp các phần tử của tập S theo thứ tự x1 < x2 < · · · < xk sao cho σ(xi) = xi+t, ∀i = 1, 2, . . . , k − t; σ(xi) = xi+t−k, ∀i = k − t+ 1, k − t+ 2, . . . , k. Lê Hồng Phương (HUS, VNU) 08/2012 31 / 75 Các số Stirling loại một Các số Stirling (không dấu) loại một, kí hiệu bởi [ n k ] hoặc s(n, k), là số hoán vị của n phần tử với k chu trình rời nhau. Chu trình của mỗi hoán vị? Định nghĩa (Định nghĩa số 1 về hoán vị vòng tròn) Mỗi hoán vị σ trên tập S gồm k phần tử được gọi là một hoán vị vòng tròn với độ lệch t khi và chỉ khi có thể sắp các phần tử của tập S theo thứ tự x1 < x2 < · · · < xk sao cho σ(xi) = xi+t, ∀i = 1, 2, . . . , k − t; σ(xi) = xi+t−k, ∀i = k − t+ 1, k − t+ 2, . . . , k. Lê Hồng Phương (HUS, VNU) 08/2012 31 / 75 Hoán vị vòng tròn Ví dụ, xét hoán vị σ = ( 1 2 3 4 5 6 7 8 3 4 5 7 6 1 8 2 ) . Ta có thể sắp lại hoán vị này theo thứ tự sau: σ = ( 1 2 3 4 5 7 6 8 3 4 5 7 6 8 1 2 ) . Tức là ta sử dụng thứ tự x6 = 7, x7 = 6 và xi = i,∀i 6= 6, 7. Ta thấy hoán vị này là hoán vị vòng tròn với độ lệch t = 2 như sơ đồ sau: 1 −−−−→ 3x y 6 ←−−−− 5 2 −−−−→ 4x y 8 ←−−−− 7 Lê Hồng Phương (HUS, VNU) 08/2012 32 / 75 Hoán vị vòng tròn Ví dụ, xét hoán vị σ = ( 1 2 3 4 5 6 7 8 3 4 5 7 6 1 8 2 ) . Ta có thể sắp lại hoán vị này theo thứ tự sau: σ = ( 1 2 3 4 5 7 6 8 3 4 5 7 6 8 1 2 ) . Tức là ta sử dụng thứ tự x6 = 7, x7 = 6 và xi = i,∀i 6= 6, 7. Ta thấy hoán vị này là hoán vị vòng tròn với độ lệch t = 2 như sơ đồ sau: 1 −−−−→ 3x y 6 ←−−−− 5 2 −−−−→ 4x y 8 ←−−−− 7 Lê Hồng Phương (HUS, VNU) 08/2012 32 / 75 Hoán vị vòng tròn Ta có σ(x1) = σ(1) = 3 = x3 σ(x2) = σ(2) = 4 = x4 σ(x3) = σ(3) = 5 = x5 σ(x4) = σ(4) = 7 = x6 σ(x5) = σ(5) = 6 = x7 σ(x6) = σ(7) = 8 = x8 Và σ(x7) = σ(6) = 1 = x1 σ(x8) = σ(8) = 2 = x2 Ta có hai chu trình kí hiệu là (1356) và (2478). Lê Hồng Phương (HUS, VNU) 08/2012 33 / 75 Hoán vị vòng tròn Chú ý rằng nếu σ là một hoán vị vòng tròn với độ lệch t thì nó có thể được xây dựng với đúng s chu trình có độ dài bằng nhau, trong đó s là ước chung lớn nhất của k và t. Ngoài định nghĩa cơ bản trên, ta còn gặp một số định nghĩa khác về hoán vị vòng tròn. Các định nghĩa này tuy hơi khác nhau như