Tài liệu Tập hợp và cực trị tập hợp

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC CHU THỊ HẢI YẾN TẬP HỢP VÀ CỰC TRỊ TẬP HỢP LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2018 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC CHU THỊ HẢI YẾN TẬP HỢP VÀ CỰC TRỊ TẬP HỢP LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8460113 NGƯỜI HƯỚNG DẪN KHOA HỌC TS. TRẦN NGUYÊN AN Thái Nguyên - 2018 3 Mục lục Mở đầu 5 Chương 1. Tập hợp, ánh xạ và tổ hợp 7 1.1 Tập hợp, ánh xạ . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Chương 2. Cực trị tập hợp 24 2.1 Một số định lý trong lý thuyết cực trị tập hợp . . . . . . . . . 24 2.2 Một số dạng toán cực trị tập hợp . . . . . . . . . . . . . . . . 28 2.2.1 Sử dụng ánh xạ . . . . . . . . . . . . . . . . . . . . . . 28 2.2.2 Sử dụng nguyên lý tổ hợp . . . . . . . . . . . . . . . . 30 2.2.3 Đếm hai cách . . . . . . . . . . . . . . . . . . . . . . . 32 2.2.4 Quy nạp - Truy hồi . . . . . . . . . . . . . . . . . . . . 35 2.2.5 Phương pháp ma trận liên thuộc . . . . . . . . . . . . 37 2.2.6 Khoảng cách Hamming - chặn Plotkin . . . . . . . . . 40 Kết luận 45 Tài liệu tham khảo 46 4 Lời cảm ơn Trong quá trình làm luận văn, tôi nhận được sự hướng dẫn và giúp đỡ tận tình của TS. Trần Nguyên An - Trường Đại học Sư phạm - Đại học Thái Nguyên. Tôi xin được bày tỏ lòng biết ơn sâu sắc đến thầy. Tôi xin gửi lời cảm ơn chân thành đến quý thầy cô giảng dạy lớp Cao học khóa Cao học Toán khóa 10Q (2016-2018) - Trường Đại học Khoa học - Đại học Thái Nguyên, đã truyền thụ đến cho tôi nhiều kiến thức và kinh nghiệm nghiên cứu khoa học. Xin trân trọng cảm ơn Sở Giáo dục và Đào tạo Hải Phòng, Ban Giám hiệu và các đồng nghiệp ở Trường THPT Phạm Ngũ Lão, Thủy Nguyên, Hải Phòng, đã tạo mọi điều kiện thuận lợi để tác giả học tập và nghiên cứu. Lời cuối cùng, tác giả muốn dành để tri ân bố mẹ và gia đình vì đã chia sẻ những khó khăn để tác giả hoàn thành công việc học tập của mình. 5 Mở đầu Khái niệm tập hợp là nền tảng để xây dựng các khái niệm khác như số, hình, hàm số,. . . trong Toán học. Nghiên cứu lý thuyết tập hợp hiện đại do Cantor và Dedekind khởi xướng vào thập niên 1870. Mục đích đầu tiên của luận văn là nhắc lại một số kiến thức cơ bản về bản số của tập hợp. Từ đó giải thích chi tiết các nguyên lý đếm, và các khái niệm cơ bản của tổ hợp. Nội dung này được kết thúc bằng bài toán đếm số ánh xạ, đơn ánh, toàn ánh, song ánh giữa các tập hữu hạn. Mục đích tiếp theo của luận văn là tìm hiểu lý thuyết cực trị tập hợp. Những bài toán trong lý thuyết cực trị tập hợp thường có dạng: cho một tập (hay một họ các tập) F thỏa mãn một số điều kiện cho trước, tìm max hoặc min của lực lượng của F. Khi nào dấu đẳng thức xảy ra ? Luận văn quan tâm đến một số bài toán. Cho F là một họ các tập con của một tập có n phần tử X. Để đơn giản ta thường xét X là tập [n] = {1, 2, 3, ..., n}. Bài toán 1. Giả sử bất kỳ hai phần tử nào của F cũng có giao khác rỗng. Hỏi giá trị lớn nhất có thể của |F|? Bài toán 2. Giả sử A * B với mọi phần tử A, B của F. Hỏi giá trị lớn nhất có thể của |F|? Các bài toán có thêm các điều kiện của F và các bài toán về cực trị tập hợp liên quan ở phổ thông cũng được tìm hiểu trong luận văn. Ngoài các phần Mở đầu, Kết luận, Tài liệu tham khảo, nội dung của luận văn được trình bày trong hai chương. 6 • Chương 1. Tập hợp, ánh xạ và tổ hợp. Trong chương này chúng tôi sẽ trình bày về lực lượng của tập hợp, các quy tắc đếm, các quy tắc tổ hợp và giải quyết bài toán đếm ánh xạ giữa các tập hữu hạn. Nguyên lý Dirichlet và một số mở rộng cũng được trình bày trong chương này. • Chương 2. Cực trị tập hợp. Chương này trình bày các Định lý Erdös - Ko - Rado, Định lý Sperner, Bất đẳng thức Lubell - Yamamoto Meshalkin. Cuối cùng luận văn trình bày một số dạng toán cực trị tập hợp ở phổ thông. Thái Nguyên, ngày 05 tháng 5 năm 2018 Tác giả Chu Thị Hải Yến 7 Chương 1 Tập hợp, ánh xạ và tổ hợp 1.1 Tập hợp, ánh xạ Tập hợp là một khái niệm nguyên thuỷ (cơ bản) của toán học, không định nghĩa. Ta hiểu tập hợp là những vật, những đối tượng của toán học,. . . , được gom lại do một tính chất chung nào đó. Chẳng hạn, người ta nói "Tập hợp các sinh viên trong một lớp", "tập hợp các lớp học trong một trường học", "tập hợp N các số tự nhiên", "tập hợp Z các số nguyên", "tập hợp Q các số hữu tỉ", "tập hợp R các số thực",. . . Các tập hợp thường được ký hiệu bởi các chữ in hoa: X, Y, Z, . . .. Các vật trong tập hợp gọi là các phần tử của tập hợp ấy và thường được ký hiệu bởi các chữ in thường: x, y, z, . . . , a, b, c, . . .. Tập hợp, phép toán trên tập hợp và một số tính chất là những kiến thức quen thuộc nên ta không nhắc lại ở đây. Để hiểu đầy đủ hơn về lý thuyết tổ hợp, ta nhắc lại khái niệm ánh xạ, đây cũng là kiến thức chuẩn bị cho chương sau. Định nghĩa 1.1.1. (i) Một ánh xạ f từ tập X đến tập Y là một quy tắc cho tương ứng mỗi phần tử x ∈ X với một phần tử duy nhất y ∈ Y. Khi đó ta viết f (x) = y, ta gọi y gọi là ảnh của phần tử x bởi ánh xạ f ; và ta gọi x là một tạo ảnh của phần tử y. Tập X được gọi là tập nguồn, tập Y gọi là tập đích của ánh xạ f . Để diễn tả ánh xạ f như trên người ta kí hiệu: f X→ − Y, x 7→ f (x) = y, hoặc f : X → Y, x 7→ f (x) = y, hoặc 8 f :X→Y x 7−→ f (x) = y. (ii) Ta quy ước rằng có một ánh xạ rỗng từ tập ∅ đến tập Y bất kì. (iii) Cho ánh xạ f : X → Y, x 7→ f (x). Ta gọi tập hợp con G(f ) của X × Y xác định bởi G(f ) = {(x, f (x)) | x ∈ X} là đồ thị của ánh xạ f . (iv) Hai ánh xạ được gọi là bằng nhau nếu chúng có chung nguồn, chung đích và chung đồ thị. Nói cách khác, cho f : X → Y và g : X 0 → Y 0 là hai ánh xạ, khi đó f = g nếu X = X 0 , Y = Y 0 và f (x) = g(x) với mọi x ∈ X. Định nghĩa 1.1.2. Cho f : X −→ Y, x 7→ y = f (x) là một ánh xạ. (i) f được gọi là đơn ánh nếu f (x) = f (x0 ) kéo theo x = x0 với mọi x, x0 ∈ X. (ii) f được gọi là toàn ánh nếu với mọi y ∈ Y kéo theo tồn tại x ∈ X để f (x) = y. (iii) f được gọi là song ánh nếu nó vừa là đơn ánh vừa là toàn ánh. Chú ý 1.1.3. Cho X, Y là những tập hợp, ta nói X ∼ Y khi và chỉ khi có một song ánh từ X đến Y . Khi đó (i) X ∼ X với mọi tập X; (ii) Nếu X ∼ Y thì Y ∼ X với mọi tập X, Y ; (iii) Nếu X ∼ Y , Y ∼ Z thì X ∼ Z với mọi tập X, Y, Z; (iv) Nếu X ∼ X1 và Y ∼ Y1 thì X × Y ∼ X1 × Y1 ; (v) Nếu X ∼ X1 và Y ∼ Y1 và X ∩ Y = X1 ∩ Y1 = ∅ thì X ∪ Y ∼ X1 ∪ Y1 . Định lý sau do Cantor nêu lên khi nghiên cứu lý thuyết tập hợp, nhưng Cantor không chứng minh được. Phần thứ hai của định lý được Bernstein 9 chứng minh năm 1897 nên được gọi là Định lý Cantor-Bernstein. Phần thứ nhất của định lý được Zermelo chứng minh năm 1904 sau khi đưa tiên đề chọn vào lý thuyết tập hợp. Định lý 1.1.4 (Định lý Cantor-Bernstein). Cho X, Y là những tập hợp, thế thì phải xảy ra ít nhất một trong hai trường hợp sau đây: (i) X tương đương với một bộ phận của Y ; (ii) Y tương đương với một bộ phận của X. Nếu có (i) và (ii) thì X và Y tương đương với nhau. Định nghĩa 1.1.5. Khi các tập hợp X và Y tương đương với nhau, thì ta nói rằng chúng có cùng một lực lượng hay cùng một bản số. Bản số của X ký hiệu |X| hoặc Card(X). Định nghĩa 1.1.6. Một tập hợp không tương đương với bất kỳ một bộ phận thực sự nào của nó được gọi là một tập hợp hữu hạn. Một tập hợp không phải là hữu hạn được gọi là tập vô hạn. Bản số của một tập hợp hữu hạn được gọi là một số tự nhiên. Tập các số tự nhiên được ký hiệu là N. Chú ý, hợp, tích đề các của hai tập hữu hạn là một tập hữu hạn. Từ đó ta định nghĩa được phép cộng và nhân trên N. Cho a, b là các số tự nhiên, gọi X, Y là các tập hợp mà a = |X|, b = |Y | và X ∩Y = ∅. Khi đó a+b = |X ∪Y |, ab = |X ×Y |. Cũng từ đây ta có kết quả sau là điểm khởi đầu của các nguyên lý đếm trong tổ hợp. Cho X, Y là các tập hợp hữu hạn, X ∩ Y = ∅. Khi đó |X ∪ Y | = |X| + |Y |. 1.2 Tổ hợp Người ta thương phân biệt nhiều mức độ trong việc giải các bài toán tổ hợp. Mức độ đầu tiên là tìm ít nhất một cách bố trí các đối tượng có tính chất 10 đã cho (chẳng hạn bố trí mười điểm nằm trên đoạn thẳng sao cho trên đoạn nào cũng có bốn điểm, như trên hình vẽ). Nếu bài toán tổ hợp có nhiều lời giải thì vẫn đề đặt ra là đếm số lời giải, và mô tả tất cả các lời giải của các bài toán đã cho. Cuối cùng, nếu các lời giải khác nhau được phân biệt với nhau bởi những tham số nào đó, thì vấn đề đặt ra là tìm lời giải tối ưu của bài toán đã cho. Ở đây chúng ta sẽ chỉ giới hạn vào việc đếm số lời giải cuả bài toán tổ hợp. Để làm việc này, người ta thường áp dụng những công thức thiết lập cho từng loại bài toán. Tất cả các công thức ấy, xét cho cùng, đều dựa trên hai quy tắc đơn giản là quy tắc cộng và quy tắc nhân. Định nghĩa 1.2.1 (Quy tắc cộng). Nếu một công việc nào đó có thể thực hiện theo n phương án khác nhau, trong đó: phương án 1 có m1 cách thực hiện, phương án 2 có m2 cách thực hiện, ..., phương án thứ n có mn cách thực hiện. Khi đó, có: m1 + m2 + ... + mn cách để hoàn thành công việc đã cho. Ta phát biểu quy tắc cộng theo ngôn ngữ tập hợp: Gọi A1 là tập hợp các đối tượng x1 , A2 là tập hợp các đối tượng x2 , ..., An là tập hợp các đối tượng xn . Mỗi cách chọn đối tượng xi ứng với một phần tử của Ai và đảo lại. Điều kiện "cách chọn đối tượng xi không trùng với bất kỳ đối tượng xj , (j 6= i)" được diễn tả theo ngôn ngữ tập hợp bằng điều kiện: Ai ∩ Aj = ∅, (i 6= j); 11 i, j = 1, 2, ..., n. Cách chọn "x1 hoặc x2 ... hoặc xn " được phiên dịch thành cách chọn một phần tử của tập hợp A1 ∪ A2 ∪ ... ∪ An . Các số m1 , m2 , ..., mn theo thứ tự là số phần tử của tập hợp A1 , A2 , ..., An , tức là, theo cách ký hiệu quen thuộc m1 = |A1 |, m2 = |A2 |, ..., mn = |An |. Mệnh đề 1.2.2. Nếu A1 , ..., Am là các tập hợp hữu hạn đôi một rời nhau, khi đó: |A1 ∪ ... ∪ Am | = |A1 | + ... + |Am−1 | + |Am |. Chứng minh. Ta chứng minh quy nạp theo m. Với m = 1 hiển nhiên đúng. Với m = 2, vì A1 ∩ A2 = ∅ nên theo định nghĩa của phép cộng các số tự nhiên, ta có |A1 ∪ A2 | = |A1 | + |A2 |. Với m > 2, giả sử kết quả đã đúng với m − 1 tập hợp. Đặt A = A1 ∪ ... ∪ Am−1 và B = Am Theo giả thiết quy nạp, |A| = |A1 | + ... + |Am−1 |. Vì Am không giao với bất kì tập Aj nào với j < m, ta có A và B rời nhau, khi đó: |A1 ∪ ... ∪ Am | = |A ∪ B| = |A| + |B| = |A1 | + ... + |Am−1 | + |Am |. Quy tắc cộng có thể mở rộng cho công thức |A1 ∪ A2 ∪ ... ∪ An |, trong đó A1 ,..., An là các tập hợp hữu hạn tùy ý (không nhất thiết đôi một rời nhau). Công thức này được gọi là Nguyên lý bao hàm và loại trừ. Định lý 1.2.3 (Nguyên lý bao hàm và loại trừ). Giả sử A1 , A2 , ...An . Là các tập hữu hạn bất kỳ. Khi đó: |A1 ∪ A2 ∪ ... ∪ An | = X 16i1 6n |Ai1 | − X 16i1 6i2 6n |Ai1 ∩ Ai2 | + ... 12 + (−1)k+1 X |Ai1 ∩ Ai2 ∩ ... ∩ Aik | + ... 16i1 6i2 6...ik 6n + (−1)n+1 |Ai1 ∩ Ai2 ∩ ... ∩ Ain |. Chứng minh. Ta chứng minh công thức trên bằng quy nạp theo n. Với n = 1, công thức trên hiển nhiên đúng. ta chứng minh rằng nó cũng đúng cho n = 2. Ta có: A1 = (A1 ∩ A2 ) ∪ (A1 \ (A1 ∩ A2 )), A2 = (A1 ∩ A2 ) ∪ (A2 \ (A1 ∩ A2 )), A1 ∪ A2 = (A1 ∩ A2 ) ∪ (A1 \ (A1 ∩ A2 )) ∪ (A1 ∩ A2 ) ∪ (A2 \ (A1 ∩ A2 )). Hợp của các vế phải là hợp của các tập đôi một rời nhau. Vì vậy theo quy tắc cộng, |A1 | = |A1 ∩ A2 | + |A1 \ (A1 ∩ A2 )|, |A2 | = |A1 ∩ A2 | + |A2 \ (A1 ∩ A2 )|, |A1 ∪ A2 | = |A1 ∩ A2 | + |A1 \ (A1 ∩ A2 )| + |A2 \ (A1 ∩ A2 )|. Từ ba đẳng thức này ta nhận được |A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 |. Vậy công thức trên đúng cho trường hợp n = 2. Giả sử công thức đã được chứng minh cho n = m và A1 , A2 , ..., Am , Am+1 là m + 1 tập hữu hạn bất kỳ đã cho. Vì công thức đã được chứng minh cho n = 2 nên |A1 ∪ A2 ∪ ... ∪ Am ∪ Am+1 | = |(A1 ∪ A2 ∪ ... ∪ Am ) ∪ Am+1 | = |A1 ∪ A2 ∪ ... ∪ Am | + |Am+1 | − |(A1 ∪ A2 ∪ ... ∪ Am ) ∩ Am+1 | X X = |Ai1 | − |Ai1 ∩ Ai2 | + ... 16i1 6m + (−1)k+1 16i1 6i2 6m X |Ai1 ∩ Ai2 ∩ ... ∩ Aik | + ... 16i1 6i2 6...ik 6m + (−1)m+1 |Ai1 ∩ Ai2 ∩ ... ∩ Aim | + |Am+1 | − |(A1 ∪ A2 ∪ ... ∪ Am ) ∩ Am+1 |. 13 Từ hai đẳng thức trên suy ra công thức trong Định lý 1.2.3 cũng đúng cho n = m + 1. Trước khi đề cập ví dụ, ta nhắc lại một số kết quả về hàm sàn. Định nghĩa 1.2.4. Cho một số thực x ∈ R. (i) Số nguyên lớn nhất không vượt quá x được gọi là phần nguyên (integer part, integral part) hay sàn (floor) của x .Ta thường kí hiệu phần nguyên của x là [x]. Nhiều tài liệu gọi phần nguyên của x là sàn và kí hiệu phần nguyên của x là bxc. (ii) Cho một số thực x ∈ R. Số nguyên bé nhất không nhỏ hơn x được gọi là trần của x và được kí hiệu là dxe. Từ định nghĩa, ta có tính chất sau:   z 6 x < z + 1 [x] = z ⇔  z ∈ Z và dxe = z ⇔   z − 1 < x 6 z ⇔   0 6 x − z < 1  z ∈ Z ⇔  z ∈ Z   0 6 z − x < 1  z ∈ Z. Hơn nữa, dxe = bxc nếu x ∈ Z và dxe = bxc + 1 với mọi x ∈ / Z. Mệnh đề 1.2.5. Với mọi x ∈ R ta có (i) [x] 6 x < [x] + 1 hay x − 1 < [x] 6 x. (ii) dxe − 1 < x 6 dxe hay x 6 dxe < x + 1. Dấu bằng xảy ra khi và chỉ khi x là số nguyên. Ví dụ 1.2.6. Có bao nhiêu số nguyên dương từ 1 đến 1000 mà không chia hết cho 2, không chia hết cho 3 và cũng không chia hết cho 7? Giải. Kí hiệu A = {1, 2, 3, ..., 1000}, A2 = {a ∈ A | a chia hết cho 2}, A3 = {a ∈ A|a chia hết cho 3}, A7 = {a ∈ A|a chia hết cho 7}. Khi đó A \ (A2 ∪ 14 A3 ∪ A7 ) là tập tất cả các số từ 1 đến 1000 mà không chia hết cho 2, không chia hết cho 3, không chia hết cho 7. Theo nguyên lý bao hàm và loại trừ, ta có: |A2 ∪ A3 ∪ A7 | = |A2 | + |A3 | + |A7 | − |A2 ∩ A3 | − |A3 ∩ A7 |− |A2 ∩ A7 | + |A2 ∩ A3 ∩ A7 |. thì 1000 c = b500c = 500, 2 1000 |A3 | = b c = b333, 3...c = 333, 3 1000 c = b142, 8...c = 142, |A7 | = b 7 1000 1000 |A2 ∩ A3 | = b c=b c = 166, 6... = 166, (2 × 3) 6 1000 1000 c=b c = 71, 4... = 71, |A2 ∩ A7 | = b (2 × 7) 14 1000 1000 |A3 ∩ A7 | = b c=b c = 47, 6... = 47, (3 × 7) 21 1000 1000 c=b c = 23, 8... = 23. |A2 ∩ A3 ∩ A7 | = b (2 × 3 × 7) 42 |A2 | = b Do đó, |A2 ∪ A3 ∪ A7 | = 500 + 333 + 142 − 166 − 71 − 47 + 23 = 714. Vì (A2 ∪ A3 ∪ A7 ) ⊆ A, nên |A \ (A2 ∪ A3 ∪ A7 )| = |A| − |A2 ∪ A3 ∪ A7 | = 1000 − 714 = 286. Định nghĩa 1.2.7 (Quy tắc nhân). Nếu một công việc nào đó phải hoàn thành qua m giai đoạn liên tiếp, trong đó: giai đoạn 1 có m1 cách thực hiện, giai đoạn 2 có m2 cách thực hiện, ..., giai đoạn n có mn cách thực hiện. Khi đó, có: m1 .m2 ...mn cách để hoàn thành công việc đã cho. 15 Mệnh đề 1.2.8. Cho s tập hợp hữu hạn A1 , A2 , ..., An (n > 2). Khi đó |A1 × A2 × ... × An | = |A1 |.|A2 |...|An |. Chứng minh. a) Trường hợp hai tập hợp. Cho hai tập hợp hữu hạn A và B. Ta cần chứng minh rằng |A × B| = |A| · |B| (1.1) Thật vậy, giả sử |A| = m, |A| = k và A = {a1 , a2 , . . . am }, B = {b1 , b2 , . . . bk }. Tích Đề các A × B, gồm các cặp (ai , bj ), 1 6 i 6 m, 1 6 j 6 k, có thể viết thành một bảng hình chữ nhật m dòng n cột như sau: (a1 , b1 ), (a1 , b2 ), . . . , (a1 , bk ) (a2 , b1 ), (a2 , b2 ), . . . , (a2 , bk ) ................................................. (am , b1 ), (am , b2 ), . . . , (am , bk ). Đặt Ai = {(ai , b1 ), (ai , b2 ), . . . , (ai , bk )} 1 6 i 6 m. Rõ ràng ta có |Ai | = k, (1 6 i 6 m). Ai ∩ Aj = ∅ nếu i 6= j, và A × B = A1 ∪ A2 ∪ . . . ∪ Am . Theo quy tắc cộng, ta có |A × B| = |A1 | + |A2 | + . . . + |Am | = m.k = |A|.|B|. Vậy |A × B| = |A|.|B|. Giả sử mệnh đề đúng với n = k, (k > 2) ta sẽ chứng minh mệnh đề đúng khi n = k + 1, tức là |A1 × A2 × ... × Ak × Ak+1 | = |A1 |.|A2 |...|Ak |.|Ak+1 |. Thật vậy, xét một phần tử bất kỳ (a1 , a2 , ..., ak , ak+1 ) của tích Đề các A1 × A2 × ... × Ak × Ak+1 . Đặt α = (a1 , a2 , ..., ak ). Hiển nhiên giữa tập hợp các 16 bộ có dạng như (a1 , a2 , ..., ak , ak+1 ) và tập hợp các cặp có dạng (α, ak+1 ) có một tương ứng 1 - 1. Vậy có bao nhiêu bộ như (a1 , a2 , ..., ak , ak+1 ) thì có bấy nhiêu cặp (α, ak+1 ). Nếu ta ký hiệu tập hợp tất cả các α là A, thì ta có thể nói rằng tập hợp A1 × A2 × ... × Ak × Ak+1 có bao nhiêu phần tử thì tập hợp A × Ak+1 có bấy nhiêu phần tử, tức là |A1 × A2 × ... × As | = |A × Ak+1 |. Theo chứng minh trên, ta có |A × Ak+1 | = |A|.|Ak+1 |. Theo cách dựng thì A chính là tích Đề các |A1 × A2 × ... × Ak |. Áp dụng giả thiết quy nạp, ta có |A × Ak+1 | = |A|.|Ak+1 | = |A1 × A2 × ... × Ak |.|Ak+1 | = |A1 |.|A2 |...|Ak |.|Ak+1 |. Vậy |A1 × A2 × ... × Ak × Ak+1 | = |A1 |.|A2 |...|Ak |.|Ak+1 |. Mệnh đề được chứng minh. Sau đây ta tìm hiểu tập các tập con của một tập hợp X, ký hiêu là 2X hoặc P(X). Định lý 1.2.9. Số tất cả các tập con của tập hợp có m phần tử bằng 2m . Chứng minh. Gọi Ta là tập hợp tất cả các tập con của tâp hợp A chứa phần tử a ∈ A. Hiển nhiên mỗi tập con như thế được hoàn toàn xác định, nếu ta biết tất cả các phần tử còn lại của nó (trừ a). Vì vậy có bao nhiêu tập con như thế thì có bấy nhiêu tập con trong tập A0 = A \ {a}. Tập hợp A0 này có m − 1 phần tử. Vì vậy, nếu ta gọi sm là số tập con của một tập con của một tập hợp có m phần tử, thì |Ta | = sm−1 . Gọi T a là tập hợp tất cả các tập con của tập hơp A không chứa a, thì n(T a ) cũng bằng sm−1 , vì các tập con đó cũng là các tập con của tập hợp 17 A0 = A \ {a}. Vì T (A) = Ta ∪ T a và Ta ∩ T a = ∅, nên theo quy tắc cộng, ta có |T (A)| = |T (a)| + |T a | = 2sm−1 . Từ đó suy ra sm = 2sm−1 . Áp dụng liên tiếp đẳng thức này, ta được sm = 2sm−1 = 22 sm−2 = . . . = 2m−1 s1 . s1 là số tập con của một tập hợp có một phần tử. Nhưng một tập hợp có một phần tử chỉ có hai tập con là tập rỗng và chính nó. Vậy s1 = 2. Do đó sm = |T (A)| = 2m . Định lý 1.2.10. Số tất cả các tập con k phần tử của một tập hợp m phần tử bằng m(m − 1) . . . (m − k + 1) m! = . 1.2 . . . k k!(m − k)!
Chứng minh. Ta kí hiệu |Tk (A)| là m k Muốn dựng một tập con k phần tử |Tk (A)| = của tập hợp A ta có thể ghép thêm vào một tập con k − 1 phần tử của A một trong m − (k − 1) = m − k + 1 phần tử không tham dự vào nó.
m Vì có k−1 tập con k − 1 phần tử và ta có thể bổ sung tập con ấy thành một tập con k phần tử theo m − k + 1 cách, nên làm như vậy ta thu được
m (m − k + 1) k−1 tập con k phần tử của A. Nhưng không phải tất cả các tập con đều khác nhau, vì ta có thể nhận một tập con k phần tử theo k cách, cụ thể là lấy mỗi một trong k phần tử của nó ghép thêm k − 1 phần tử còn lại.

m Vì vậy số (m − k + 1) k−1 vừa tìm được ở trên gấp k lần số m k các tập con k phần tử của A. Do đó ta có đẳng thức     m m =k . (m − k + 1) k−1 k Từ đó ta suy ra       m m−k +1m−k +2 m m m−k+1 = = k k k−1 k k−1 k−2 18   (m − k + 1) . . . (m − 1) m = ... k(k − 1) . . . 2 1 m 1
là số tập con một phần tử của A. Nó bằng số phần tử của A, tức là m. Vậy   m n(m − 1) . . . (m − k + 1) = k 1.2 . . . k m(m − 1) . . . (m − k + 1)(m − k) . . . 3.2.1 = 1.2 . . . k.(m − k) . . . 3.2.1 m! . = k!(m − k)! Định nghĩa 1.2.11. Một tập con k phần tử của một tập hợp m phần tử được gọi là một tổ hợp chập k của m phần tử. Số tổ hợp chập k của m phần tử. Số đó chính là số m k
= |Tk (A)| đã tìm thấy ở trên   m(m − 1) . . . (m − k + 1) m m! = . (1.2) = k!(m − k)! 1.2 . . . k k
Nhận xét 1.2.12. Ta có m0 = 1, vì chỉ có một tập con không chứa phần
tử nào, đó là tập rỗng. Mặt khác ta cũng có m m = 1, vì chỉ có một tập con chứa m phần tử, đó là tập A. Cho X là tập có n phần tử và k > 0 là một số tự nhiên. Đặt Nk = {1, 2, . . . , k}. Giả sử f : Nk −→ X là một ánh xạ. Khi đó f (1) =: a1 , ..., f (k) := ak cho ta một bộ sắp thứ tự gồm k phần tử của X (không nhất thiết khác nhau). Định nghĩa 1.2.13. Cho X là một tập hợp có n phần tử và k > 0 là một số tự nhiên. Một chỉnh hợp có lặp chập k của n phần tử là một bộ sắp thứ k tự gồm k phần tử của X. Ta kí hiệu An là số chỉnh hợp có lặp chập k của n phần tử. 19 Nhận xét 1.2.14. (i) Cho X là tập có n phần tử và k > 0 là một số tự nhiên. Đặt Nk = {1, 2, . . . , k}. Khi đó mỗi chỉnh hợp có lặp chập k của n phần tử (a1 , . . . , ak ) (với ai ∈ X) cho ta một ánh xạ f : Nk −→ X xác định bởi f (i) = ai , i = 1, . . . , k. Ngược lại, mỗi ánh xạ f : Nk −→ X cho ta một chỉnh hợp (f (1), . . . , f (k)). Vì thế có một song ánh giữa tập các ánh xạ từ k Nk đến X và tập các chỉnh hợp có lặp chập k của n phần tử. Do đó An cũng chính là số ánh xạ từ Nk đến X. (ii) Trong chỉnh hợp có lặp chập k của n phần tử, thì số k có thể lớn hơn n. Trường hợp k = 0, để cho thuận tiện, người ta quy ước rằng có đúng một chỉnh hợp có lặp chập 0 của n phần tử, và do đó có đúng một ánh xạ từ tập rỗng vào tập gồm n phần tử (đó là ánh xạ rỗng). Mệnh đề 1.2.15. Chỉnh hợp có lặp chập k của n phần tử được cho bởi công thức k An = nk . Chứng minh. Gọi X là một tập hợp có n phần tử. Kí hiệu X k là tập tích Đề các X × . . . × X (k lần). Ta thấy rằng mỗi chỉnh hợp có lặp chập k của n k phần tử tương ứng 1-1 với một phần tử của tập X k . Do đó An bằng với số phần tử của tập X k . Để tạo thành một phần tử (a1 , . . . , ak ) của X k , ta có n cách chọn phần tử của X cho toạ độ thứ nhất a1 , với mỗi cách chọn toạ độ thứ nhất có n cách chọn phần tử cho toạ độ thứ hai a2 ,. . . , và cuối cùng, cứ mỗi cách chọn các phần tử cho các toạ độ thứ 1, 2, . . . , k − 1 ta có n cách k k chọn phần tử cho toạ độ cuối cùng ak . Do đó ta có An = n.n. | {z. . . n} = n . k Hệ quả 1.2.16. Số ánh xạ từ tập gồm k phần tử tới tập gồm n phần tử là nk . Định nghĩa 1.2.17. Cho X là một tập hợp có n phần tử và 0 < k 6 n là một số tự nhiên. Một chỉnh hợp không lặp chập k của n phần tử là một bộ 20 sắp thứ tự gồm k phần tử phân biệt của X. Ta kí hiệu Akn là số chỉnh hợp không lặp chập k của n phần tử. Nhận xét 1.2.18. Cho X là tập có n phần tử và 0 < k 6 n là một số tự nhiên. Đặt Nk = {1, 2, . . . , k}. Khi đó mỗi chỉnh hợp không lặp chập k của n phần tử (a1 , . . . , ak ), với ai ∈ X cho ta một ánh xạ f : Nk −→ X xác định bởi f (i) = ai , i = 1, . . . , k. Hơn nữa, ánh xạ này là đơn ánh vì các phần tử ai , i = 1, . . . , k, là đôi một phân biệt. Ngược lại, mỗi đơn ánh f : Nk −→ X cho ta một chỉnh hợp (f (1), . . . , f (k)). Hơn nữa, chỉnh hợp này là không lặp vì các ảnh f (1), . . . , f (k) của đơn ánh f là đôi một phân biệt. Vì thế có một tương ứng 1-1 giữa tập các đơn ánh từ Nk đến X và tập các chỉnh hợp không lặp chập k của n phần tử. Do đó số đơn ánh từ Nk đến X là Akn . Mệnh đề 1.2.19. Số các chỉnh hợp không lặp chập k của n phần tử được cho bởi công thức Akn = n! , (n − k)! trong đó ta quy ước 0! = 1. Chứng minh. Cho X là một tập hợp có n phần tử. Khi đó Akn chính là số bộ gồm k toạ độ phân biệt (a1 , . . . , ak ), trong đó mỗi toạ độ là một phần tử của X. Để có một bộ như thế, có n cách chọn phần tử của X cho toạ độ thứ nhất a1 , với mỗi cách chọn toạ độ thứ nhất có n − 1 cách chọn phần tử cho toạ độ thứ hai a2 ,. . . , và cuối cùng, cứ mỗi cách chọn toạ độ thứ 1, 2, . . . , k − 1 có n − k + 1 cách chọn phần tử cho toạ độ ak (tọa độ thứ k). Do đó ta có Akn = n(n − 1) . . . (n − k + 1) = n! . (n − k)! Hệ quả 1.2.20. Với k 6 n là các số tự nhiên, số đơn ánh từ một tập gồm k phần tử tới một tập gồm n phần tử là n! . (n − k)!