Đăng ký Đăng nhập
Trang chủ Một số phương pháp và kỹ thuật đếm cơ bản trong lý thuyết tổ hợp và áp dụng...

Tài liệu Một số phương pháp và kỹ thuật đếm cơ bản trong lý thuyết tổ hợp và áp dụng

.PDF
52
235
104

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------ Lê Quang Việt MỘT SỐ PHƯƠNG PHÁP VÀ KỸ THUẬT ĐẾM CƠ BẢN TRONG LÝ THUYẾT TỔ HỢP VÀ ÁP DỤNG 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ố: 60460113 Người hướng dẫn khoa học GS. TSKH. NGUYỄN VĂN MẬU THÁI NGUYÊN - NĂM 2013 1 . 2 Mục lục Mở đầu 4 Lời cảm ơn 5 1 Các quy tắc đếm cơ bản trong tổ hợp 1.1 Một số kiến thức cơ bản của tổ hợp . . . . . . . . . 1.1.1 Tập hợp . . . . . . . . . . . . . . . . . . . . 1.1.2 Công thức tính lực lượng của tập hợp . . . . 1.1.3 Công thức bao hàm và loại trừ . . . . . . . . 1.2 Hai quy tắc cơ bản của phép đếm . . . . . . . . . . 1.2.1 Quy tắc cộng . . . . . . . . . . . . . . . . . 1.2.2 Quy tắc nhân . . . . . . . . . . . . . . . . 1.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Hoán vị không lặp . . . . . . . . . . . . . . . 1.3.2 Hoán vị có lặp . . . . . . . . . . . . . . . . . 1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Chỉnh hợp không lặp . . . . . . . . . . . . . 1.4.2 Chỉnh hợp có lặp . . . . . . . . . . . . . . . 1.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1 Tổ hợp không lặp . . . . . . . . . . . . . . . 1.5.2 Tổ hợp có lặp . . . . . . . . . . . . . . . . . 1.5.3 Khai triển lũy thừa của nhị thức . . . . . . . 1.5.4 Tính số phần tử của một tập hợp các tập hợp 2 Các phương pháp đếm sử dụng hàm sinh 2.1 Chuỗi lũy thừa hình thức . . . . . . . . . . . . 2.1.1 Định nghĩa . . . . . . . . . . . . . . . 2.1.2 Các phép toán trên CN . . . . . . . . . 2.2 Phương pháp đếm bằng hàm sinh thông thường . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6 6 7 9 10 10 12 14 14 16 17 17 19 20 20 21 22 23 . . . . 27 27 27 28 30 3 2.3 2.2.1 Định nghĩa hàm sinh thường . . . . . . . . . . . . 2.2.2 Sử dụng hàm sinh thường để giải các bài toán đếm Phương pháp đếm bằng hàm sinh mũ . . . . . . . . . . . . 2.3.1 Định nghĩa hàm sinh mũ . . . . . . . . . . . . . . 2.3.2 Sử dụng hàm sinh mũ để giải các bài toán đếm . . 3 Phương pháp đếm bằng các công thức nghịch đảo 3.1 Công thức nghịch đảo các đồng nhất thức tổ hợp . . 3.2 Công thức nghịch đảo nhị thức . . . . . . . . . . . . 3.3 Công thức nghịch đảo Stirling . . . . . . . . . . . . 3.4 Công thức sàng . . . . . . . . . . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 33 37 37 37 . . . . . . 40 43 44 45 46 50 51 4 Mở đầu Trong lý thuyết tổ hợp các phép đếm luôn chiếm một phần vô cùng quan trọng và có ứng dụng vô cùng đa dạng. Các phương pháp đếm số lượng phần tử của một tập hợp đóng vai trò quan trọng trong một số môn khoa học, đặc biệt là Tin học và Toán học ứng dụng. Đối với chương trình toán phổ thông các phương pháp đếm luôn là chuyên đề quan trọng và hết sức cần thiết trong việc bồi dưỡng học sinh giỏi Toán ở bậc học phổ thông, đồng thời các ứng dụng đa dạng của nó cũng luôn đem lại sự hấp dẫn đối với nhiều đối tượng học sinh và giáo viên khi nghiên cứu vấn đề này. Mục tiêu của Luận văn " Một số phương pháp và kĩ thuật đếm cơ bản trong lý thuyết tổ hợp và áp dụng" nhằm trình bày một số phép đếm cơ bản nhất và những ứng dụng của nó nhằm tạo ra được một đề tài phù hợp cho việc giảng dạy, bồi dưỡng học sinh trung học phổ thông. Luận văn bao gồm phần mở đầu, kết luận, tài liệu tham khảo và 3 Chương. Chương 1 trình bày tóm tắt một số kiến thức cơ bản của tổ hợp và các quy tắc cơ bản của phép đếm. Trong chương này cũng trình bày một số ví dụ và các bài toán về tính lực lượng tập hợp, bài toán về khai triển nhị thức. Chương 2 trình bày các phương pháp đếm bằng hàm sinh thông thường và phương pháp đếm bằng hàm sinh mũ cùng các ví dụ áp dụng. Chương 3 trình bày các phương pháp đếm bằng các công thức nghịch đảo các đồng nhất thức tổ hợp bao gồm công thức nghịch đảo nhị thức, nghịch đảo Stirling, công thức sàng và các ví dụ áp dụng. 5 Lời cảm ơn Trong suốt quá trình làm luận văn, tôi luôn nhận được sự hướng dẫn và giúp đỡ tận tình của GS.TSKH Nguyễn Văn Mậu. Tôi xin được bày tỏ lòng biết ơn sâu sắc nhất đến thầy. Trong quá trình học tập tôi cũng đã nhận được sự quan tâm giúp đỡ và sự giảng dạy nhiệt tình của các Thầy, các Cô dạy lớp cao học toán K5B (2011 -2013), tôi xin được bày tỏ lòng biết ơn đến các Thầy, các Cô. Tôi xin chân thành cảm ơn các Thầy cô trong BGH trường ĐH Khoa Học ĐH Thái Nguyên đã tạo kiều kiện thuận lợi cho tôi trong suốt thời gian học cao học. Mặc dù đã có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót. Tác giả mong nhận được những ý kiến đóng góp của quý thầy, cô và bạn đọc để luận văn được hoàn thiện hơn. Xin trân trọng cảm ơn ! Hải phòng, tháng 5 năm 2013 Người viết Luận văn Lê Quang Việt 6 Chương 1 Các quy tắc đếm cơ bản trong tổ hợp 1.1 1.1.1 Một số kiến thức cơ bản của tổ hợp Tập hợp Khái niệm về tập hợp Tập hợp ( còn gọi là tập ) là một khái niệm cơ bản của toán học, không định nghĩa. Giả sử cho tập hợp A. Để chỉ a là một phần tử của tập hợp A, ta viết a ∈ A ( đọc là a thuộc A). Để chỉ a không là một phần tử của tập hợp A, ta viết a ∈ / A ( đọc là a không thuộc A). Một tập hợp được coi là xác định nếu ta có thể chỉ ra được tất cả các phần tử của nó. Các cách xác định tập hợp: Tập hợp được xác định bằng một trong hai cách sau: - Liệt kê chúng(thường dùng để biểu thị các tập hữu hạn). Ví dụ: Tập các số tự nhiên chẵn nhỏ hơn 10 A = {0, 2, 4, 6, 8} - Chỉ ra tính chất đặc trưng của chúng. Ví dụ:  B = x ∈ Z|x2 − 3x + 2 ≥ 0 Tập con. - Tất cả các phần tử của tập B đều thuộc tập A thì ta nói tập B là tập con của tập A và viết B ⊆ A - Trường hợp B ⊆ A và B 6= A thì B được gọi là tập con không tầm thường 7 (hay tập con thực sự) của tập A và viết B ⊂ A Tập rỗng -Tập hợp rỗng (hay tập hợp trống) là tập hợp không chứa một phần tử nào và thường được ký hiệu là ∅ - Quy ước tập rỗng là con của bất kỳ tập nào Hợp, giao, hiệu và phần bù của hai tập hợp. Giả sử có các tập A, B. - Tập hợp gồm các phần tử hoặc thuộc tập A hoặc thuộc tập B được gọi là hợp của tập A và tập B và ký hiệu là A ∪ B hoặc A ∨ B. - Tập hợp gồm các phần tử thuộc đồng thời cả tập A và tập B được gọi là giao của tập A và tập B ký hiệu là A ∩ B hoặc A ∧ B . - Tập hợp gồm các phần tử thuộc tập A mà không thuộc tập B được gọi là hiệu của tập A và tập B. Kí hiệu A\B - Trường hợp tập B là tập con của tập A. Hiệu của tập A và tập B được gọi là tập phần bù (hay phần bù) của tập B (đối với tập A) và ký hiệu hoặc bằng hoặc bằng CA (B) hoặc bằng C (B). Lực lượng của tập hợp. Giả sử có tập A. Số phần tử trong tập A được gọi là lực lượng của tập A, ký hiệu là |A|. 1.1.2 Công thức tính lực lượng của tập hợp Với hai tập hợp V1 , V2 ta có |V1 ∪ V2 | = |V1 | + |V2 | − |V1 ∩ V2 | . (1.1) Với ba tập hợp V1 , V2 , V3 ta có |V1 ∪ V2 ∪ V3 | = |V1 | + |V2 | + |V3 | − |V1 ∩ V2 | − |V2 ∩ V3 | − |V1 ∩ V3 | + |V1 ∩ V2 ∩ V3 | . (1.2) Tổng quát với các tập tùy ý V1 , V2 , . . . , Vn bằng phương pháp quy nạp 8 theo n (n ≥ 2) ta có công thức n n [ X X | Vi ∩ Vj | + | V1 ∩ V2 ∩ V 3 | + | V1 ∩ V2 ∩ V4 | | Vi | − Vi = i=1 i=1 i6=j + · · · + | Vn−2 ∩ Vn−1 ∩ Vn | − · · · − (−1)n | V1 ∩ V2 ∩ · · · ∩ Vn |. (1.3) Ví dụ 1.1 (Tài liệu tập huấn phát triển chuyên môn giáo viên trường THPT Chuyên - 2012). Chứng minh rằng bản báo cách thành tích cuối năm của một lớp sau đây là sai. "Lớp có 45 học sinh, trong đó có 30 em nam. Lớp có 30 em đạt loại giỏi và trong số này có 16 nam. Lớp có 25 em chơi thể thao và trong số này có 18 em nam và 17 em đạt loại giỏi. Có 15 em nam vừa đạt loại giỏi và chơi thể thao." Giải. Kí hiệu : V = 45 là tổng số học sinh của lớp V1 số học sinh nam V2 số học sinh đạt giỏi V3 số học sinh chơi thể thao. Khi đó |V1 ∪ V2 ∪ V3 | = |V1 |+|V2 |+|V3 |−|V1 ∩ V2 |−|V2 ∩ V3 |−|V1 ∩ V3 |+|V1 ∩ V2 ∩ V3 | = (30 + 30 + 25) − 16 − 18 − 17 + 15 = 49 > 45 = |V | Vậy bản báo cáo thành tích của lớp đó là sai. Ví dụ 1.2 (VMO 2005, Bảng B). Tìm kết quả học tập của một lớp học, người ta thấy: hơn 32 số học sinh đạt điểm giỏi ở môn Toán cũng đồng thời đạt điểm giỏi ở môn Vật Lý ; hơn 23 số học sinh đạt điểm giỏi ở môn Vật Lý cũng đồng thời đạt điểm giỏi ở môn Ngữ văn; hơn 23 số học sinh đạt điểm giỏi ở môn Ngữ Văn cũng đồng thời đạt điểm giỏi ở môn Lịch sử; hơn 23 số học sinh đạt điểm giỏi ở môn Lịch Sử cũng đồng thời đạt điểm giỏi ở môn Toán. Chứng minh rằng tồn tại ít nhất một học sinh đạt điểm giỏi ở cả bốn môn nêu trên. Giải. Ký hiệu T, L, V, S lần lượt là tập hợp các học sinh đạt điểm giỏi ở môn Toán, 9 Vật Lý, Ngữ Văn, Lịch Sử. Đặt Tl = T ∩ L, Lv = L ∩ V, Vs = S ∩ V . Từ giả thiết suy ra: |Tl | > 23 |T | , |Lv | > 32 |L| , |Vs | > 23 |V | .. Ta cần chứng minh : |T ∩ L ∩ V ∩ S| > 0. Vì T ∩ L ∩ V ∩ S = (T ∩ L) ∩ (L ∩ V ) ∩ (V ∩ S) nên ta cần chứng minh |(T ∩ L) ∩ (L ∩ V ) ∩ (V ∩ S)| > 0. Thật vậy, không mất tính tổng quát, giả sử |T | ≥ |L| ≥ |V | ≥ |S|. Ta có |Tl ∩ Lv ∩ Vs | = |(Tl ∩ Lv ) ∩ Vs | = |Tl ∩ Lv | + |Vs | − |(Tl ∩ Lv ) ∪ Vs | = |Tl | + |Lv | + |Vs | − |Tl ∪ Lv | − |(Tl ∩ Lv ) ∪ Vs | > 32 |T | + 32 |L| + 32 |V | − |L| − |V | = 32 |T | − 13 |L| − 13 |V | ≥ 32 |T | − 31 |T | − 31 |T | = 0. Vậy ta có điều phải chứng minh. 1.1.3 Công thức bao hàm và loại trừ Cho V là tập hữu hạn và V1 ⊂ V . Ta sẽ có V 1 = V \V1 Khi đó V 1 = |V | − |V1 | . (1.4) Cho tập hợp V và V1 , V2 ⊂ V . Khi đó V 1 ∩ V 2 = |V | − |V1 ∪ V1 | = |V | − |V1 | − |V1 | + |V1 ∩ V1 | . (1.5) Cho tập hợp V và V1 , V2 , V3 ⊂ V . Khi đó. V 1 ∩ V 2 ∩ V 3 = |V | − |V1 ∪ V2 ∪ V3 | = |V | − |V1 | − |V2 | − |V3 | + |V1 ∩ V2 | + |V2 ∩ V3 | + |V1 ∩ V3 | − |V1 ∩ V2 ∩ V3 | . (1.6) Tổng quát với các tập tùy ý V1 , V2 , . . . , Vn ⊂ V bằng phương pháp quy nạp theo n (n ≥ 2) ta có công thức n n \ X X V = |V | − | | + | Vi ∩ Vj | − | V1 ∩ V2 ∩ V3 | − | V1 ∩ V2 ∩ V 4 | Vi i i=1 i=1 i6=j − · · · − | Vn−2 ∩ Vn−1 ∩ Vn | + · · · + (−1)n | V1 ∩ V2 ∩ · · · ∩ Vn |. (1.7) 10 Ví dụ 1.3 ([1], Chuyên đề chọn lọc tổ hợp và toán rời rạc - Nguyễn Văn Mậu). Một cuộc Hội thao cấp Thị xã có 4 môn thi: Cầu lông, bóng bàn, chạy và cờ tướng. Có 100 vận động viên tham gia. Khi tổng kết, Ban tổ chức nhận thấy rằng: Môn cầu lông có 18 vận động viên tham gia, môn bóng bàn có 26 vận động viên tham gia, môn chạy có 19 vận động viên tham gia, môn cờ tướng có 24 vận động viên tham gia; trong đó 5 người tham gia cả cầu lông và bóng bàn; 2 người tham gia cầu lông và chạy; 3 người tham gia cầu lông và cờ tướng; 5 người tham gia bóng bàn và chạy; 4 người tham gia bóng bàn và cờ tướng; 3 người tham gia chạy và cờ tướng; 2 người tham gia đồng thời cầu lông, bóng bàn, và chạy; 3 người tham gia cầu lông, bóng bàn và cờ tướng; 2 người tham gia cầu lông, chạy và cờ tướng; 4 người tham gia bóng bàn, chạy và tờ tướng; 1 người tham gia đồng thời cả 4 môn của Hội thao. Hỏi có bao nhiêu vận động viên không tham gia thi đấu một môn nào của Hội thao? Giải. Dùng V để ký hiệu tập hợp các vận động viên tham gia hội thao. V1 tập hợp các vận động viên tham gia môn cầu lông. V2 tập hợp các vận động viên tham gia môn bóng bàn. V3 tập hợp các vận động viên tham gia môn chạy. V4 tập hợp các vận động viên tham gia môn cờ tướng. Khi đó số vận động viên không tham gia môn nào của Hội thao chính bằng lực lượng của tập V1 ∩ V2 ∩ V3 ∩ V4 : V1 ∩ V2 ∩ V3 ∩ V4 = 100 − (18 + 26 + 19 + 24)+ +(5 + 2 + 3 + 5 + 4 + 3) − (2 + 3 + 2 + 4) + 1 = 25 Vậy có 25 người không tham gia thi đấu môn nào của Hội thao. 1.2 1.2.1 Hai quy tắc cơ bản của phép đếm Quy tắc cộng Nội dung quy tắc: Giả sử có n hành động H1 , H2 , . . . , Hn không hành động nào xảy ra đồng thời. Trong đó hành động Hi có mi cách thực hiện 11 (1 ≤ i ≤ n). Khi đó sẽ có m1 + m2 + · · · + mn cách thực hiện hành động H: hoặc H1 xảy ra, hoặc H2 xảy ra , . . . , hoặc Hn xảy ra . Quy tắc cộng có chuyển sang ngôn ngữ tập hợp như sau: Cho n tập hợp V1 , V2 , . . . , Vn với |Vk | = mk (1 ≤ k ≤ n) và ∀i, j(1 ≤ i, j ≤ n)Vi ∩ Vj = ∅ khi i 6= j . Khi đó số cách thực hiện hành động H1 , hoặc H2 , . . . , hoặc Hn sẽ n S S P bằng số cách chọn phần tử v thuộc nk=1 Vk và bằng | ni=1 Ak | = |Ak |. k=1 Ví dụ 1.4 (Đề tuyển sinh vào trường ĐH Y Hà Nội - 1999). Có thể lập được bao nhiêu số chẵn gồm năm chữ số khác nhau lấy từ các chữ số 0, 2, 3, 6, 9 Giải. Gọi n = a1 a2 a3 a4 a5 là số cần lập. Vì n chẵn, nên a5 chẵn suy ra a5 ∈ {0, 2, 6}. Có hai trường hợp: Trường hợp 1 a5 = 0 thì ta có 1 cách chọn a5 = 0 4 cách chọn a1 = 0 3 cách chọn a2 = 0 2 cách chọn a3 = 0 1 cách chọn a4 = 0 Vậy ta có 1 × 4 × 3 × 2 × 1 = 24 số n. Trường hợp 2 a5 6= 0 thì ta có 2 cách chọn a5 ( vì a5 = 2 hoặc a5 = 6) 3 cách chọn a1 3 cách chọn a2 2 cách chọn a3 2 cách chọn a4 Vậy ta có 2 × 3 × 3 × 2 × 1 = 36 số n. Tổng cộng hai trường hợp ta có 24+36 = 60 số n thỏa mãn yêu cầu bài toán. Ví dụ 1.5 (Đề thi tuyển sinh đại học khối A,B - 2001). Có bao nhiêu số tự nhiên có 4 chữ số sao cho không có chữ số nào lặp lại đúng 3 lần ? Giải. 12 Gọi n = a1 a2 a3 a4 là số tự nhiên cần lập. Tổng các số n có bồn chữ số ( không chú ý đến điều kiện không có chữ số nào lại lại đúng ba lần). Ta có 9 cách chọn a1 ( do a1 6= 0 ) 10 cách chọn a2 10 cách chọn a3 10 cách chọn a4 Do đó ta có 9 × 10 × 10 × 10 = 9000 số n Tính các số n có bốn chữ số và có chữ số lập lại đúng ba lần. +) Trường hợp 1 : Ta có 9 cách chọn a1 (a1 6= 0, a1 lặp lại ba lần) Chọn a2 = a3 = a1 , có 1 cách chọn. Chọn a4 6= a1 , 9 cách chọn. Vậy ta có 9 × 9 = 81 cách. +) Trường hợp 2 : Chọn a1 6= 0 có 9 cách. Chọn a2 = a3 = a4 , có 1 cách (a2 lặp lại 3 lần) Chọn a4 6= a1 , a4 có 9 cách chọn. Vậy ta có 9 × 9 = 81 cách. +) Trường hợp 3 : Chọn a1 6= 0 có 9 cách. Chọn a3 = a4 = a1 , có 1 cách (a3 lặp lại 3 lần) Chọn a2 6= a3 , a2 có 9 cách chọn. Vậy ta có 9 × 9 = 81 cách. +) Trường hợp 4 : Chọn a1 6= 0 có 9 cách. Chọn a2 = a3 = a4 , có 1 cách (a4 lặp lại 3 lần) Vậy ta có 9 × 9 = 81 cách. Từ 4 trường hợp ta có 81 + 81 + 81 + 81 = 324 số n có một chữ số lặp lại đúng ba lần. Do đó các số n thỏa mãn yêu cầu bài toán là 9000 − 324 = 8676 số. 1.2.2 Quy tắc nhân Nội dung quy tắc : Giả sử một hành động H bao gồm n giai đoạn kế tiếp và độc lập với nhau, trong đó giai đoạn thứ i là hành động Hi , (1 ≤ i ≤ n). Ta cũng giả sử rằng hành động Hi có mi , (1 ≤ i ≤ n) cách thực hiện. Khi 13 đó hành động H sẽ có m1 m2 . . . mi cách thực hiện. Quy tắc nhân ta có thể chuyển sang ngôn ngữ tập hợp như sau :Cho n tập hợp V1 , V2 , . . . , Vn hữa hạn bất kì và|Vk | = mk (1 ≤ k ≤ n). Khi đó số cách thực hiện hành động H sẽ tương ứng bằng với lực lượng của tập tích Đề các của các tập đó : |V1 × V2 × · · · × Vn | = |V1 | |V2 | . . . |Vn | = m1 m2 . . . mn Ví dụ 1.6. Từ thành phố A đến thành phố B có 3 con đường, từ thành phố B đến thành phố C có 4 con đường. Một ô tô trở hàng từ thành phố A đến C rồi quay lại thành phố A ( cả hai lượt đi và về ô tô đều đi qua B) . Hỏi có tất cả bao nhiêu cách đi sao cho đoạn đường lúc đi không trùng với đoạn đường về. Giải. Tìm đường đi từ A đến B có 3 còn đường, đi từ B đến C có 4 con đường. Vậy ta có 3 × 4 = 12 con đường đi từ A đến C qua B. Tìm đường đi từ C về B có 3 con đường, đi từ B về A có 2 ( vì đoạn đường lúc đi không trùng với đoạn đường về) Vậy ta có 3 × 2 = 6 con đường đi từ C về A qua B. Do đó ta sẽ có 12 × 6 = 72 cách đi từ thành phố A đến thành phố C rồi quay lại thành phố A sao cho đoạn đường lúc đi không trùng với đoạn đường về. Ví dụ 1.7. Từ các số 0,1,2,3,4,5,6 có thể lập được bao nhiêu số tự nhiên có 5 chữ số khác nhau đôi một mà bắt buộc phải có chữ số 5. Giải. Gọi n = a1 a2 a3 a4 a5 là số tự nhiên cần lập.Có hai trường hợp. +) Nếu a1 = 5 thì ta có 1 cách chọn a1 6 cách chọn a2 5 cách chọn a3 4 cách chọn a4 3 cách chọn a5 Trường hợp này ta có 1 × 6 × 5 × 4 × 3 = 360 số. 14 +) Nếu a1 6= 5 : Có bốn vị trí chữ số 5 trong n ứng với một vị trí của 5 ta có chẳng hạn n = a1 a2 5a4 a5 thì ta có 5 cách chọn a1 ( vì a1 6= 0, a1 6= 5) 1 cách chọn a2 5 cách chọn a3 4 cách chọn a4 3 cách chọn a5 Trong trường hợp này ta có 4 × 5 × 1 × 5 × 4 × 3 = 1200 số n. Vậy tổng hai trường hợp ta có 1200 + 360 = 1560 số n. 1.3 Hoán vị Hoán vị thực chất là một cách sắp xếp nào đó các phần tử của một tập hợp. 1.3.1 Hoán vị không lặp Định nghĩa 1.1 ([1]-[4]). Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi cách sắp xếp n phần tử này theo một tứ tự nào đó (mỗi phần tử có mặt đúng một lần) được gọi là một hoán vị của n phần tử đã cho. Kí hiệu số hoán vị của n phần tử bằng Pn . Ta có công thức: Pn = n! Ví dụ 1.8. Với sáu chữ số 1, 2, 3, 4, 5,6 có thể lặp được bao nhiêu số gồm sáu chữ số, không trùng nhau. Giải. Mỗi số cần lập là một hoán vị của 6 số đã cho. Do đó, số cần lập bằng đúng số các hoán vị của 6 phần tử. Do đó ta có tổng số các số có 6 chữ số cần lập là : P6 = 6! = 720 Ví dụ 1.9. Từ các chữ sô 0,1,2,3,4,5 có thể lập được bao nhiêu số tự nhiên có 6 chữa số, không trùng nhau. 15 Giải. Do các số có 6 chữ số cần lập là các số tự nhiên nên chữa số 0 không được đứng vị trí đầu tiên. Xét trường hợp số 0 đứng vị trí đầu tiên các vị trí còn lại được sắp sếp từ các số 1,2,3,4,5 ta có P5 = 5! = 120 Nếu sắp sếp 6 chữa số trên thành số có 6 chữ số trong đó có cả trường hợp số 0 đứng vị trí đầu tiên ta sẽ có P6 = 6! = 720 Vậy tổng số các số tự nhiên có 6 chữa số cần lập là : P6 − P5 = 600 số. Ví dụ 1.10 ([1], Chuyên đề chọn lọc tổ hợp và toán rời rạc - Nguyễn Văn Mậu). Cho tập S = {1, 2, . . . , n} với n ≥ 1 và f là một hoán vị của tập S. Phẩn tử i của S được gọi là một điểm cố định nếu f (i) = i. Gọi Pn (k) là số hoán vị của tập S có đúng k điểm cố định. Hãy chứng minh rằng n X kPn (k) = n! (1.8) k=0 Giải. 1) Vì tổng tất cả các hoán vị của n phần tử có 0,1,2,. . . ,n điểm cố định bằng tất cả các hoán vị có thể của n phần tử, tức bằng n!, nên có đẳng thức n X Pn (k) = n! (1.9) k=0 2) Ta chứng minh rằng: ∀k (1 ≤ k ≤ n)đều có kPn (k) = n.Pn−1 (k − 1) Dùng (f, i) để kí hiệu cặp gồm hoán vị f tùy ý của n phần tử với k điểm cố định và i là điểm tùy ý trong k điểm cố định đó ( tức f (i) = i ). Thừa nhận P0 (0) = 1 Để lý giải quan hệ (1.11), ta hãy tính số N cáp cặp (f,i) bằng hai cách. Một mặt, i chạy qua k điểm cố định đã xác định, nên mỗi hoán vị trong Pn (k) hoán vị đó có mặt trong k cặp (f,i). Bởi vậy N = k.Pn (k). Mặt khác, nếu f (i) = i, thì trên tập gồm n − 1 phần tử còn lại ( tức các phần tử khác i ) hoán vị f có k − 1 điểm cố định, nên mỗi một trong n phần tử i có mặt trong Pn−1 (k − 1) cặp. Do đó N = n.Pn−1 (k − 1), nên đẳng thức (1.11) được chứng minh. Tính tổng các đẳng thức ở (1.11) theo k = 1, 2, . . . , n và dựa vào đẳng thức 16 (1.10) bằng cách thay n bằng n − 1 ta có n X k=0 1.3.2 kPn (k) = n X nPn−1 (k − 1) = n k=1 n X Pn−1 (k − 1) = n (n − 1)! = n!. k=1 Hoán vị có lặp Định nghĩa 1.2. Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi cách sắp xếp n phần tử này theo một tứ tự nào đó (mỗi phần tử có mặt ít nhất một lần) được gọi là là hoán vị lặp. Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i(1 ≤ i ≤ k) xuất hiên ni luần được kí hiệu là P (n1 , n2 , . . . , nk ) và được tính bằng công thức n! P (n1 , n2 , . . . , nk ) = n1 !n2 !...nk ! Ví dụ 1.11 (Đề tuyển sinh vào trường ĐH - Khối D - 2001). Từ các chữ số 0,1,2,3,4 có thể lập được bao nhiêu số có bảy chữ số trong đó chữ số 4 có mặt đúng ba lần, còn các chữ số khác có mặt đúng một lần. Giải. Gọi n = a1 a2 a3 ...a7 (ai ∈ X = {0, 1, 2, 3, 4, 4, 4}) là số cần lập. Áp dụng công thức ta có số n được lập kể cả các số n có dạng 0a2 a3 ...a7 là 7! 3! . Số các số n có dạng 0a2 a3 ...a7 là 6! 3! . 7! Vậy số các số n đúng yêu cầu bài toán là : 3! − 6! 3! = 720 số. Ví dụ 1.12. Với sáu chữ số 0,1,2,3,4,5 có thể lập được bao nhiêu số chia hết cho 5 gồm 11 chữ số, trong đó chữ số 1 có mặt 4 lần, chữ số 2 có mặt 3 lần, chữ số 3 có mặt 2 lần, chữ số 4 có mặt 1 lần và tổng số lần xuất hiện của chữ số 0 và chữ số 5 là 1. Giải. Gọi số cần lập là n = a1 a2 a3 ...a11 . Do n chia hết cho 5 nên n phải tận cùng bằng 0 hoặc 5. Vì tổng số lần xuất hiện trong n của 0 và 5 bằng 1 nên nếu n tận cùng 17 bằng 0 thì 5 không có mặt và ngược lại nếu n tận cùng bằng 5 thì chữ số 0 không xuất hiện. Bởi vậy ai (1 ≤ i ≤ 10) chỉ có thể là một trong những chữ số 1,2,3,4. Bởi vậy số khả năng lập phần dầu độ dài 10a1 a2 a3 ...a10 của số n bằng số hoán vị lặp của 10 phần tử thuộc 4 loại chữ sô : 1,2,3,4 với 1 xuất hiện 4 lần, 2 xuất hiện 3 lần, 3 xuất hiện 2 lần và 4 xuất hiện 1 lần, sẽ bằng P(1,2,3,4). Ngoài ra a11 lại có thể nhận giá trị 0 hoặc 5 nên số cần tìm sẽ là 2P (1, 2, 3, 4) = 1.4 1.4.1 10! .2 = 25200 1!2!3!4! Chỉnh hợp Chỉnh hợp không lặp Định nghĩa 1.3. Cho tập hợp A gồm n phần tử. Mỗi bộ gồm k 0 ≤ k ≤ n phần tử được sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử thuộc A. Kí hiệu số chỉnh hợp chập k của n phần tử bằng Akn . Số chỉnh hợp chập k của n phần tử được tính bởi công thức Akn = n(n − 1)...(n − k + 1) = n! (n − k)! Ví dụ 1.13. Một lớp học có 25 học sinh. Muốn chọn ra một lớp trưởng, một lớp phó và một thủ quỹ mà không cho kiêm nhiệm. Hỏi có bao nhiêu cách chọn ? Giải. Mỗi cách chọn tra một lớp trưởng, một lớp phó và một thủ quỹ là một chỉnh hợp chập ba 3 của tập 25 phần tử. Số các chỉnh hợp là : A325 = 25! = 13800 (25 − 3)! Vậy có 13800 cách chọn ra một lớp trưởng, một lớp phó và một thủ quỹ trong lớp học có 25 học sinh. 18 Ví dụ 1.14. Từ các số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số tự nhiên (số nguyên không âm); mà trong mỗi số này các chữ số không lặp lại. Giải. Vì có 6 chữ số khác nhau, nên số dài nhất trong các số cần tìm cũng chỉ gồm 6 chữ số. Ta lập các loại số tự nhiên dạng a1 a2 ...an Dùng S1 để kí hiệu tập số dạng a1 Dùng S2 để kí hiệu tập số dạng a1 a2 Dùng S3 để kí hiệu tập số dạng a1 a2 a3 Dùng S4 để kí hiệu tập số dạng a1 a2 a3 a4 Dùng S5 để kí hiệu tập số dạng a1 a2 a3 a4 a5 Dùng S6 để kí hiệu tập số dạng a1 a2 a3 a4 a5 a6 Kí hiệu một chỉnh hợp chập k của 6 phần tử 0, 1, 2, 3, 4, 5 bằng (Ci1 , Ci2 , . . . , Cik ). Mỗi số tự nhiên Ci1 Ci2 Cik với các chữ số khác nhau Cij thuộc tập 0, 1, 2, 3, 4, 5, (1 ≤ j ≤ k) đều tương ứng với một chỉnh hợp chập k của sáu phần tử 0, 1, 2, 3, 4, 5. Ngược lại, mỗi chỉnh hợp chập k (k ≥ 2) (Ci1 , Ci2 , . . . , Cik ) của sáu phần tử 0, 1, 2, 3, 4, 5 tương ứng với một số tự nhiên, nếu Ci1 6= 0. Ngược lại, nếu Ci1 = 0, thì nó không tương ứng với số tự nhiên gồm k chữ số. Nhưng tương ứng với một chỉnh hợp chập k – 1 (Ci2 , Ci3 . . . , Cik ) của năm phần tử 1, 2, 3, 4, 5. Từ đó có 6! 5! − = 720 − 120 = 600; 0! 0! |S5 | = A56 − A45 = 720 − 120 = 600; |S6 | = A66 − A55 = |S4 | = A46 − A35 = 300; |S3 | = A36 − A25 = 100; |S2 | = A26 − A25 = 25; |S1 | = 6 Vậy các số tự nhiên có thể lập là: S = |S1 |+|S2 |+|S3 |+|S4 |+|S5 |+|S6 | = 6+25+100+300+600+600 = 1631. 19 Ví dụ 1.15. ( Bài toán đếm số tất cả các hàm đơn ánh từ một tập hữu hạn vào một tập hữu hạn) Giả sử N và M là hai tập hữu hạn với |N | = n và |M | = m . Hãy xác định số các hàm đơn ánh f : N → M . Giải. Giả sử N = {a1 , a2 , ..., an } . Khi đó một hàm đơn ánh f : N → M tương ứng với đúng một bộ có thứ tự gồm n thành phần là (f (a1 ) , f (a2 ) , ..., f (an )) với f (a1 ) , f (a2 ) , ..., f (an ) ∈ M . và f (ai ) 6= f (aj ) nếu i 6= j Do đó số các hàm f : N → M bằng số chỉnh hợp chập n của m phần tử của M, tức là bằng Anm Vậy ta có số tất cả các hàm đơn ánh f : N → M với |N | = n và |M | = m bằng Anm 1.4.2 Chỉnh hợp có lặp Định nghĩa 1.4. Cho tập hữu hạn X gồm n phần tử. Mỗi dãy có độ dài k các phần tử của tập X, mà mỗi phần tử có thể lặp lại nhiều lần và được sắp xếp theo một thứ tự nhất định được gọi là một chỉnh hợp lặp chập k của n phần tử thuộc tập X. Số chỉnh hợp lặp chập k của n phần tử, ký hiệu là Akn , bằng số ánh xạ từ tập k phần tử đến tập n phần tử và bằng nk , tức Akn = nk . Ví dụ 1.16. Từ bốn chữ số 1, 2, 3, 5 có thể thành lập được bao nhiêu số chẵn gồm 4 chữ số? Giải. Vì tập 1, 2, 3, 5 chỉ có duy nhất một chữ số chẵn là 2, nên x = abcd với a, b, c, d thuộc tập 1, 2, 3, 5 là số chẵn khi và chỉ khi d bằng 2. Mặt khác a, b, c có thể bằng nhau, nên y = abc là một chỉnh hợp lặp chập 3 của bốn phần tử 1, 2, 3, 5. Để thành lập số x ta chỉ cần lấy một số y nào đó rồi thêm 2 vào cuối. Bởi vậy, số các số x = abc2 bằng các số y = abc và bằng A34 = 43 = 64. Chẳng hạn 1112, 1122, 1132, 1152, . . . , 5542, 5552. Ví dụ 1.17. ( Bài toán đếm số các hàm từ một tập hữu hạn vào một tập
- Xem thêm -

Tài liệu liên quan