Luận văn Một số tính chất của hệ số nhị thức

n đó cũng là một khó khăn cho các thầy cô giáo giảng dạy lứa tuổi THPT - THCS trong việc áp dụng phương pháp giảng dạy cho phù hợp. Các em thường rất máy móc, nếu gặp toán lạ là không biết cách giải quyết hay chưa đặt ra hướng giải quyết. Học sinh thiếu tính chủ động trong việc tiếp thu kiến thức. Vì vậy kiến thức dễ quên và kết quả học tập chưa cao. Hay học sinh tiếp nhận kiến thức một cách thụ động, chủ yếu theo lối đọc chép hay thiếu tính tư duy logic. “Vậy làm thế nào để học sinh học tốt phần kiến thức này?” Đó chính là một trong những lý do thôi thúc chúng tôi thực hiện đề tài “Một số tính chất của hệ số nhị thực”. Không giống như những cách chứng minh thông thường trong sách giáo khoa, ở đây chúng tôi sẽ chứng minh các đồng nhất thức bằng phương pháp mới, đó là phương pháp đặt ra các câu hỏi và trả lời bằng hai cách hoàn toàn theo toán tổ hợp thuần túy. Đây là phương pháp tiếp cận khá mới tại Việt Nam nhưng đã được sử dụng rộng rãi trên toàn thế giới và đặt nhiều thành tựu cao. 2. Lịch sử nghiên cứu: Nội dung toán tổ hợp đưa vào giảng dạy từ cấp trung học phổ thông ở hầu hết các nước trên thế giới. Tuy nhiên, ở Việt Nam nội dung toán tổ hợp được đưa vào sách giáo khoa lớp 11 năm 2000 với lượng kiến thức còn hạn chế. Dạy học phát hiện và giải quyết vấn đề là phương pháp dạy học tích cực đáp ứng yêu Thang Long University Libraty 2 cầu xã hội. Xong áp dụng phương pháp này để giảng dạy hiệu quả nội dung khó như toán tổ hợp thì cần sự đóng góp của các thầy cô giáo và các nhà khoa học. 3. Mục đích nghiên cứu: Dạy học sinh chứng minh hệ số nhị thức, các đồng nhất thức bằng định nghĩa tổ hợp thuần túy mà không sử dụng phương pháp quy nạp. Rèn luyện cho học sinh tư duy một cách logic, tư duy trừu tượng trong toán tổ hợp. 4. Phạm vi và đối tượng nghiên cứu: - Đối tượng nghiên cứu: Học sinh trung học cơ sở và giáo viên toán cấp trung học cơ sở. - Phạm vi nghiên cứu: Các trường cấp trung học cơ sở. 5. Mẫu khảo sát: Xem xét việc áp dụng dạy học chứng minh các đồng nhất thức bằng phương pháp tổ hợp đếm. 6. Câu hỏi nghiên cứu: Vận dụng phương pháp tổ hợp đếm để tiếp thu tốt hơn kiến thức cũ và lối chứng minh cũ các đồng nhất thức. 7. Giả thuyết nghiên cứu: Khi học sinh được học chương tổ hợp xác suất theo phương pháp dạy học mới là phương pháp tổ hợp đếm, đặt câu hỏi và trả lời hoàn toàn theo toán tổ hợp thuần túy. Các em sẽ tiếp thu bài tốt hơn, ngoài ra các em có thể mở rộng bài toán và có những sáng tạo toán học. 8. Phương pháp nghiên cứu: Nghiên cứu sách giáo khoa toán trung học cơ sở, đặc biệt các khối 6, 7, 8, 9. Các đề tài tham khảo, kết hợp việc nghiên cứu và thực hành chứng minh toán tổ hợp. Sử dụng phương pháp dạy học truyền thống và hiện đại một cách đan xen. 3 9. Các luận cứ thu nhập được: 9.1. Luận cứ lí thuyết: - Lý thuyết dạy học phát hiện và giải quyết vấn đề. - Thực trạng dạy và học ở trường trung học cơ sở. - Dạy học phát hiện và giải quyết vấn đề trong toán. 9.2. Luận cứ thực tế: Kết quả thực nghiệm về năng lực học tập của học sinh sau quá trình giảng dạy của giáo viên lớp thực nghiệm. 10. Cấu trúc luận văn: Ngoài phần mở đầu, kết luận khuyến nghị, tài liệu tham khảo, phụ lục, nội dung chính của luận văn được trình bày trong 2 chương. Chương 1: Giới thiệu về hệ số nhị thức. Chương 2: Các đồng nhất thức của hệ số nhị thức. Thang Long University Libraty 4 CHƯƠNG 1 GIỚI THIỆU VỀ HỆ SỐ NHỊ THỨC VÀ KIẾN THỨC CHUẨN BỊ Ở chương 1, chúng tôi xin trình bày khái quát về lịch sử toán tổ hợp trong cấp trung học cơ sở, giới thiệu về hệ số nhị thức. Những kiến thức chuẩn về kĩ thuật đếm, các nguyên lý đếm cơ bản, các khái niệm cơ bản hàm toán học sẽ được chúng tôi giới thiệu theo phương pháp đếm. Kiến thức chính trong chương 1 này, chúng tôi sử dụng một số tài liệu tham khảo sau: 1. Nguyễn Hữu Anh, Toán rời rạc, NXB Đại học Quốc Gia TP. Hồ Chí Minh, 2001 2. Trần Ngọc Danh, Toán rời rạc nâng cao, NXB Đại học Quốc Gia TP. Hồ Minh 3. Schaum's Outline of Discrete Mathematics, McGraw - Hill, 1977 1.1. LỊCH SỬ TOÁN TỔ HỢP TRONG CẤP THCS: Nội dung: “Đại số tổ hợp” cung cấp kiến thức cơ bản về đại số tổ hợp và lý thuyết sác xuất. Đại số tổ hợp, còn giới thiệu về hai quy tắc đếm cơ bản, các khái niệm, các công thức về hoán vị, chính hợp, tổ hợp, công thức khai triển nhị thức Niu-tơn và áp dụng của nó. Nó còn cung cấp khái niệm mở đầu và các công thức đơn giản nhất của lí thuyết xác suất, một lĩnh vực quan trọng của Toán học, có nhiều ứng dụng thực tế. Trong những năm 80 của thế kỷ trước, Đại số tổ hợp đưa vào chương trình sách giáo khoa và mang tính chất giới thiệu. Đến năm 1994 - 1995, trong chương trình thí điểm chuyên ban, Đại số tổ hợp được đưa vào dạy cùng xác suất. Mục tiêu dạy học phần này là hình thành khái niệm ban đầu về Đại số tổ hợp, học sinh cần nắm được các quy tắc đếm, cách tính số hoán vị, chính hợp, tổ hợp, biết cách áp dụng vào các bài toán, đơn giản của thực tiễn và xác 5 suất cổ điển, đồng thời biết công thức khai triển nhị thức Niu-tơn và sử dụng công thức đó vào việc giải toán. 1.2. GIỚI THIỆU VỀ HỆ SỐ NHỊ THỨC: 1.2.1. Định nghĩa: * Định nghĩa: Chúng ta định nghĩa n k       là số tập con có k phần tử (k phần tử khác nhau và không phân biệt thứ tự) lấy từ tập gồm n phần tử. Nói một cách khác, n k       được tính theo cách chọn tập con có k phần tử từ tập có n phần tử mà thứ tự sắp xếp là không quan trọng. 1.2.2. Công thức:   ! ! ! n n k k n k       Công thức này là hệ quả của đồng nhất thức 1 sẽ được chúng tôi chứng minh ở chương 2. n k       đọc là tổ hợp n chập k Lưu ý rằng, ở một số quốc gia châu Á trong đó có Việt Nam thường ký hiệu tổ hợp n chập k là k nC Toàn bộ luận văn này, chúng tôi sử dụng ký hiệu quốc tế là n k       . Thang Long University Libraty 6 1.3. KỸ THUẬT ĐẾM: 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 phần 1.3 là kiến thức chuẩn bị này 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. Đếm bằng hai cách là một kỹ thuật đếm thông dụng để tạo ra các phương trình, đẳng thức, các mối liên hệ giúp chúng ta giải quyết các bài toán phương trình, tính toán hình học, bất phương trình và đặc biệt là các bài toán tổ hợp trong đó có bài toán đếm. 1.3.1. Một số kiến thức cơ bản của tổ hợp: a. 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 Aa (đọ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 Aa (đọc là a không thuộc Aa ). 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 7 - Chỉ ra tính chất đặc trưng của chúng. Ví dụ:  2B 3x 2 0x x     * 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 được gọi là tập con của tập A và viết B A . - Trường hợp B A và B A thì B được gọi là tập con không tầm thường (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 hợ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 và 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 là 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 AC (B) hoặc C(B) . b. Công thức tính của tập hợp: Với hai tập hợp 1 2V ,V ta có : 1 2 1 2 1 2V V V + V V V    Với ba tập hợp 1 2 3V ,V ,V ta có: 1 2 3 1 2 3 1 2 2 3 1 3 1 2 3V V V V + V + V V V V V V V V V V            Thang Long University Libraty 8 Tổng quát với các tập tùy ý 1 2V ,V ,...,Vn bằng phương pháp quy nạp theo n ( 2)n  , ta có công thức: 1 2 3 1 2 4 11 V V V V V V V V V V n n i i i j i i ji             2 1 1 2.... V V V ... ( 1) V V ... V n n n n n           Ví dụ 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áo 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: 1V số học sinh nam. 2V số học sinh đạt giỏi. 3V số học sinh chơi thể thao. Khi đó:   1 2 3 2 3 1 2 2 3 1 3 1 2 31 V V V V V V V V V V V V V V V 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. 9 V1 V2 V3 1.3.2. Công thức bao hàm và loại trừ: Cho V là tập hợp hữu hạn và 1V V . Ta sẽ có 1 1V V\V . Khi đó: 1 1V = V - V a. Cho tập hợp V và 1 2V ,V V . Khi đó : 1 2 1 1 1 1 1 1V V V - V V V V - V + V V      b. Cho tập hợp V và 1 2 3V ,V ,V V . Khi đó: 1 2 3 1 2 3 1 2 3 1 2 2 3 1 3 1 2 3 V V V V V V V V V V V V V V V V V V V V                    c. Tổng quát với các tập tùy ý 1 2V ,V ,...,V Vn  bằng phương pháp quy nạp theo  2n n  ta có công thức:   1 2 3 1 2 4 11 2 1 1 2 V V V V V V V V V V V ... V V V ... 1 V V ... V n n i i i j i i ji n n n n n                           1V 1 2V V 2V Thang Long University Libraty 10 Ví dụ 2: ( 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 thảo 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à cờ 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 bộ 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. 1V tập hợp các vận động viên tham gia môn cầu lông. 2V tập hợp các vận động viên tham gia môn bóng bàn. 3V tập hợp các vận động viên tham gia môn chạy. 4V 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 1 2 3 4V V V V   :       1 2 3 4V V V V 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. 11 1.3.3. Hai quy tắc cơ bản của phép đếm: a. Quy tắc cộng: Ví dụ: Hoặc là một giảng viên của khoa Toán, hoặc là một sinh viên của khoa Toán sẽ là đại diện của trường. Như vậy nếu có 24 giảng viên, 310 sinh viên thì có bao nhiêu cách chọn lựa đại diện ? Lời giải: Chọn đại diện từ giảng viên thì có 24 cách, chọn đại diện từ sinh viên thì có 310 cách. Như vậy ta có 24 310 350  cách lựa chọn đại điện. Giả thiết: Công việc 1 có thể làm bằng 1n cách, công việc 2 có thể làm bằng 2n cách. Nếu hai công việc không thể làm đồng thời thì có 1 2n n cách làm một trong hai công việc. Tổng quát hóa quy tắc cộng: Tổng quát lên m công việc không thể làm đồng thời và số cách làm chúng tương ứng là 1 2, ,..., mn n n . Số cách làm một trong m công việc là P = 1...i im n . Ví dụ: Một sinh viên chọn đồ án môn học trong 5 nhóm: Khoa học máy tính, cơ sở dữ liệu, công nghệ phần mềm, hệ thống & mạng máy tính, kỹ thuật máy tính. Mỗi nhóm có số lượng đề tài tương ứng là: 10, 15, 14, 16, 11. Có bao nhiêu cách chọn? Lời giải: 10+15+14+16+11 = 66 cách. Thang Long University Libraty 12 Góc nhìn tập hợp: Giả thiết 1 2A ,A ,...,Am là các tập hợp rời nhau (disjoint). Khi đó số cách để chọn một phần tử từ một trong các tập chính là: 1 2 1 2A A ... A A A ... Am m       b. Quy tắc nhân: Ví dụ: Một trung tâm máy tính có 32 máy vi tính. Một máy có 12 cổng. Như vậy trung tâm có bao nhiêu cổng? Lời giải: Quá trình gồm hai bước: Bước 1: Chọn máy Bước 2: Chọn cổng của máy được chọn Dễ thấy, số cách là 32 12 384  cổng. Giả thiết: Một nhiệm vụ được tách làm hai việc: Việc 1 làm bằng 1n cách, việc 2 làm 2n cách khi việc 1 đã được làm. Khi đó sẽ có 1 2n n cách thực hiện nhiệm vụ. Tổng quát quy tắc nhân: Giả thiết một nhiệm vụ có m công việc phải thực hiện 1T ,...,Tm . Nếu việc Ti có in cách thực hiện. Khi đó ta có 1 ... nmn   cách thực hiện nhiệm vụ. Ví dụ: Có bao nhiêu xâu nhị phân có độ dài 7? Lời giải: Mỗi bit có thể chọn một trong hai cách: 0 và 1. Quy tắc nhân cho số lượng xâu là 72 128 . Ví dụ: Có bao nhiêu hàm đơn ánh xác định trên tập hữu hạn A có m phần tử và nhận giá trị trên tập B có n phần tử? 13 Phối hợp 2 quy tắc: Sẽ được chứng minh qua các đồng nhất thức ở chương 2 1.3.4. 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. a. Hoán vị không lặp: * Định nghĩa: Cho một tập hợp gồm  1n n  phần tử. Một cách sắp xếp n phần tử này theo một thứ 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: P !n n Ví dụ: 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à: 6 6! 720P   Ví dụ: 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ữ số, không trùng nhau. 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í còn lại được sắp xếp từ các số 0, 1, 2, 3, 4, 5 ta có 5 5! 120P   Nếu sắp xếp 6 chữ 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ó 6 6! 720P   Vậy tổng số các số tự nhiên có 6 chữ số cần lập là: 6 5 600P P  số. Thang Long University Libraty 14 Ví dụ: (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  1,2,...,S n với 1n  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 P ( )n 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: 0 P ( ) ! n n k k k n    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: 0 P ( ) ! n n k k n   2. Ta chứng minh rằng: (1 )k k n   đều có 1P ( ) P ( 1)n nk k n k  . 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 0P (0) 1 Để lý giải quan hệ (1.11), ta hãy tính số N các cặp  ,f i bằng hai cách. Một mặt, i chạy qua điểm k cố định đã xác định, nên mỗi hoán vị trong P ( )n k hoán vị đó có mặt trong k cặp  ,f i . Bởi vậy  N= .Pnk k . Mặt khác, nếu ( )f i i , thì trên tập gồm  1n  phần tử còn lại (tức các phần tử khác i ) hoán vị có f có  1k  điểm cố định, nên mỗi một trong n phần tử i có mặt trong 1P ( 1)n k  cặp. Do đó 1N .P ( 1)nn k  , nên đẳng thức (1.11) được chứng minh. Tính tổng các đẳng thức ở (1.11) theo 1,2,...,k n và dựa vào đẳng thức (1.10) bằng cách thay n bằng  1n  ta có: 1 1 0 1 1 P ( ) P ( 1) P ( 1) ( 1)! ! n n n n n n k k k k k n k n k n n n              15 b. Hoán vị có lặp: * Định nghĩa: Cho một tập hợp gồm  1n n  phần tử. Mỗi cách sắp xếp n phần tử này theo một thứ tự nào đó (mỗi phần tử có mặt ít nhất một lần) được gọi 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 (1 )i i k  xuất hiện in lần được ký hiệu là 1 2P( , ,..., )kn n n và được tính bằng công thức: 1 2 2 ! P( , ,..., ) ! !... ! k k n n n n n n n  Ví dụ: (Đề 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  1 2 3 7... ( X 0,1,2,3,4,4,4 )in a a a a a   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 2 3 70 ...a a a là 7! 3! . Số các số n có dạng 2 3 70 ...a a a là 6! 3! Vậy số các số n đúng yêu cầu bài toán là 7! 3! - 6! 3! = 720 số Ví dụ: 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 lần. Thang Long University Libraty 16 Giải: Gọi số cần lập là 1 2 3... 11n a a a a . 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 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 (1 10)ia i  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 đầu độ dài 1 2 3 1010 ....a a a a 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 11a lại có thể nhận giá trị 0 hoặc 5 nên số cần tìm sẽ là:   10! 2P 1,2,3,4 .2 25200 1!2!3!4!   1.3.5. Chỉnh hợp: a. Chỉnh hợp không lặp: * Định nghĩa: Cho tập hợp A gồm n phần tử. Mỗi bộ gồm (0 )k 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:       ! A 1 ... 1 ! k n n n n n k n k       Ví dụ: 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ác chọn ra 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 3 của tập 25 phần tử. 17 Số các chỉnh hợp là:   3 25 25! 13800 25 3 ! A    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. b. Chỉnh hợp có lặp: * Định nghĩa: 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 kn , tức k knA n . Ví dụ: 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 dx abc 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 1, ,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ố 2x abc bằng các số y abc và bằng 3 34 4 64.A   Chẳng hạn 1112, 1122, 1132, 1152,..., 5542, 5552. Thang Long University Libraty 18 Ví dụ: (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 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 các hàm f: N M . Giải: Giả sử  1 2N , ,... .na a a Khi đó một hàm f: N M tương ứng với đúng một bộ có thứ tự gồm n thành phần là       1 2, ,..., nf a f a f a với      1 2, ,..., Mnf a f a f a  . Do đó số các hàm f: N M bằng số chỉnh hợp có lặp chập n của m phần tử của M, tức là bằng n nmA m . Vậy ta có số tất cả các hàm f: N M với N n và M m bằng An nm m 1.3.6. Tổ hợp: a. Tổ hợp không lặp: * Định nghĩa: Cho tập A gồm n phần tử. Mỗi tập con gồm  0k k n  phần tử thuộc A được gọi là tổ hợp chập k của n phần tử đã cho. * Nhận xét: Hai tổ hợp được coi là khác nhau khi và chỉ khi có ít nhất một phần tử khác nhau. Số tổ hợp chập  0k k n  của n phần tử, được kí hiệu là n k       và được tính theo công thức   ! ! ! n n k k n k       Ví dụ: Có bao nhiêu cách chia một lớp 40 học sinh thành bốn tổ, sao cho mỗi tổ có đúng 10 học sinh? 19 Giải: Đầu tiên lập tổ 1 bằng cách chọn tùy ý 10 học sinh trong 40 học sinh của lớp, nên số cách chọn bằng đúng số tổ hợp chập 10 của 40 phần tử, tức bằng 40 40! 10 10!30!       Tổ 2 có thể chọn 10 em tùy ý trong 30 em còn lại, nên số cách thành lập tổ 2 sẽ bằng số tổ hợp chập 10 của 30 phần tử, tức bằng 30 30! 10 10!20!       . Tổ 3 có thể chọn 10 em trong 20 em còn lại, nên số cách thành lập tổ 3 sẽ bằng số tổ hợp chập 10 của 20 phần tử, tức bằng 20 20! 10 10!10!       . Tổ 4 gồm 10 em còn lại, nên chỉ có 1 cách chọn. Vậy số cách chia lớp sẽ là:   4 40 30 20 10 40!30!20! 40! 10 10 10 10 10! 30! 20!10!10!10! 10!                             b. Tổ hợp có lặp: * Định nghĩa: Cho tập hợp 1 2A , ,..., na a a . Một tổ hợp lặp chập m (m không nhất thiết phải nhỏ hơn n ) của n phần tử thuộc A là một bộ gồm m phần tử, mà mỗi phần tử này là một trong những phần tử của A. Ta sử dụng * n k       hay n k          để kí hiệu số tổ hợp lặp chập m của n phần tử. Khi đó: * 1n n k k k              Thang Long University Libraty 20 Ví dụ: (Lý thuyết tổ hợp và đồ thị - Ngô Đắc Tân). Tại Việt Nam hiện đang có bán 10 loại máy vi tính khác nhau mà ta gọi là loại máy 1,..., loại máy 10. Một cơ quan muốn mua 5 máy vi tính. Hỏi cơ quan có bao nhiêu sự lựa chọn khác nhau? Giải: Giả sử 1a là một máy vi tính thuộc loại máy 1; 2a là một máy vi tính thuộc loại máy 102,...,a là một máy vi tính thuộc loại máy 10, và  1 2 10A , ,...,a a a . Mỗi cách chọn 5 máy vi tính có thể coi là một tổ hợp chập 10 của 5 và tổng số các tổ hợp được tính theo công thức.   * 5 10 5 1 14 14! 10 5 5 5! 14 5 ! 10 11 12 13 14 11 13 14 2002 2 3 4 5                                  Ví dụ: Giả sử có 4 loại bóng màu: Xanh, Đỏ, Tím, Vàng, với số lượng mỗi loại không hạn chế. Hai bộ bóng được xem là khác nhau, nếu có ít nhất một màu với số lượng thuộc hai bộ khác nhau. Liệu có bao nhiêu cách chọn ra các bộ 6 (quả bóng) khác nhau. Giải: Vì trong mỗi bộ 6 có thể có các quả bóng cùng màu và không phân biệt thứ tự chọn, nên số cách chọn khác nhau bằng số tổ hợp lặp chập 6 của 4 phần tử (tập hợp bóng cùng màu được coi là một phần tử) và được tính bằng công thức * 4 4 6 1 9! 84 6 6 6!3!                21 1.3.7. Tính số phần tử của một tập hợp các tập hợp: Ví dụ: Lớp 12A phải làm một bài kiểm tra Toán gồm có ba bài toán. Biết rằng mỗi em trong lớp đều giải được ít nhất một bài, trong lớp có 20 em giải được bài toán thứ nhất, 14 em giải được bài toán thứ hai, 10 em giải được bài toán thứ ba, 6 em giải được cả hai bài thứ hai và thứ ba, 2 em giải được hai bài thứ nhất và thứ hai, mà có một em được 10 điểm vì đã giải được cả 3 bài toán. Hỏi rằng lớp học có bao nhiêu em tất cả? Giải: Gọi A là tập hợp các em học sinh giải được bài toán thứ nhất. B là tập hợp các em học sinh giải được bài toán thứ 2. C là tập hợp các em học sinh giải được bài toán thứ 3. Ta phải tính số phần tử của tập hợp A B C  . Không khó khăn ta có thể thấy được công thức sau là đúng: A B C A B C A B B C C A A B C              Theo công thức trên, số học sinh trong lớp sẽ là: 20 14 10 6 5 2 1 32       Nhưng ta có thể bắt gặp những bài toán có sự tham gia của nhiều hơn ba tập hợp con. Ví dụ: Tính số cách treo 5 đôi tất trên một dây phơi sao cho không có hai chiếc tất nào cùng đôi được phơi cạnh nhau. Giải: Để giải bài toán này, cũng như nhiều bài toán tương tự, ta chứng minh định lý sau: * Định lý: Cho trước các tập hợp 1 2 nV ,V ,...,V khi đó ta có:   1 1 2 1 2 1 1 V V ... V V V V ... ... 1 V V ... V n n n i i j n i i j n                  (định lý 1.12) Thang Long University Libraty 22 Chứng minh: Định lý này có thể được chứng minh bằng hai cách: Cách 1: Chứng minh bằng quy nạp theo n . Với 1n  hiển nhiên đẳng thức đúng. Với 2n  ta cũng dễ kiểm tra để thấy rằng đẳng thức đúng. Ta giả sử (1.14) đúng cho 2n tập hợp tùy ý.   1 1 2 1 2 1 1 V V ... V V V V ... ... 1 V V ... V n n n i i j n i i j n                  Bây giờ xét 1n tập hợp tùy ý 1 2 1V ,V ,...,V ,Vn n . Lưu ý rằng:    1 2 1 i 1 1 V V ... V V V V n n n n i          (1.13) Cho nên ta có:    1 2 1 1 1 V V ... V V V V n n n i n i          Sử dụng (1.12) cho vế phải của (1.13) ta thu được     1 2 1 1 1 1 1 1 1 1 2 1 1 V V ... V V V V V V V V V V V ... 1 V V ... V V n n n i n i j n i i j n n i j k n n n i j n                                  Đặt 1 2A V V ... Vn    và 1B Vn và áp dụng đẳng thức A B A B A B     Ta thu được điều cần chứng minh.   1 1 2 1 1 1 1 1 2 1 V V ... V V V V V ... ... 1 V V ... V V n n n i i j i i j n n n n                         23 Cách 2: Ta xét một phần tử 1 2V V ... Vna    bất kì. Giả sử rằng a thuộc vào r (1 )r n  tập hợp trong số các tập hợp này. Số lần xuất hiện của a trong Công thức 1.12 trên là:     1 ... 1 1 1 1 1 1 2 3 r rr r r r r                                 Vậy Công thức 1.12 là đúng Thang Long University Libraty 24 CHƯƠNG 2 CÁC ĐỒNG NHẤT THỨC CỦA HỆ SỐ NHỊ THỨC Nội dung chương 2, chúng tôi trình bày chứng minh các đồng nhất thức bằng phương pháp đếm. Hệ thống kiến thức trong chương 2 này, chúng tôi viết dựa theo các tài liệu tham khảo sau: 1. Benjamin Arthur T., and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof. No. 27. MAA, 2003. 2.1. CÁC ĐỒNG NHẤT THỨC CƠ BẢN 2.1.1. Đồng nhất thức 1:  ! ! ! (0 ) n n k n k k n k          a. Câu hỏi: Trong một đội kiểm tra sức khỏe hàng năm của trường THCS Ngô Quyền, giáo viên chủ nhiệm muốn sắp xếp n học sinh vào một danh sách để đi khám bệnh (không theo thứ tự, tên bàn, sao cho cách sắp xếp là ngẫu nhiên và bất kỳ). Có bao nhiêu cách sắp xếp n học sinh vào danh sách khám sức khỏe? b. Trả lời: + Cách 1: Đơn giản ta sẽ có !n cách sắp xếp. + Cách 2: Đầu tiên, cô chọn ra k học sinh từ n học sinh có n k       cách. Điền tên các học sinh này vào k vị trí đầu tiên có k! cách. Số học sinh còn lại có  !n k cách sắp xếp vào các vị trí còn lại. 25 Theo quy tắc nhân, số cách chọn là  ! ! n k n k k       Vậy:    ! ! ! 0 ) n n k n k k n k          Hay   ! ! ! n n k k n k       Vậy chúng tôi đã giải bài toán đặt ra theo hai cách. 2.1.2. Đồng nhất thức 2:  0 n n k n k n k               a. Câu hỏi: Trong đợt kỉ niệm thành lập Đoàn 26 - 3, cô Bí thư Đoàn muốn chọn ra k bạn học sinh từ một chi đoàn có n học sinh để đi thăm người già neo đơn và làm tình nguyện. Có bao nhiêu cách chọn ra k học sinh từ một chi đoàm có n học sinh để tham gia tình nguyện? b. Trả lời: + Cách 1: Đơn giản ta sẽ có n k       cách sắp xếp. + Cách 2: Đầu tiên cô loại  n k bạn từ n bạn của chi Đoàn thì cô có n n k       cách của k bạn được chọn. Hay n n k n k             (với 0 k n  ) Vậy chúng tôi đã giải bài toán đặt ra theo hai cách. Hay chúng tôi có đồng nhất thức 2:  0 n n k n k n k               Thang Long University Libraty 26 2.1.3. Đồng nhất thức 3:   1 1 , 0 1 n n n k n k k k                       a. Câu hỏi: Thầy Thế hôm nay sẽ lên lớp bài “Tam giác Pascal”. Trước khi vào học bài mới, thầy muốn gọi k học sinh lên bảng kiểm tra bài cũ. Lớp thầy Thế có n học sinh, tất cả đều chăm chú và chuẩn bị tinh thần chờ thầy gọi lên bảng, duy nhất có bạn Huy là ngủ gục trong lớp. Có bao nhiêu cách gọi một bạn bất kì trong lớp lên bảng? b. Trả lời: Thầy Thế đưa ra hai cách trả lời sau: + Cách 1: Thầy sẽ gọi k bạn từ n bạn lên bảng , thầy có ngay n k       cách chọn để gọi một bạn bất kì lên bảng kiểm tra bài cũ. + Cách 2: Thầy sẽ gọi k bạn, trừ cậu Huy lên bảng ra, thầy Thế có 1n k       cách lựa chọn. Hoặc là thầy gọi bạn Huy và  1k  bạn khác từ lớp có  1n  cách lựa chọn bạn còn lại, có 1 1 n k       . Theo quy tắc cộng, hai hành động của thầy Thế cho chúng ta có 1 1 1 n n k k              cách chọn. Vậy chúng tôi đã giải bài toán đặt ra theo hai cách. Hay chúng tôi có kết quả của đồng nhất thức 3:   1 1 , 0 1 n n n k n k k k                       27 2.1.4. Đồng nhất thức 4:   0 2 0n k n n k         a. Câu hỏi: Trong một đợt đi tham quan để học hỏi kinh nghiệm làng nghề của một xã A. Bác chủ tịch xã chọn ra một số người bất kỳ trong n người của xã để đi tham quan. Có bao nhiêu cách lựa chọn để lập ra một nhóm người để đi tham quan? b. Trả lời: + Cách 1: Với mỗi số 0,...,k n Bác chủ tịch xã chọn k người từ n người dân để đi tham quan. Hay 0k n k        cách chọn lựa chọn người dân đi tham quan. + Cách 2: Mỗi một người trong xã sẽ có hai cơ hội là được đi tham quan hoặc không được đi tham quan nên mỗi người sẽ có hai sự lựa chọn. Theo quy tắc nhân, cứ n người trong xã sẽ có hai sự lựa chọn hay 2n (cách) Hay bác chủ tịch xã có 2n (cách) lựa chọn số người đi tham quan. Vậy chúng tôi đã giải bài toán đặt ra theo hai cách. 0 2n k n k        Thang Long University Libraty 28 2.1.5. Đồng nhất thức 5:  1 0 2 , 1 2 n k n n k           Để chứng minh đồng nhất thức 5, chúng tôi sử dụng phương pháp song ánh, tức là nếu tồn tại một song ánh từ A vào B thì A B . a. Câu hỏi: Trong màn đồng diễn chào mừng 60 năm giải phóng Hải Phòng. Thầy Hiệu trưởng nhờ biên đạo múa dàn dựng một tiết mục múa thật hay. Người biên đạo múa muốn chọn ra số bạn tham gia màn đồng diễn là một số chẵn từ một trường có n học sinh. Người biên đạo đó có bao nhiêu sự lựa chọn để lập ra nhóm múa? b. Trả lời: + Cách 1: 0 2k n k        cách lựa chọn. + Cách 2: Gọi tập A gồm 2n phần tử. Ta sẽ chứng minh bằng ví dụ sau: “Số tập con có chẵn phần tử” bằng “Số tập con có lẻ phần tử” Ánh xạ f : { Tập hợp gồm chẵn phần tử}  { Tập hợp gồm lẻ phần tử}           A \ neáu A chöùa A A neáu A khoâng chöùa x x f x x Bằng chứng minh tương tự, chúng tôi có:  ( 1) ( )f B B x   f là song ánh vì              1 B neáu B kh chöùa ( ) B \ neáu B chöùa x x f B x x «ng Vậy số tập con có chẵn phần tử bằng số tập con có lẻ phần tử và bằng 12 2 2 n n , tức là có 12n cách lập ra nhóm múa. Vậy chúng tôi đã giải bài toán đặt ra theo hai cách. 29 Từ hai cách trả lời trên cho chúng tôi đồng nhất thức 5:  1 0 2 , 1 2 n k n n k           2.1.6. Đồng nhất thức 6:   1 , 0 1 n n k n k n k k               a. Câu hỏi: Trong một hội thi "Ai thông minh nhất", thầy giáo muốn chọn ra một đội thi đấu gồm k người. Có bao nhiêu cách lập ra một đội thi đấu gồm k thành viên từ một lớp có n học sinh mà trong đó chọn ra một bạn làm đội trưởng? b. Trả lời: + Cách 1: Đầu tiên, thầy chọn ra k bạn trong n bạn để thành lập đội thi đấu, thầy có n k       cách. Từ k bạn, chọn một bạn bất kỳ làm đội trưởng, thầy có: k cách lựa chọn. Từ đó, theo quy tắc nhân, thầy có: n k k       cách lựa chọn các bạn tham gia thi đấu. + Cách 2: Thầy chọn ra bạn đội trưởng trước. Thầy chọn ra một bạn từ n bạn, thầy có n cách. Sau đó, số bạn còn lại là  1n  . Thầy chọn ra  1k  bạn từ  1n  bạn còn lại. Theo quy tắc nhân, thầy có: 1 1 n n k       cách lựa chọn các bạn tham gia thi đấu. Vậy chúng ta giải bài toán đặt ra theo hai cách. Thang Long University Libraty 30 Hay chúng tôi có kết quả của đồng nhất thức 6 :             1 1 n n k n k k 2.1.7. Đồng nhất thức 7:  1 0 .2 , 1 n n k n k n n k           a. Câu hỏi: Trong kì thi tiếng hát học trò của trường A. Do ai cũng muốn tham gia nên cô chọn ra một tốp ca từ một nhóm có n học sinh, mà cô muốn trong nhóm có một bạn làm quản ca diễn xướng. Có bao nhiêu cách lập ra một tốp ca từ một nhóm có n học sinh ? b. Trả lời: + Cách 1: Với mỗi số 0,...,k n Đầu tiên, cô chọn ra k bạn từ n bạn trong lớp để lập thành tốp ca. Cô có n k       cách. Tiếp theo trong k bạn được chọn, cô chọn ra một bạn bất kì làm diễn xướng. Cô có k cách. Theo quy tắc nhân, cô có n k k       cách lựa chọn. Vậy với k từ 0 đến n, tổng cộng cô có 0 n k n k k        cách chọn. + Cách 2: Do bạn nào cũng có năng khiếu ca hát và mong muốn tham gia. Cô chọn ra bạn diễn xướng trước, cô lấy ra một bạn bất kì từ n bạn trong nhóm làm diễn xướng. Cô có ngay n cách. Số bạn còn lại của nhóm là  1n  bạn. Mà mỗi bạn còn lại sẽ có hai khả năng tham gia hoặc không tham gia, nên 1n  bạn cô có 12n cách. Theo quy tắc nhân, cô có 1.2nn  cách lựa chọn. 31 Vậy chúng ta giải bài toán đặt ra theo hai cách. 1 0 .2 n n k n k n k          2.1.8. Đồng nhất thức 8:  0 , 0 2 2 n k n n k k n n           a. Câu hỏi: Gọi X tập có n phần tử. Như vậy có n2 tập con của X. Thế nào là kích cỡ trung bình của tập con ? b. Trả lời: + Cách 1: X: Tập có n phần tử. A là tập con của X. Kích cỡ trung bình của tập con là: A 0 A 2 2 n X n n k n k k           + Cách 2: Để hiểu rõ hơn về bản chất ta làm rõ công thức sau: Ta chia tập con thành từng cặp, mỗi cặp gồm một tập con và phần bù của nó. Ta đưa ra một ví dụ bất kì để hiểu thêm về công thức trên. Ví dụ: Xét tập A {1,2,..., }n Chia tập A thành các tập con. Tập  1A 1,...,k gồm k phần tử. Tập A 2 = k+1,...,n-1,n{ } gồm  n k phần tử. ( Tập 2A : phần bù của tập 1A ) Kích cỡ trung bình của tập 1A và 2A là: 2 2 k n k n   Vậy mỗi cặp có số phân tử trung bình là 2 n Hay kích cỡ trung bình của tất cả các tập con là 2 n . Thang Long University Libraty 32 Từ hai cách trả lời trên cho chúng ta đồng nhất thức 8.  0 , 0 2 2 n k n n k k n n           2.1.9. Đồng nhất thức 9:   0 , 0, 0 k j m n m n m n k j k j                   a. Câu hỏi: Từ một lớp có  m n học sinh, bao gồm m học sinh nam và n học sinh nữ. Có bao nhiêu cách tạo ra một tổ gồm k thành viên? b. Trả lời: + Cách 1: Tất nhiên ta có m n k       cách tạo ra một tổ của lớp. + Cách 2: Với mỗi số 0,...,j k Đầu tiên thầy chọn ra j thành viên từ m bạn nam trước. Ta có: m j       cách. Tiếp theo chọn ra  k j số thành viên còn lại từ n học sinh nữ. Thầy có n k j       cách. Theo quy tắc nhân, thầy có            0 k j m n j k j cách lựa chọn số thành viên. Vậy chúng ta giải bài toán đặt ra theo hai cách. 0 . k j m n m n k j k j                    33 2.2. CÁC ĐỒNG NHẤT THỨC NÂNG CAO: Giải tích tổ hợp không chỉ giải quyết các bài toán được đặt ra trong đại số tổ hợp mà còn nhiều ứng dụng thú vị trong các ngành toán học khác. Ví dụ trong đại số, số học, hình học tổ hợp, lý thuyết xác suất Các hệ số nhị thức thường được nảy sinh một cách tự nhiên trong số học modular, trong đại số giao hoán, trong lý thuyết modular, vì vậy những đẳng thức liên quan đến hệ số nhị thức đóng một vai trò đặc biệt quan trọng. Dưới đây chúng tôi xin trình bày một số ví dụ về chứng minh đồng nhất thức theo phương pháp đếm. Nội dung phần 2.2, chúng tôi viết dựa theo một số tài liệu tham khảo sau: 1. Nguyễn Hữu Anh, Toán rời rạc, NXB Đại học Quốc Gia TP. Hồ Chí Minh, 2001 2. Trần Ngọc Danh, Toán rời rạc nâng cao, NXB Đại học Quốc Gia TP. Hồ Chí Minh, 2003 3. Nguyễn Khắc Minh, Tài liệu bồi dưỡng giáo viên, Hà Nội 1999 4. Tạp chí Toán học và tuổi trẻ, số 1, 2/20 2.2.1. Đồng nhất thức 10:               2 1 2 1 1k n n k n k n a. Câu hỏi: Chúng tôi đưa ra tình huống sau: Có n nhà khoa học nghiên cứu vật lý và n nhà khoa học nghiên cứu toán học cùng tham gia một hội nghị khoa học. Hỏi có bao nhiêu cách chọn ra một nhóm làm việc gồm n người, trong đó có một nhà vật lý làm nhóm trưởng? Thang Long University Libraty 34 b. Trả lời: + Cách 1: Đầu tiên chọn nhóm trưởng là nhà vật lý, có n cách chọn. Sau đó, chọn  1n  thành viên còn lại từ  2 1n  nhà vật lí và nhà toán học. Như vậy, có 2 1 1 n n       cách chọn. Theo quy tắc nhân, chúng ta có cách chọn       2 1 1 n n n nhóm nghiên cứu khoa học mà nhà vật lý làm trưởng nhóm. + Cách 2: Với mỗi số 1,...,k n Chúng tôi chọn k nhà vật lý có n k       cách chọn. Chọn nhóm trưởng là nhà vật lý, chúng tôi có k cách chọn. Tiếp theo chọn ra  n k nhà toán học, có n n k       cách chọn. Theo quy tắc nhân chúng tôi có:         2 1k n k k Vậy chúng tôi đã chứng minh đồng nhất thức 10:               2 1 2 1 1k n n k n k n 2.2.2. Đồng nhất thức 11: 0 2 1 2 2 n k k n k n n n k k n                   a. Câu hỏi: Tương tự như ví dụ 2, chúng tôi thấy vế phải là số cách chọn n phần tử từ tập X gồm 2 1n  phần tử nên xét bài toán sau: Tính số cách chọn n phần tử từ tập X gồm 2 1n  phần tử? 35 b. Trả lời: + Cách 1: Ta chọn n phần tử từ tập gồm 2n + 1 phần tử. Số cách chọn chính bằng 2 1n n       cách chọn. + Cách 2: Ta chia X thành n cặp và phần tử x. Để chọn n phần tử từ tập X ta thực hiện các bước sau: Bước 1: Ta chọn k cặp  0,k n từ n cặp đã chia, ta có n k       cách. Sau đó, mỗi cặp ta chọn một phần tử. Mỗi phần tử có 2 cách chọn, nên mỗi phần tử k có 2 cách. Ta có 2k cách chọn. Theo quy tắc nhân, ta có 2k n k æ è ç ö ø ÷ cách chọn. Bước 2: Chọn 2 n k      cặp trong  n k cặp còn lại. Vì 2 2 n k n k       nếu  n k chẵn và 1 2 2 n k n k        nếu  n k lẻ. Do đó, ta chọn x nếu  n k lẻ và không chọn x nếu  n k chẵn. Theo quy tắc nhân, chúng ta có: 0 2 2 n k k n k n n k k             cách chọn. Vậy bằng hai cách trả lời câu hỏi, chúng tôi đã chứng minh được đồng nhất thức11: 0 2 1 2 2 n k k n k n n n k k n                   Thang Long University Libraty 36 2.2.3. Đồng nhất thức 12: 1 2 1 2 1 2 ... 1 2 ... ... r r r k k k r n n n n n n k k k k                          a. Câu hỏi: Chúng tôi xây dựng tình huống sau: Thầy Thế có một khay đựng bút chì màu, các cây bút hình thức thì khác nhau nhưng có tất cả r màu  1 2, ,..., rm m m 1n bút màu 1m 2n bút màu 2m ... ... ... rn bút màu rm Có bao nhiêu cách để thầy tặng bạn Huy k cây bút bất kì? b. Trả lời: + Cách 1: Chọn ra 1k bút màu 1m có 1 1 n k       cách. Chọn ra 2k bút màu 2m có 2 2 n k       cách. ... ... ... Tương tự, chọn ra rk bút màu rm có r r n k       cách. Các số lượng 1 2, ,..., rk k k thầy có thể chọn bất kì sao cho tổng 1 2 ... rk k k k    Như vậy, theo quy tắc nhân thầy có tất cả: 1 2 1 2 ... 1 2 ... r r k k k r n n n k k k                   cách. + Cách 2: Thầy lấy ngẫu nhiên ra k cây bút trong tổng số  1 2 ... rn n n   cây bút của thầy, dĩ nhiên sẽ có: 1 2 ... rn n n k         cách để thầy chọn. Vậy qua hai cách trả lời, ta có: 37 1 2 1 2 1 2 ... 1 2 ... ... r r r k k k r n n n n n n k k k k                          2.2.4. Đồng nhất thức 13: 2 1 2 2 2 ... 2 0 2 2 n n n n n                     a. Câu hỏi: Xét bài toán: Có 2n đồ vật, hỏi có bao nhiêu cách lấy ra một số chẵn đồ vật ? b. Trả lời: Cách 1: Ta có các trường hợp sau: + Trường hợp 1: Lấy 0 đồ vật từ 2n đồ vật có 2 0 n      cách. + Trường hợp 2: Lấy 2 đồ vật từ 2n đồ vật có 2 2 n      cách. + Trường hợp thứ 1n  . Lấy 2n đồ vật từ 2n đồ vật, có 2n 2n æ è ç ö ø ÷ cách. Vậy áp dụng quy tắc cộng, ta có: 2 2 2 ... 0 2 2 n n n n                     cách. Cách 2: Mỗi hành động lấy một đồ vật, có hai sự lựa chọn là lấy (L) hoặc không lấy (K). Ta có: 2n hành động thì có 22 n cách lấy. Nhưng vì muốn lấy được một số chẵn đồ vật, mỗi lần chọn (L) (hoặc (K)) một đồ vật ta phải chọn (L) hoặc (K) thêm 1 đồ vật khác. Như vậy, mỗi cách lấy đã được đếm 2 lần. Do đó, số cách lấy là: 2 2 12 2 2 n n Thang Long University Libraty 38 Từ hai cách trả lời trên cho chúng ta kết quả: 2 1 2 2 2 ... 2 0 2 2 n n n n n                     Vậy ta đã chứng minh được đồng nhất thức 13 bằng phương pháp đếm. 2.2.5. Đồng nhất thức 14: 12 3 ... .2 1 2 3 n n n n n n n n                            a. Câu hỏi: Ta biết, n chính là số cách lấy một phần tử từ một tập gồm n phần tử. 2 12 n là số tập con của tập gồm  1n  phần tử. Xét tập  1 2X ; ;...; nx x x Hãy đếm số cặp  , Aa trong đó Xa và A là một tập con của tập X-1 =X/ a{ }. b. Trả lời: Cách 1: Ta có: n cách chọn a , với mỗi cách chọn a . ta có: 12n cách chọn A. Theo quy tắc nhân ta có: 1.2nn  cặp  ,Aa . Cách 2: A là một tập con gồm k phần tử của tập gồm n phần tử  0, 1k n  nên n n k n k             cách chọn A. Một cách chọn tập A, chọn \a X A nên có  n k cách chọn a . Khi k chạy từ 0 đến  1n  . Theo quy tắc cộng, ta có:   0 ... 1 2 n k n k n n n n k n n n                              cặp  ,Aa . Vậy từ hai cách trả lời trên cho ta kết quả. 39 2.2.6. Đồng nhất thức 15: 0 2 k k i n n i n k k i k                 a. Câu hỏi: Ta đã biết, 2k là số tập con của một tập gồm k phần tử. n k       là số tập con gồm k phần tử của tập gồm n phần tử. Xét tập  1 2X ; ;...; nx x x Hãy đếm số cặp (A, M) trong đó A là một tập con gồm k phần tử của X. M là một tập con của A. b. Trả lời: Cách 1: Vì tập A có k phần tử nên n k       cách chọn tập A. Mỗi cách chọn A ta có 2k cách chọn M. Theo quy tắc nhân, ta có: 2k n k       cặp (A, M) Cách 2: Ta có: n k       cách chọn M  0 i k  Sau khi chọn M, ta chọn  k i phần tử từ  n i phần tử còn lại ta có: n i k i       cách chọn . Theo quy tắc nhân, ta có: n n i k k i          cách chọn. Với 0i  đến k, lấy tổng các cặp (A, M) là 0 k i n n i k k i           Vậy từ hai cách trả lời trên cho chúng ta kết quả: Thang Long University Libraty 40 0 2 k k i n n i n k k i k                 Chúng ta đã chứng minh được đồng nhất thức 15. 41 KẾT LUẬN Luận văn đã trình bày một cách có hệ thống tổng quan về tính chất hệ số nhị thức. Trong chương một, chúng tôi đã giới thiệu khái quát các đồng nhất thức cơ bản, kỹ thuật đếm và một số nguyên lý cơ bản. Đặc biệt ở chương hai chúng tôi đã đi nghiên cứu, chứng minh chi tiết các đồng nhất nhất thức bằng phương pháp đếm số phần tử của một tập hợp bằng hai cách. Trên cơ sở đó, để chứng minh các đồng nhất thức bằng cách xây dựng các tình huống sao cho học sinh để tiếp thu và tạo hứng thú với môn học. Ở chương hai, chúng tôi còn nghiên cứu các đồng nhất thức nâng cao, cùng dựa trên phương pháp đếm số phần tử. Cuối chương, chúng tôi còn đưa ra một số đồng nhất thức nâng cao nhằm sử dụng phương pháp ở chương hai, cho học sinh hiểu thêm về một cách mới chứng minh các đồng nhất thức. Kết quả của luận văn nhằm nâng cao chất lượng dạy và học toán tổ hợp xác suất, nhằm phát triển tư duy toán học cho học sinh lứa tuổi trung học cơ sở và đặc biệt tạo tiền đề cho các em yêu thích, tìm hiểu chuyên sâu về toán tổ hợp, được gọi là môn học khó ở cấp này. Cuối cùng chúng tôi xin được nêu một số vấn đề có thể mở rộng nghiên cứu tiếp theo trong tương lai, đó là: - Các đồng nhất thức đan dấu. - Ứng dụng của hệ số nhị thức trong giải một số bài toán thi đại học cũng như thi Olympic quốc gia và cấp quốc tế. Hay giải các bài toán liên quan đến độ phức tạp của các thuật toán cũng như giải các bài toán trong lĩnh vực tin học. - Ứng dụng của nguyên lý bao hàm và loại trừ trong cuộc sống, hay trong giải các bài toán phức tạp và các bài toán liên quan đến lĩnh vực tin học. Thang Long University Libraty 42 TÀI LIỆU THAM KHẢO 1. Nguyễn Hữu Anh, Toán rời rạc, NXB Đại học Quốc Gia TP. Hồ Chí Minh, 2001 2. Trần Ngọc Danh, Toán rời rạc nâng cao, NXB Đại học Quốc Gia TP. Hồ Chí Minh, 2003 3. Nguyễn Khắc Minh, Tài liệu bồi dưỡng giáo viên, Hà Nội 1999 4. Tạp chí Toán học và tuổi trẻ, số 1, 2/2001 5. Schaum's Outline of Discrete Mathematics, McGraw - Hill, 1977 6. Benjamin Arthur T., and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof. No. 27. MAA, 2003. LỜI CẢM ƠN Trong thời gian học tập và nghiên cứu tại trường được sự quan tâm giúp đỡ của Khoa Toán - Tin, phòng Sau đại học và Quản lý khoa học, Trường Đại học Thăng Long, và đặc biệt là sự hướng dẫn của thầy giáo PGS.TS Vũ Thế Khôi để tôi có thể tiến hành nghiên cứu đề tài “Một số tính chất của hệ số nhị thức”. Đến nay chúng tôi đã hoàn thành đề tài. Để hoàn thành luận văn này, ngoài sự nỗ lực của bản thân, tôi còn nhận được rất nhiều sự giúp đỡ, đóng góp ý kiến của nhiều cá nhân và tập thể. Tôi xin bày tỏ lòng biết ơn sâu sắc đến: Quý thầy cô giáo trong Khoa Toán - Tin, phòng Sau đại học và Quản lý khoa học, Trường Đại học Thăng Long đã tận tình giảng dạy trang bị kiến thức cho tôi trong suốt quá trình học tập tại ngôi trường này. Đặc biệt, tôi xin gửi lời cảm ơn chân thành nhất tới Thầy PGS.TS Vũ Thế Khôi - người Thầy đã trực tiếp giảng dạy, hướng dẫn, động viên và giúp đỡ tôi hoàn thành luận văn này. Bên cạnh đó, tôi không thể không nhắc đến sự động viên, giúp đỡ từ tập thể lớp Cao học Toán Thăng Long khóa 1. Ở đây, chúng tôi sống và giúp đỡ nhau như một gia đình. Và cuối cùng, người tôi muốn cảm ơn nhất là gia đình và những người thân của tôi, và một người đặc biệt ??? sao tôi lại gọi là đặc biệt vì người đó đã theo tôi từ đầu đến suốt quá trình học tập - con trai - tình yêu nhỏ bé của tôi luôn ngoan ngoãn ở nhà để cho tôi có thể hoàn thành luận văn. Mặc dù hết sức nỗ lực và cố gắng, nhưng do kiến thức và kinh nghiệm còn hạn chế nên đề tài không tránh khỏi những sai sót, rất mong được sự chỉ đạo để luận văn của tôi có thể được hoàn thiện hơn nữa. Hải Phòng, tháng 7, năm 2015 TÁC GIẢ LUẬN VĂN Nguyễn Thị Thu Giang Thang Long University Libraty