Tài liệu Số stirling loại hai và số bell cho các đồ thị

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NÔNG MẠNH LINH SỐ STIRLING LOẠI HAI VÀ SỐ BELL CHO CÁC ĐỒ THỊ LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NÔNG MẠNH LINH SỐ STIRLING LOẠI HAI VÀ SỐ BELL CHO CÁC ĐỒ THỊ Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. ĐÀM VĂN NHỈ Thái Nguyên - 2015 LỜI CẢM ƠN Luận văn được thực hiện và hoàn thành tại trường Đại học Khoa Học-Đại học Thái Nguyên. Qua đây tôi xin chân thành cảm ơn các thầy cô giáo Khoa Toán-Tin, Ban Giám hiệu, Phòng Đào tạo nhà trường đã trang bị kiến thức cơ bản và tạo điều kiện tốt nhất cho tôi trong quá trình học tập và nghiên cứu. Tôi xin bày tỏ lòng biết ơn chân thành tới PGS. TS. Đàm Văn Nhỉ, người đã tận tình chỉ bảo, tạo điều kiện và giúp đỡ tôi có thêm nhiều kiến thức, khả năng nghiên cứu, tổng hợp tài liệu để hoàn thành luận văn. Tôi xin cảm ơn các thầy, cô giáo trong hội đồng chấm luận văn đã đóng góp cho tôi những ý kiến quý giá giúp tôi hoàn thiện luận văn này. Tôi cũng xin gửi lời cảm ơn đến gia đình, bạn bè và các đồng nghiệp đã động viên, giúp đỡ tôi quá trình học tập của mình. Tôi xin chân thành cảm ơn! 1 Mục lục Mở đầu 3 1 Kiến thức chuẩn bị 1.1 Đồ thị và đường đi . . . . . . . . . . . . . 1.1.1 Khái niệm đồ thị . . . . . . . . . . 1.1.2 Đường đi và chu trình . . . . . . . 1.1.3 Bậc của đỉnh và tính liên thông của 1.2 Số Stirling loại 2 của phân hoạch . . . . . . . . . . . . . . . . . đồ thị . . . . 2 Số Stiling và số Bell của đồ thị 2.1 Số χ(G) . . . . . . . . . . . . . . . . . . . . . 2.1.1 Bài toán tô màu cạnh đồ thị . . . . . . 2.1.2 Đa thức màu (chromatic polynomials) 2.2 Số Stiling loại hai và số Bell của đồ thị . . . . 2.2.1 Số Stiling loại hai và số Bell của đồ thị 2.2.2 Một số ví dụ . . . . . . . . . . . . . . . 2.2.3 Số r-Stirling loại hai và số r-Bell . . . 2.3 Đa thức r-Bell . . . . . . . . . . . . . . . . . . 2.3.1 Mở rộng truy hồi (2.11) . . . . . . . . 2.3.2 Số Bell . . . . . . . . . . . . . . . . . . 2.3.3 Đa thức Bell . . . . . . . . . . . . . . . 2.3.4 Chuỗi hệ thức ngược . . . . . . . . . . 2.3.5 Hàm sinh mũ . . . . . . . . . . . . . . 2.3.6 Đa thức r-Bell . . . . . . . . . . . . . . 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 6 7 10 . . . . . . . . . . . . . . 16 16 16 18 19 19 23 25 27 28 32 34 35 37 40 Mở đầu Lý thuyết tổ hợp là một phần quan trọng của toán học rời rạc nghiên cứu về sự sắp xếp các phần tử trong các tập hữu hạn và sự phân bố của các phần tử vào các tập hữu hạn. Mỗi cách sắp xếp hoặc phân bố như thế được gọi là một cấu hình tổ hợp. Các cấu hình đó là các hoán vị, chỉnh hợp, tổ hợp,... các phần tử của một tập hợp. Toán học tổ hợp liên quan đến cả khía cạnh giải quyết vấn đề lẫn xây dựng cơ sở lý thuyết, Một trong những mảng lâu đời nhất của toán học tổ hợp là lý thuyết đồ thị. Lý thuyết đồ thị là một ngành toán học hiện đại, gắn kết nhiều ngành khoa học với nhau. Các thuật toán ngắn gọn và thú vị của lý thuyết đồ thị giúp chúng ta giải quyết rất nhiều bài toán phức tạp trong thực tế. Vì tầm quan trọng của nó trong các ứng dụng khác nhau, các nhà toán học đã nỗ lực tìm công thức tính số phân hoạch một tập hợp. Một trong những công thức tính số phân hoạch đầu tiên thuộc về nhà toán học tên tuổi Eric Temple Bell (1883-1960). Số phép phân hoạch một tập hợp n phần tử được gọi là số Bell, được kí hiệu là Bn . Để tính số Bell, ta cần tính số phân hoạch tập hợp X gồm n phần tử vào k tập con (hay k khối) khác rỗng, tức là cần tính số Stirling loại hai. Số Stirling được đặt tên theo nhà toán học James Stirling (1692-1770), đã được đề cập trong cuốn sách "Methodus differentialis, sive Tractatus de Summatine et Interpolatione Serireun Infinitarum". Trong luận văn này chúng ta chủ yếu nghiên cứu về số Bell; số Stirling loại hai và các ứng dụng của chúng vào một số lĩnh vực khác nhau của toán học. Luận văn bao gồm hai chương, phần mở đầu, kết luận và tài liệu tham khảo. Chương 1: Kiến thức chuẩn bị. Trong chương 1 chúng tôi trình bày các khái niệm cơ bản về tập hợp, phép phân hoạch của một tập hợp và 3 giới thiệu sơ lược về số Bell và số Stirling. Đồng thời cũng chỉ ra mối liên hệ giữa số Stirling loại hai và số toàn ánh. Chương 2: Số Stiling loại hai và số Bell của đồ thị. Trong chương 2 chúng tôi trình bày cách xác định các số Bell và số Stirling loại hai của đồ thị và đưa ra các ví dụ cụ thể. Đồng thời cũng giới thiệu về bài toán tô màu cạnh đồ thị, đa thức màu (chromatic polynomials). Ngoài ra, chúng tôi cũng đề cập đến khai triển hàm ban đầu f (n) như một tổ hợp tuyến tính của hệ số nhị thức với đa thức hệ số Arj (n) và đa thức Bn được biểu diễn theo các hệ số nhị thức Arj (n). Thái Nguyên, ngày 10 tháng 01 năm 2016. Người thực hiện Nông Mạnh Linh 4 Chương 1 Kiến thức chuẩn bị 1.1 1.1.1 Đồ thị và đường đi Khái niệm đồ thị Lý thuyết đồ thị là một ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ 18 bởi nhà toán học L. Euler, người Thụy sĩ. Ông cũng là .. người đã sử dụng đồ thị để giải quyết bài toán cầu Konigsberg nổi tiếng. Nhờ Lý thuyết đồ thị mà nhiều bài toán phức tạp, diễn giải dài dòng được mô tả hình học một cách trực quan và cô đọng. Các thuật toán ngắn gọn và trực quan của Lý thuyết đồ thị đã giúp chúng ta giải quyết rất nhiều bài toán phức tạp trong thực tế. Định nghĩa 1.1. Đồ thị là một cặp G = (V, E), trong đó (1) V là tập hợp các phần tử, chúng được gọi là các đỉnh. (2) E ⊆ V × V là tập hợp các phần tử, chúng được gọi là các cạnh. Về bản chất, đồ thị là một tập hợp các đối tượng được biểu diễn bằng các đỉnh và giữa các đối tượng này có một mối quan hệ nhị nguyên biểu diễn bằng các cạnh. Với hai đỉnh x, y ∈ V, đoạn thẳng hay đoạn cong nối x và y biểu thị cạnh (x, y) của đồ thị. Nếu cặp đỉnh x, y tạo thành một cạnh của đồ thị và hai đỉnh này không sắp thứ tự thì cạnh (x, y) được gọi là cạnh vô hướng; còn nếu chúng sắp thứ tự thì cạnh được viết thành [x, y] và được gọi là cạnh có hướng. Người ta thường phân đồ thị thành hai lớp. 5 Định nghĩa 1.2. Đồ thị chỉ chứa các cạnh vô hướng được gọi là đồ thị vô hướng. Đồ thị chỉ chứa các cạnh có hướng được gọi là đồ thị có hướng. Hiển nhiên, mỗi đồ thị vô hướng có thể biểu diễn bằng một đồ thị có hướng bằng cách thay mỗi cạnh vô hướng (x, y) bằng hai cạnh có hướng tương ứng [x, y] và [y, x]. Định nghĩa 1.3. Đồ thị G = (V, E) được gọi là đồ thị đối xứng nếu (x, y) ∈ E, ([x, y] ∈ E), thì (y, x) ∈ E, ([y, x] ∈ E). Dễ dàng thấy rằng, các đồ thị vô hướng đều là đối xứng. Định nghĩa 1.4. Đồ thị G = (V, E), trong đó mỗi cặp đỉnh được nối với nhau bởi không quá một cạnh được gọi là đơn đồ thị hay đồ thị. Nếu đồ thị có những cặp đỉnh được nối với nhau nhiều hơn một cạnh thì được gọi là đa đồ thị. Đồ thị được gọi là đồ thị hữu hạn nếu tập các đỉnh hữu hạn. Trong luận văn này chúng ta giới hạn chỉ xét các đồ thị hữu hạn. Ta ký hiệu n là số đỉnh, m là số cạnh của một đồ thị hữu hạn. 1.1.2 Đường đi và chu trình Giả sử G = (V, E) là một đồ thị. Định nghĩa 1.5. Đường đi trên một đồ thị G đã cho là một dãy các đỉnh < x1 , x2 , . . . , xi , xi+1 , . . . , xk−1 , xk > sao cho, mỗi đỉnh trong dãy (không kể đỉnh đầu tiên) kề với đỉnh trước nó bằng một cạnh nào đó, nghĩa là: Với mọi i = 2, 3, . . . , k − 1, k ta đều có cạnh (xi−1 , xi ) ∈ E. Với đường đi < x1 , x2 , . . . , xi , xi+1 , . . . , xk−1 , xk >, ta nói rằng, đường đi này đi từ đỉnh đầu x1 đến đỉnh cuối xk . Số cạnh trên đường đi gọi là độ dài của đường đi đó. Đường đi đơn là đường đi mà các đỉnh của nó khác nhau từng đôi một. Định nghĩa 1.6. Chu trình là một đường đi khép kín, có nghĩa, đỉnh đầu của đường đi trùng với đỉnh cuối của đường đi. Chu trình được gọi là chu trình đơn nếu các đỉnh của nó khác nhau từng đôi. Ta thường ký hiệu chu trình qua [x1 , x2 , ..., xi , xi+1 , .., xk−1 , xk ], trong đó x1 ≡ xk . Để thu gọn, trong ký hiệu của chu trình ta thường không viết đỉnh cuối [x1 , x2 , ..., xi , xi+1 , .., xk−1 ]. 6 Trong một đồ thị, đỉnh nút là đỉnh kề với chính nó. Hai cạnh có ít nhất một đỉnh chung được gọi là hai cạnh kề nhau. 1.1.3 Bậc của đỉnh và tính liên thông của đồ thị Định nghĩa 1.7. Cho đồ thị G= (V, E). Đồ thị G0 = (V 0 , E 0 ) được gọi V 0 ⊆ V là đồ thị con của đồ thị G nếu E 0 = E ∩ (V × V 0 ). Đồ thị G00 = (V, E 00 ), E 00 ⊆ E, được gọi là đồ thị riêng của đồ thị G. Như vậy, mỗi tập con các đỉnh V 0 của đồ thị G tương ứng duy nhất với một đồ thị con của nó. Do vậy, để xác định một đồ thị con ta chỉ cần nêu tập đỉnh của nó. Còn đồ thị riêng là đồ thị giữ nguyên tập đỉnh và bỏ bớt đi một số cạnh. Định nghĩa 1.8. Hai đồ thị G1 = (V1 , E1 ) và G2 = (V2 , E2 ) được gọi là đẳng hình với nhau nếu có một song ánh S : V1 → V2 , x 7→ S(x), trên tập các đỉnh, bảo toàn quan hệ các cạnh, có nghĩa: Với mọi x, y ∈ V1 , cạnh (x, y) ∈ E1 khi và chỉ khi (S(x), (S(y)) ∈ E2 . Người ta thường không phân biệt hai đồ thị đẳng hình với nhau vì về thực chất chúng chỉ khác nhau tên gọi của các đỉnh và cách biểu diễn bằng hình vẽ. Định nghĩa 1.9. Cho đồ thị G = (V, E). Ta có định nghĩa sau: (1) Hai đỉnh của đồ thị G được gọi là liên thông nếu trên đồ thị có đường đi vô hướng nối chúng với nhau. (2) Đồ thị G được gọi là liên thông nếu mọi cặp đỉnh của đồ thị đều liên thông với nhau. (3) Đồ thị có hướng G được gọi là liên thông mạnh nếu mọi cặp đỉnh đều có đường đi có hướng nối chúng với nhau.. (4) Số cạnh kề với đỉnh a ∈ V được gọi là bậc của đỉnh a trong đồ thị G và được ký hiệu qua deg(a). Riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Đỉnh bậc 0 được gọi là đỉnh cô lập; Đỉnh bậc 1 được gọi là đỉnh treo. 7 Quan hệ liên thông trên tập đỉnh là một quan hệ tương đương. Nó tạo nên một phân hoạch trên tập các đỉnh. Mỗi lớp tương đương của quan hệ này được gọi là một mảng liên thông (hay thành phần liên thông) của đồ thị. Định nghĩa 1.10. Đồ thị được gọi là đầy đủ nếu hai đỉnh bất kỳ đều có cạnh nối. Người ta thường ký hiệu đồ thị vô hướng đầy đủ n đỉnh là Kn . Trong đồ thị đầy đủ Kn mỗi đỉnh đều có bậc là n − 1 và đồ thị là liên thông. Hai đỉnh bất kỳ được nối với nhau bằng một đường đi ngắn nhất có độ dài bằng 1. Đó chính là cạnh nối hai đỉnh ấy. Định lý 1.1. Giữa mọi cặp đỉnh phân biệt của một đồ thị G = (V, E), n = |V | > 2, vô hướng liên thông luôn có đường đi đơn. Chứng minh: Giả sử x, y là hai đỉnh phân biệt của đồ thị vô hướng liên thông G. Ta có ít nhất một đường đi giữa x và y. Gọi x0 , x1 , . . . , xk với x0 = x, xk = y là dãy các đỉnh của đường đi có độ dài ngắn nhất (bao giờ cũng có). Đây chính là đường đi đơn cần tìm. Thật vậy, giả sử nó không là đường đi đơn. Khi đó xi = xj với 0 6 i < j. Điều này có nghĩa là giữa các đỉnh x và y có đường đi ngắn hơn nữa qua các đỉnh x0 , x1 , . . . , xi−1 , xj , . . . , xk nhận được bằng cách xóa đi các cạnh tương ứng với dãy các đỉnh xi , . . . , xj−1 . Định lý 1.2. Đồ thị n > 2 đỉnh không có đỉnh nút có ít nhất hai đỉnh cùng bậc. Chứng minh: Xét 3 trường hợp dưới đây: (i) Trường hợp 1: Đồ thị có đỉnh bậc 0, có nghĩa: Đồ thị có đỉnh cô lập. Khi đó đỉnh của các bậc chỉ có thể là: 0, 1, 2, ..., n − 2. Số các bậc khác nhau nhiều nhất là n − 1. (ii) Trường hợp 2: Đồ thị có đỉnh bậc n − 1. Khi đó đồ thị không có đỉnh cô lập. Vậy, bậc của các đỉnh chỉ có thể là 0, 1, 2, ..., n − 1. Số các bậc khác nhau nhiều nhất cũng là n − 1. (iii) Trường hợp 3: Đồ thị không có đỉnh bậc 0 và đỉnh bậc n − 1. Khi đó, số các bậc khác nhau nhiều nhất cũng là n − 1. Trong cả ba trường hợp, số các bậc khác nhau không quá n − 1. Như vậy ít nhất phải có hai đỉnh chung một bậc theo Nguyên lý Dirichlet. 8 Định lý 1.3. Đồ thị với n > 4 đỉnh không có đỉnh nút và có đúng hai đỉnh cùng bậc thì hai đỉnh này không thể đồng thời có bậc 0 hoặc bậc n − 1. Chứng minh: Ta chứng minh bằng phản chứng. Giả sử đồ thị trên có hai đỉnh cùng bậc 0 hay bậc n−1. Loại hai đỉnh cùng bậc 0 hay bậc n−1 này đi, ta được đồ thị G0 . Theo Định lý 1.2, đồ thị G0 có hai đỉnh cùng bậc. Hai đỉnh này cũng cùng bậc trong G. Mâu thuẫn với giả thiết. Định lý 1.4. Tổng tất cả các bậc của các đỉnh trong một đồ thị bằng hai lần số cạnh của đồ thị. Chứng minh: Ta tính bậc của các đỉnh. Mỗi đỉnh thuộc một cạnh nào đó thì bậc của nó tăng thêm 1. Vì mỗi cạnh có hai đỉnh nên tổng tất cả các bậc của các đỉnh trong một đồ thị bằng hai lần số cạnh của đồ thị. Hệ quả 1.1. Số đỉnh có bậc lẻ trong một đồ thị phải là một số chẵn. Chứng minh: Nếu số đỉnh có bậc lẻ trong một đồ thị là một số lẻ thì tổng tất cả các bậc của các đỉnh trong một đồ thị là một số lẻ: Mâu thuẫn theo Định lý 1.4. Vậy, số đỉnh có bậc lẻ trong một đồ thị phải là một số chẵn. Hệ quả 1.2. Nếu đồ thị G có đúng hai đỉnh bậc lẻ thì hai đỉnh đó phải liên thông với nhau. Chứng minh: Giả sử hai đỉnh đó là a và b. Xét mảng liên thông G0 chứa a. Bậc của mỗi đỉnh trong G0 bằng bậc của mỗi đỉnh đó trong G. Nếu b ∈ / G0 thì trong G0 chỉ có một đỉnh bậc lẻ, trái với Hệ quả 1.1. Vậy b phải thuộc mảng liên thông G0 chứa a. Ví dụ 1.1. Có bao nhiêu cạnh trong một đồ thị có 10 đỉnh và mỗi đỉnh có bậc bằng 6? Bài giải: Gọi số cạnh của đồ thị bằng m. Theo Định lý 1.4 ta có 2m = 10.6 = 60. Vậy m = 30. Ví dụ 1.2. Giả sử đồ thị G = (V, E) có n đỉnh và m cạnh. Ký hiệu r, s là bậc lớn nhất và bậc nhỏ nhất của các đỉnh của G. Khi đó ta có các 2m bất đẳng thức s 6 6 r. n 9 Bài giải: Hiển nhiên 2m = n P deg(xi ) theo Định lý 1.4. i=1,xi ∈V Vậy ns 6 2m 6 nr và suy ra s 6 1.2 2m 6 r. n Số Stirling loại 2 của phân hoạch Định nghĩa 1.11. Cho một tập hữu hạn S 6= ∅. Một phân hoạch của S thành k phần, với 1 6 k 6 n, là một họ các tập con S1 , . . . , Sk thỏa mãn ba điều kiện sau đây :  k S     i=1 Si = S Si 6= ∅ với mọi i     Si ∩ Sj = ∅ với mọi i 6= j. Ví dụ 1.3. Với tập X = {1, 2, 3, 4} ta có 7 phân hoạch 2 phần {1}, {2, 3, 4} {2}, {1, 3, 4} {3}, {1, 2, 4} {4}, {1, 2, 3} {1, 2}, {3, 4} {1, 3}, {2, 4} {1, 4}, {2, 3} và có 6 phân hoạch 3 phần {1, 2}, {3}, {4} {1, 3}, {2}, {4} {1, 4}, {2}, {3} {2, 3}, {1}, {4} {2, 4}, {1}, {3} {3, 4}, {1}, {2}. Định nghĩa 1.12. Cho tập hữu hạn S 6= ∅. Số các phân hoạch của tập S thành k phần được ký hiệu là S(n, k) và được gọi là số Stirling loại 2. n P Định nghĩa 1.13. Số Bell Bn được xác định Bn = S(n, k) với n > 1 k=1 và B0 = 1. Ví dụ 1.4. Xác định số nguyên dương k để sao cho tập hợp X = {2012, 2012 + 1, 2012 + 2, . . . , 2012 + k} có thể phân ra làm hai tập A và B thỏa mãn A ∩ B = ∅, A ∪ B = X và tổng của các số thuộc tập A bằng tổng của các số thuộc tập B. Bài giải: Trước tiên ta tìm điều kiện cho k. Giả sử có hai tập A và B thỏa mãn đầu bài. Đặt s là tổng của tất cả các số thuộc tập A. Khi đó 10 tập B cũng có tổng các số bằng s và tập X có tổng của tất cả các số bằng 2s. Vậy 4s = 2[2012+(2012+1)+(2012+2)+· · ·+(2012+k)] = 4024(k+1)+k(k+1). Như vậy, k(k + 1) chia hết cho 4 và từ đây suy ra k ≡ 3 (mod 4) hoặc k ≡ 0 (mod 4). • Trường hợp 1: k ≡ 3 (mod 4). Dễ dàng suy ra được số phần tử thuộc tập X phải là bội của 4. Hiển nhiên, 4 số tự nhiên liên tiếp n, n + 1, n + 2, n + 3 luôn thỏa mãn n + n + 3 = n + 1 + n + 2 và {n, n + 3} ∩ {n + 1, n + 2} = ∅. Tập X thỏa mãn tính chất đòi hỏi. • Trường hợp 2: k ≡ 0 (mod 4). Trong trường hợp này, số phần tử của tập X phải là số lẻ. Giả sử X được phân ra làm hai tập rời nhau A và B và A ∩ B = ∅. Ta có thể giả thiết Card(A) >Card(B). Đặt k = 4m với số tự nhiên m. Khi đó Card(A) > 2m + 1, Card(B) 6 2m. Ta có s > 2012 + (2012 + 1) + · · · + (2012 + 2m) và s < (2012 + 2m + 1) + · · · + (2012 + 4m). Như vây, ta có được 2012+(2012+1)+· · ·+(2012+2m) 6 s < (2012+2m+1)+· · ·+(2012+4m) hay 2012 < 2m.2m hay m > 23 và k = 4m > 23.4 = 92. Khi k = 92 : Ta xét A1 = {2012, 2012 + 1, . . . , 2012 + 46} với tổng các số a1 = 2012 + (2012 + 1) + · · · + (2012 + 46); và B1 = {(2012 + 47) + · · · + (2012+92)} với tổng các số b1 = (2012+47)+· · ·+(2012+92). Ta có ngay b1 − a1 = 46.46 − 2012 = 104. Thế số 2012 + 52 trong B1 bởi số 2012 và thế số 2012 của A1 bởi số 2012+52. Khi đó A = A1 \{2012}∪{2012+52} và B = B1 \ {2012 + 52} ∪ {2012} thỏa mãn đầu bài. Khi k ≡ 0 (mod 4) và k > 92 : Ta viết X = {2012, 2012 + 1, . . . , 2012 + 92} ∪ {2012 + 93, . . . , 2012 + 4m}. Phân tập X1 = {2012, 2012+1, . . . , 2012+92} thành hai tập A và B như trên; phân tập X2 = {2012 + 93, . . . , 2012 + 4m} với số phần tử chẵn dễ dàng phân ra làm hai tập C và D thõa mãn C ∩D = ∅ và C ∪D = X2 với tổng các số trong tập C và D bằng nhau. Vậy A0 = A ∪ C, B0 = B ∪ D thỏa mãn đầu bài. Tóm lại, hoặc k ≡ 3 (mod 4) hoặc k ≡ 0 (mod 4) với k > 92. 11 Ví dụ 1.5. Giả sử X là một tập gồm n phần tử. Xác định số các cặp (A, B), ở đó A, B ⊆ X, thỏa mãn A không là tập con thực sự của B. Bài giải: Ta biết rằng số tập con của tập X đúng bằng 2n . Vậy số các cặp (A, A) bằng 2n . Với mỗi số tự nhiên k và tập con B gồm k phần tử, số các tập con A của B đúng bằng 2k . Từ đây suy ra số các cặp (A, B), ở đó A, B ⊆ X, thỏa mãn A là tập con thực sự của B n
P n k n n n đúng bằng k 2 − 2 = 3 − 2 . Do vậy, số các cặp (A, B), ở đó k=0 A, B ⊆ X, thỏa mãn A không là tập con thực sự của B đúng bằng 2n .2n − [3n − 2n ] = 4n − 3n + 2n . Những kết quả sau đây cho thấy số Stirling loại 2 có liên quan trực tiếp đến số các toàn ánh giữa hai tập hữu hạn hoặc số lũy thừa. Ký hiệu Fn,k là tập tất cả các ánh xạ từ tập D = {1, 2, . . . , n} vào tập R = {1, 2, . . . , k}. Định lý 1.5. Số các toàn ánh trong tập Fn,k đúng bằng k!S(n, k). Chứng minh: Dễ thấy, mỗi toàn ánh f ∈ Fn,k tương ứng một phân hoạch duy nhất D = {1, 2, . . . , n} = f −1 (1) ∪ f −1 (2) ∪ . . . ∪ f −1 (k). Ngược lại, mỗi phân hoạch D = {1, 2, . . . , n} = A1 ∪ A2 ∪ . . . ∪ Ak tương ứng đúng k! toàn ánh: (1) Tập A1 không nhất thiết phải bằng f −1 (1). Khi đó có i1 ∈ R để tập A1 = f −1 (i1 ). Có đúng k cách chọn số nguyên i1 để A1 = f −1 (i1 ). (2) Tương tự, có đúng k − 1 cách chọn số nguyên i2 ∈ R \ {i1 } để A2 = f −1 (i2 ). ... (k) Có duy nhất 1 cách chọn số nguyên ik để Ak = f −1 (ik ). Như vậy, có tương ứng một-một giữa mỗi phân hoạch tập D thành k phần với k! toàn ánh. Vậy số các toàn ánh trong tập Fn,k bằng k!S(n, k).
Ví dụ 1.6. Số các ánh xạ tăng trong tập Fn,k đúng bằng nk khi n 6 k
và số các ánh xạ không giảm trong tập Fn,k đúng bằng k+n−1 . n 12 Định lý 1.6. Với hai số nguyên dương n, k thỏa mãn 1 6 k 6 n có ! k X k n k!S(n, k) = (−1)k−i i . i i=0 Chứng minh: Xét tập S = {a1 , a2 , . . . , an } và R = {1, 2, . . . , k}. Theo Định lý 1.5, số các toàn ánh từ S lên R bằng k!S(n, k). Mặt ! khác, biểu a1 a2 . . . an ta có ngay diễn ánh xạ f : S → R qua f (a1 ) f (a2 ) . . . f (an ) {f (a1 ), f (a2 ), . . . , f (an )} = {1, 2, . . . , k}. Viết dãy số f (a1 ), . . . , f (an ) như một chỉnh hợp lặp chập n của k số. Như vậy, tương ứng mỗi ánh xạ f với đúng một chỉnh hợp lặp chập n của k số. Số chỉnh hợp lặp này đúng bằng k n . Ký hiệu A là tập tất cả các ánh xạ từ S vào R và cho mỗi i ký hiệu Ai là tập con của A gồm tất cả các ánh xạ từ S vào R \ {i}. s T Ta có |A| = k n , |Ai | = (k − 1)n và Aij = (k − s)n . Tập tất cả các toàn j=1 k S ánh từ S lên R đúng bằng A \ Ai . Theo Nguyên lý Bù-Trừ ta nhận i=1 được ! k k!S(n, k) = |A| − | Ai | = k n − (k − 1)n 1 ! i=1 ! k k + (k − 2)n − · · · + (−1)k (k − k)n . 2 k k [ Vậy k!S(n, k) = k P (−1)i ki i=0
n (k − i) = k P (−1)k−i i=0 k i
n i . Hệ quả 1.3. Với số nguyên dương n, k thỏa mãn 1 6 k 6 n có ! k X k kn = i!S(n, i). i i=0 Chứng minh: Đặt ak = k!S(n, k) và bi = in . Theo Định lý 1.6 ta có k k

P P k−i k k i k ak = (−1) b . Đặt c = (−1) a . Khi đó c = (−1) i k k k i i bi . Ký i=0 i=0 hiệu đẳng thức này như sau ck = (1 − b)k và hiểu là sau khi khai triển thay bi bởi bi . Với ký hiệu hiệu hình thức, đúng với mọi giá trị của x, 13 có thể viết đồng nhất thức như sau: (c + x)k = (−b + 1 + x)k . Cho k
P x = −1 ta có (−1)k bk = (c − 1)k hay bk = (1 − c)k = (−1)i ki ci . Vậy i=0 kn = k P i=0
k i i!S(n, i). Định lý 1.7. Với hai số nguyên dương n, k thỏa mãn 1 6 k 6 n có S(n + 1, k) = S(n, k − 1) + kS(n, k). Chứng minh: Xét tập tất cả các phân hoạch tập T = {1, 2, . . . , n, n+1} thành k phần. Chia tập các phần phân hoạch đó ra làm hai phần. Phần I bao gồm tất cả các phân hoạch với một phần trong mỗi phân hoạch đó là tập {n + 1}; Phần II bao gồm tất cả các phân hoạch, trong mỗi phần phân hoạch đó không có phần là tập {n + 1}. Phần I dễ đếm được vì mỗi phân hoạch đều có một phần là tập {n+1} nên các phần còn lại là số các phân hoạch tập {1, 2, . . . , n} thành k − 1 phần. Do vậy, số phân hoạch thuộc phần I đúng bằng S(n, k − 1). Phần II: Tương ứng mỗi phân hoạch A1 ∪ A2 ∪ . . . ∪ Ak của tập {1, 2, . . . , n} với k phần khác nhau của tập T = {1, 2, . . . , n, n + 1} thuộc phần II qua việc thế Ai 7→ Ai ∪ {n + 1}, còn các Aj khác được giữ nguyên khi j 6= i với i = 1, 2, . . . , k. Ta tính được ngay số phân hoạch thuộc phần II đúng bằng kS(n, k). Tóm lại, ta nhận được công thức S(n + 1, k) = S(n, k − 1) + kS(n, k). Chú ý 1.1. Trong [5] người ta cũng đã đưa ra những biểu diễn cho số Stirling loại 2 và số Bell như sau: n
1 P n (1) S(n, k) = . k! i1 +···+ik i1 ,i2 ,...,ik n P (2) S(n + 1, k) = j=0 (3) Bn+1 = n P j=0 n j
n j
S(j, k − 1). Bj . ∞ S(n, k) P Ví dụ 1.7. Với dãy số Stirling, hãy xác định tổng T = . n! n=0 14 Bài giải: Theo Định lý 1.6, ta nhận được chuỗi lũy thừa ! k ∞ X X k n
n 1 1 (−1)k−i i x . f (x) = n! k! i n=0 i=0 k
(ix)n P Vậy k!f (x) = = (−1)k−i ki eix = (ex − 1)k hay n! i=0 x (e − 1) (e − 1)k f (x) = . Từ đây suy ra T = f (1) = . k! k! ∞ B P n . Ví dụ 1.8. Với dãy số Bell (Bn ) hãy xác định tổng T = n=0 n! ∞
P (−1)k−i ki n=0 i=0 k k P Bài giải: Theo chú ý ở trên ta có Bn+1 ! n X n = Bk . k k=0 Đặt f (x) = ∞ B P n n x . Vậy n=0 n! ∞ ∞ X X 1 Bn+1 n n Bn+1 x = x = f 0 (x). f (x)e = (n + 1) n! (n + 1)! n=0 n=0 x R f 0 (x) R Từ đây suy ra dx = ex dx hay ln(f (x)) = ex + C. f (x) Vì f (0) = B0 = 1 nên C = −1 và như thế ln(f (x)) = ex − 1. Do đó x f (x) = ee −1 . Từ đây suy ra T = f (1) = ee−1 . 15 Chương 2 Số Stiling và số Bell của đồ thị 2.1 Số χ(G) Định nghĩa 2.1. Số màu χ(G) là số nhỏ nhất các màu đủ để tô màu thích hợp đồ thị G. 2.1.1 Bài toán tô màu cạnh đồ thị Ví dụ 2.1. Với 6 người trong cuộc họp có 3 người đã từng gặp nhau hoặc chưa bao giờ gặp nhau. Bài giải: Ký hiệu 6 người là 6 điểm A, B, C, D, E, F, trong đó không có ba điểm thẳng hàng và 6 điểm là 6 đỉnh của một lục giác lồi. Nếu hai người đã gặp nhau thì ta nối họ bằng một đoạn màu đỏ, còn họ chưa bao giờ gặp nhau ta nối họ bằng một đoạn màu đen. Từ điểm A có thể kẻ 5 đoạn: AB, AC, AD, AE, AF và được tô bởi hai màu đỏ và đen. Theo Nguyên lý Dirichlet, chẳng hạn màu đỏ được tô cho 3 đoạn. Ta có thể coi AB, AC, AD được tô màu đỏ. Xét tam giác BCD. Nếu cạnh tam giác BCD đều cùng màu đen thì B, C, D là 3 người chưa bao giờ gặp nhau. Nếu 3 cạnh tam giác BCD không cùng màu đen, chẳng hạn CD có màu đỏ. Khi đó tam giác ACD có ba cạnh màu đỏ hay A, C, D đã từng gặp nhau. Bài toán đã được giải xong. Ví dụ 2.2. Trong cuộc họp 17 người bàn luận về 3 vấn đề và mỗi người đều có thể bàn luận với nhau về một trong ba vấn đề đó. Khi đó có ít nhất ba người cùng chọn một vấn đề trao đổi với nhau. 16 Bài giải: Ký hiệu 17 người là 17 điểm A1 , A2 , . . . , A17 , trong đó không có ba điểm thẳng hàng và 17 điểm là 17 đỉnh của một đa giác lồi. Nếu hai người thảo luận vấn đề I, II, III được nối với nhau bởi đoạn màu đỏ, màu xanh, màu đen, tương ứng. Điểm A1 được nối với 16 đỉnh khác được 16 đoạn. Sử dụng 3 màu để tô 16 = 5.3 + 1 đoạn nên phải có 6 đoạn tô cùng một màu theo Nguyên lý Dirichlet, chẳng hạn màu đỏ được tô cho 6 đoạn.Ta có thể coi A1 A2 , A1 A3 , A1 A4 , A1 A5 , A1 A6 , A1 A7 . được tô màu đỏ. Xét lục giác T : A2 A3 A4 A5 A6 A7 . Nếu một cạnh nào đó của lục giác T được tô màu đỏ thì ta nhận được tam giác ba cạnh đỏ. Nếu không có cạnh nào của T mang màu đỏ thì 6 cạnh của T được tô bởi 2 màu xanh, đen. Theo ví dụ trên có tam giác với ba cạnh cùng màu. Khi đó có 3 người cùng thảo luận một vấn đề. Tất nhiên xuất hiện câu hỏi vê bài toán tương tự cho n người. Xét một tập hữu hạn V gồm n phần tử. Ký hiệu V (2) là tập tất cả các tập con gồm 2 phần tử phân biệt thuộc V : V (2) = {{u, v}|u, v ∈ V, u 6= v}.
n2 − n Hiển nhiên |V | = = n2 . Ta quan tâm đến đồ thị Kn = 2 (V, V (2) ). Trong ví dụ thứ nhất ta xét K6 , còn trong ví dụ thứ hai ta xét K17 . Sử dụng mầu đỏ để đưa ra một hình và chọn ra tập con của E ⊂ V (2) và từ đó làm nẩy sinh các cạnh thuộc V (2) không thuộc E. Với việc sử dụng mầu đỏ, đen hoặc mầu đỏ, xanh, đen để tô màu cạnh đồ thị Kn ta nhận được một hình tương ứng đồ thị G = (V, E). Như vậy, n chúng ta đã xem một hình theo hai cách tương ứng 1-1 giữa 2( 2 ) tô màu n đỏ, đen các cạnh khác nhau của Kn và 2( 2 ) đồ thị khác nhau với tập n đỉnh. Để có thể rút ra kết quả mong muốn từ việc tô màu cạnh ta xét định nghĩa sau đây. (2) Định nghĩa 2.2. Xét đồ thị G = (V, E). Đồ thị Gc = (V, V (2) \ E) được gọi là phần bổ sung của G. Định nghĩa 2.3. Xét đồ thị G = (V, E) và đồ thị con H = (W, F ), trong đó W ⊂ V, F ⊂ E. Nếu F = E ∩ W (2) thì H được gọi là đồ thị con cảm sinh của G bởi W và viết H = G[W ]. 17 Xét đồ thị G = (V, E). Một bụi là một tập con không rỗng các đỉnh liền kề. Tập con W của V là một bụi khi và chỉ khi W (2) ⊂ E tương đương G[W ] = (W, W (2) ) là một đồ thị con đầy đủ. Một tập con các đỉnh không liền kề được gọi là một tập độc lập. Như vậy, một tập con không rỗng W ⊂ V là một tập độc lập khi và chỉ khi không có hai đỉnh nào của nó là liền kề một cạnh của G, tương đương G[W ] = (W, ∅) hay W là một bụi của Gc . Định nghĩa 2.4. Với hai số nguyên dương s, t ta ký hiệu N (s, t) là số nguyên dương nhỏ nhất n để mỗi đồ thị gồm n = N (s, t) đỉnh hoặc chứa Ks hoặc chứa Ktc như một đồ thị con cảm sinh. Ta công nhận hai kết quả dưới đây: Bổ đề 2.1. [[3], Theorem 5.2.3] Với hai số nguyên s, t > 2, mỗi đồ thị gồm N (s, t − 1) + N (s − 1, t) đỉnh đều chứa đồ thị con cảm sinh hoặc đẳng cấu Ks hoặc đẳng cấu Ktc , có nghĩa N (s, t) tồn tại và N (s, t) 6 N (s, t − 1) + N (s − 1, t). Định lý 2.1. [[3], Theorem 5.2.5] Với cặp số nguyên s, t > 0 ta có các bất đẳng thức ! s+t−2 (s − 1)(t − 1) + 1 6 N (s, t) 6 . s−1 Với kết quả này ta có N (1, t) = 1, N (2, t) = t với mọi t > 1 và 5 6 N (3, 3) 6 6. Do hình năm cạnh lồi không chứa K3 cũng không chứa K3c như một đồ thị cảm sinh nên N (3, 3) > 6 và ta có N (3, 3) = 6. 2.1.2 Đa thức màu (chromatic polynomials) Ở phần trên chúng ta đã xét việc tô màu cạnh đồ thị Kn . Phần này chúng ta xét bài toán liên quan đến việc tô màu đỉnh không chỉ đồ thị Kn mà cả những đồ thị tùy ý. Một r-tô màu của G là một hàm từ V = V (G) vào một tập gồm r màu nào đó. Định nghĩa 2.5. Một tô màu của đồ thị G, trong đó hai đỉnh liền kề được tô màu khác nhau, được gọi là một tô màu riêng. Số những cách r-tô màu riêng cho đồ thị G được ký hiệu qua p(G, r). 18