Tài liệu Giải và khai thác một số bài toán đếm

TRƯỜNG ĐẠI HỌC HÙNG VƯƠNG KHOA TOÁN TIN ----------------------- NGUYỄN THỊ NGỌC HUYỀN GIẢI VÀ KHAI THÁC MỘT SỐ BÀI TOÁN ĐẾM KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Ngành: Sư phạm Toán Phú Thọ, 2018 TRƯỜNG ĐẠI HỌC HÙNG VƯƠNG KHOA TOÁN TIN ----------------------- NGUYỄN THỊ NGỌC HUYỀN GIẢI VÀ KHAI THÁC MỘT SỐ BÀI TOÁN ĐẾM KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Ngành: Sư phạm Toán NGƯỜI HƯỚNG DẪN: ThS. Nguyễn Huyền Trang Phú Thọ, 2018 i LỜI CẢM ƠN Trong suốt thời gian thực hiện khóa luận tốt nghiệp, ngoài sự nỗ lực của bản thân, tôi còn nhận được sự giúp đỡ nhiệt tình của các thầy, cô giáo trong khoa Toán – Tin Trường Đại học Hùng Vương. Đặc biệt, tôi xin bày tỏ lòng viết ơn sâu sắc tới cô giáo Thạc sĩ Nguyễn Huyền Trang – Giảng viên khoa Toán – Tin. Cô đã dành nhiều thời gian quý báu để tận tình hướng dẫn, chỉ đạo tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp, đồng thời cô giáo còn là người giúp tôi lĩnh hội và nắm vững được nhiều kiến thức chuyên môn cũng như rèn luyện cho tôi tác phong nghiên cứu khoa học. Mặc dù đã rất cố gắng xong khóa luận không khỏi có những thiếu xót. Vì vậy, tôi rất mong được sự góp ý từ các thầy giáo, cô giáo và các bạn để khóa luận được hoàn thiện hơn. Tôi xin chân thành cảm ơn! Việt Trì, ngày…….tháng….. năm…… Sinh viên Nguyễn Thị Ngọc Huyền ii MỤC LỤC LỜI CẢM ƠN .................................................................................................... i MỞ ĐẦU ........................................................................................................... 1 1. Lý do chọn đề tài khóa luận .......................................................................... 1 2. Mục tiêu khóa luận ........................................................................................ 2 3. Ý nghĩa khoa học và thực tiễn....................................................................... 3 CHƯƠNG 1: KIẾN THỨC CƠ SỞ .................................................................. 4 1.1. Sơ lược về các bước giải và khai thác một bài toán................................... 4 1.1.1. Tìm hiểu sơ bộ đề toán ............................................................................ 4 1.1.2. Khai thác đề toán ..................................................................................... 4 1.1.3. Tìm tòi lời giải......................................................................................... 5 1.1.3b. Phân tích bài toán để đưa về những bài toán đơn giản hơn. ................. 5 1.1.3c. Liên hệ và sử dụng các bài toán đã giải ................................................ 5 1.1.3d. Mò mẫm, dự đoán ................................................................................. 6 1.1.3e. Bản gợi ý của Pôlya ............................................................................... 6 1.1.4. Trình bày lời giải ..................................................................................... 7 1.1.5. Khai thác một số bài toán ........................................................................ 7 1.2. Một số kiến thức về tập hợp ....................................................................... 8 1.3. Quy tắc cộng và quy tắc nhân .................................................................... 9 1.3.1. Quy tắc cộng ........................................................................................... 9 1.3.2. Quy tắc nhân ......................................................................................... 10 1.4. Giai thừa và hoán vị ................................................................................. 11 1.4.1. Giai thừa ................................................................................................ 11 1.4.2. Hoán vị .................................................................................................. 11 1.5. Chỉnh hợp, tổ hợp ..................................................................................... 11 1.5.1. Chỉnh hợp .............................................................................................. 11 1.5.2. Tổ hợp ................................................................................................... 12 1.6. Chỉnh hợp lặp, hoán vị lặp, tổ hợp lặp ..................................................... 12 1.6.1. Chỉnh hợp lặp ........................................................................................ 12 1.6.2. Hoán vị lặp ............................................................................................ 12 1.6.3. Tổ hợp lặp ............................................................................................. 13 iii KẾT LUẬN CHƯƠNG 1................................................................................ 14 CHƯƠNG 2: GIẢI VÀ KHAI THÁC MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN ......................................................................................................................... 15 2.1. Một số bài toán đếm không lặp ................................................................ 15 2.1.1. Bài toán lập số ....................................................................................... 15 2.1.2. Bài toán chọn vật, chọn người, sắp xếp ................................................ 32 2.2. Một số bài toán đếm có lặp ...................................................................... 41 2.2.1. Bài toán lập số ....................................................................................... 41 2.2.2. Bài toán đếm sử dụng tổ hợp lặp .......................................................... 46 2.2.3. Bài toán đếm sử dụng chỉnh hợp lặp ..................................................... 47 2.2.4. Bài toán đếm sử dụng hoán vị lặp ......................................................... 48 2.3. Bài toán phân bổ các đồ vật vào trong hộp .............................................. 49 KẾT LUẬN CHƯƠNG 2................................................................................ 51 CHƯƠNG 3: GIẢI VÀ KHAI THÁC MỘT SỐ BÀI TOÁN TỔ HỢP SỬ DỤNG PHÉP ĐẾM NÂNG CAO .................................................................. 52 3.1. Một số bài toán sử dụng nguyên lý trừ bù ............................................... 52 3.1.1. Nguyên lý bù trừ ................................................................................... 52 3.1.2. Các bài toán giải bằng phương pháp bù trừ .......................................... 53 3.2. Một số bài toán giải bằng phương pháp song ánh ................................... 57 3.2.1. Phương pháp song ánh .......................................................................... 57 3.2.2. Các bài toán giải bằng phương pháp song ánh ..................................... 57 3.3. Một số bài toán giải bằng phương pháp hàm sinh ................................... 61 3.3.1. Bài toán chọn các phần tử riêng biệt ..................................................... 61 3.3.2. Bài toán chọn các phần tử có lặp .......................................................... 62 3.4. Một số bài toán giải bằng phương pháp hệ thức truy hồi ........................ 64 3.4.1. Khái niệm mở đầu và mô hình hóa bằng hệ thức truy hồi .................... 64 3.4.2. Các bài toán giải bằng hệ thức truy hồi ................................................ 64 KẾT LUẬN CHƯƠNG 3................................................................................ 70 KẾT LUẬN ..................................................................................................... 71 TÀI LIỆU THAM KHẢO ............................................................................... 72 1 MỞ ĐẦU 1. Lý do chọn đề tài khóa luận Có thể nói tư duy về tổ hợp ra đời từ rất sớm. Vào thời nhà Chu, người ta đã biết đến các hình vẽ có liên quan đến những hình vuông thần bí. Thời Hi Lạp, nhà triết học Kxenokrat sống ở thế kỷ IV trước công nguyên đã biết tính số các từ khác nhau từ một bảng chữ cái cho trước. Nhà toán học Pitago và các học trò của ông đã tìm ra nhiều con số có tính chất đặc biệt. Việc tìm ra được các số như vậy đòi hỏi phải có một nghệ thuật tổ hợp nhất định. Lý thuyết tổ hợp được hình thành cùng với hàng loạt các công trình nghiên cứu nghiêm túc của các nhà toán học xuất sắc như: Pascal, Euler, Leibnitz, Fermat,…Mặc dù vậy, trong suốt hơn hai thế kỷ, tổ hợp không có vai trò nhiều trong việc nghiên cứu tự nhiên. Đến nay, với sự hỗ trợ đắc lực của máy tính, tổ hợp đã chuyển sang lĩnh vực toán ứng dụng với sự phát triển mạnh mẽ, có nhiều kết quả hữu ích cho con người. Mặc dù được nghiên cứu từ khá sớm và không được chú ý nhiều nhưng toán tổ hợp ngày càng được quan tâm nhờ có vị trí đặc biệt cũng như vai trò quan trọng của nó trong nội bộ toán học, nó không chỉ là đối tượng để nghiên cứu mà còn là công cụ đắc lực của các mô hình rời rạc của giải tích, đại số,…và trong các ngành khoa học khác. Kết quả quan trọng của nó đánh dấu bởi bài toán đếm số phân hoạch của Leonhard Euler. Trong Toán học những kết quả của nó đóng vai trò kiến thức nền tảng của giải tích, xác suất, thống kê, hình học,… Một trong những vấn đề đầu tiên của việc nghiên cứu tổ hợp là đếm xem có bao nhiêu cấu hình được tạo ra với các quy tắc đã nêu? Để đếm được chính xác, ta phải phân biệt được các cấu hình dựa vào các quy luật xây dựng chúng. Vì thế có thể xem bài toán đếm là những bài toán luyện tập đầu tiên để con người làm quen với tư duy tổ hợp, điều này giải thích vì sao một số bài toán đếm đã được đưa vào phổ thông từ rất sớm. 2 Bài toán đếm rất phong phú và đa dạng. Độ khó của bài toán đếm được trải rất rộng: Từ những bài toán dễ với các số liệu cụ thể, có thể kiểm chứng bằng trực giác đến những bài toán khó, với những dữ liệu đầu vào bằng chữ mà kết quả của nó được biểu diễn bằng một công thức toán học. Có những công thức được tìm ra qua một vài suy luận đơn giản nhưng cũng có những công thức mà việc tìm thấy chúng phải kéo dài đến hàng thế kỷ. Có những bài toán đếm nếu như giải bằng phương pháp trực tiếp sẽ gặp rất nhiều khó khăn, bế tắc, trong khi giải bằng phương pháp gián tiếp lại trở nên rõ ràng và đơn giản. Để giải được các bài toán đếm cần đòi hỏi học sinh phải tư duy tốt, linh hoạt, sáng tạo. Bài toán đếm giúp học sinh phát huy tốt năng lực tư duy sáng tạo để học tốt môn học khác cũng như các lĩnh vực khác trong cuộc sống. Các bài toán tổ hợp nói chung và các bài toán đếm nói riêng luôn là một nội dung quan trọng trong các đề thi Đại học và Cao đẳng ở nước ta, mặc dù ở mức độ không khó nhưng các thí sinh thường gặp khó khăn khi giải các bài toán này. Tuy nhiên các tài liệu về tổ hợp cũng như các bài toán đếm mới chỉ dừng lại ở việc giải các bài toán, mặc dù đã có sự phân loại các dạng toán một cách cụ thể và có hệ thống nhưng vẫn chưa chú trọng đến vấn đề khai thác. Việc khai thác các bài toán không chỉ giúp học sinh phát triển năng lực sáng tạo, đào sâu kiến thức mà còn tạo ra một hệ thống các dạng toán và bài tập toán phong phú và đa dạng. Nhưng trên thực tế, hầu hết các tài liệu chỉ chú trọng vào việc giải toán, còn việc khai thác các bài toán còn hạn chế. Với tất cả các lí do trên, để nâng cao khả năng giải toán và hứng thú học tập cho học sinh. Với mong muốn đưa ra hệ thống tập trung, phân loại kiến thức và khai thác một số dạng toán về tổ hợp đếm nhằm đem lại thuận lợi cho người học có thể tìm hiểu sâu sắc hơn về bài toán đếm. Vì vậy tôi chọn và nghiên cứu khóa luận “Giải và khai thác một số bài toán đếm ”. 2. Mục tiêu khóa luận - Hệ thống nội dung lí thuyết tổ hợp, phân dạng các bài toán đếm. Xây dựng hệ thống ví dụ và bài tập minh họa. 3 - Giải và khai thác một số bài toán đếm cơ bản và nâng cao. 3. Ý nghĩa khoa học và thực tiễn  Ý nghĩa khoa học Khóa luận đã hệ thống các kiến thức cơ sở, các dạng toán liên quan đến bài toán đếm, đồng thời đưa ra cách giải cho các dạng toán đó.  Ý nghĩa thực tiễn Khóa luận góp thêm tài liệu tham khảo cho các sinh viên ngành sư phạm Toán, cho giáo viên và cho các em học sinh THPT có nhu cầu tìm hiểu về bài toán đếm. 4 CHƯƠNG 1 KIẾN THỨC CƠ SỞ 1.1. Sơ lược về các bước giải và khai thác một bài toán Thông thường để giải một bài toán, cần qua nhiều công đoạn khác nhau như: Tìm hiểu sơ bộ đề bài, khai thác đề bài, tìm tòi lời giải, trình bày lời giải, đánh giá lời giải, khai thác lời giải, đề xuất các bài toán mới. Tất nhiên không phải bài toán nào cũng phải trải qua đủ các công đoạn đó, song chúng giúp ích rất nhiều cho việc giải các bài toán, và đối với các bài toán được chọn lọc điển hình thì nên phân tích kỹ theo trình tự đó để rèn luyện các thao tác tư duy. 1.1.1. Tìm hiểu sơ bộ đề toán Khi chọn bài toán, không nên chọn bài quá khó, mà cũng không nên chọn bài quá dễ. Cần trình bày bài toán sao cho tự nhiên và gợi được hứng thú cho người học. Trước hết cần đọc kỹ bài toán để thấy được toàn cảnh của bài toán, càng sáng sủa, càng rõ ràng càng hay, không vội đi vào chi tiết nhất là chi tiết rắc rối. Cần cố gắng khoanh vùng phạm vi của đề toán: Bài toán này thuộc vùng kiến thức nào? Sẽ cần có những kiến thức, kỹ năng gì? Nếu giải quyết được thì sẽ giải quyết vấn đề gì? 1.1.2. Khai thác đề toán Nếu là bài toán về tìm tòi thì cần xác định rõ đâu là ẩn? Cần phải làm gì? Đâu là các dữ kiện? Đã cho biết những gì? Mối tương quan giữa cái cần tìm, cái chưa biết (Các điều kiện ràng buộc). Nếu là bài toán chứng minh thì cần nêu rõ các giả thiết, kết luận. Nếu bài toán cần có hình vẽ thì phải vẽ hình. Nếu cần có thể sử dụng nét đậm, nét nhạt, nét đứt hoặc dùng màu trong hình vẽ. Cảm nhận trực giác trên hình vẽ có thể giúp chúng ta nắm bắt được dễ dàng hơn nội dung ghi trong đề toán. 5 1.1.3. Tìm tòi lời giải Đây là bước quan trọng trong việc giải bài toán. Không có một thuật toán tổng quát nào để giải được mọi bài toán, mà chỉ đưa ra những lời khuyên, những kinh nghiệm, chúng giúp cho việc tìm tòi lời giải được đúng hướng hơn, nhanh hơn, thuận lợi hơn và có nhiều khả năng dẫn tới thành công hơn. Tùy trường hợp cụ thể mà vận dụng các kinh nghiệm đó, càng linh hoạt càng nhuần nhuyễn thì càng dễ tới thành công. Càng giải quyết được nhiều bài toán thì chúng càng trở thành của mình, thành những kinh nghiệm sống chứ không phải là những chỉ dẫn khô khan. 1.1.3a. Nhận dạng và tập hợp kiến thức Như đã nói trong bước tìm hiểu đề toán, cần khoanh vùng bài toán, và vùng được khoanh càng hẹp càng tốt, giúp ta nhận dạng được bài toán thuộc loại nào. Khi đã nhận dạng, đã phân loại được bài toán thì trong óc phải nhanh chóng huy động và tổ chức các kiến thức đã học, đã biết từ trước; phải nhớ lại để chuẩn bị vận dụng một loạt yếu tố cần thiết để giải loại toán này. Quá trình đó có thể là “Tự phát” nhất là khi đã quen với việc giải toán. 1.1.3b. Phân tích bài toán để đưa về những bài toán đơn giản hơn. Một bài toán, nhất là bài toán tổng hợp, bài toán khó được xây dựng từ những bài toán đơn giản hơn. Cần phải xem có thể phân tích bài toán đang xét thành những bài toán đơn giản hơn không, rồi giải từng bài toán nhỏ ấy, sau đó kết hợp chúng lại để có lời giải bài toán đã cho. 1.1.3c. Liên hệ và sử dụng các bài toán đã giải Thật khó mà đặt ra một bài toán hoàn toàn mới, không giống bất kì bài toán nào, hoặc không liên quan gì với các bài toán khác. Vì thế khi gặp một bài toán, ta gắng nhớ lại xem đã gặp một bài toán tương tự hoặc gần giống với bài toán cần giải chưa, và nhớ lại con đường đi đến lời giải của bài toán đã biết. Điều đó giúp ta rút ngắn việc tìm tòi lời giải của bài toán mới này và tạo thêm rất nhiều thuận lợi. 6 Việc nhớ được một hay một số bài toán tương tự bài toán đang xét, có thể về dạng, về phương pháp, về vấn đề đặt ra,…ta đã lợi dụng được những điểm tương đồng về phương pháp giải, về kinh nghiệm, về kết quả,… 1.1.3d. Mò mẫm, dự đoán Trong khi tìm tòi lời giải cho bài toán, ta có thể thử nghiệm với một số trường hợp đặc biệt, nhiều khi sẽ cho ta những gợi ý để giải quyết trong trường hợp tổng quát. Việc này cũng là nội dung của phương pháp đặc biệt hóa, nhưng ở đây được sử dụng để gợi ý, để tìm tòi lời giải và phương pháp đi tới kết quả. 1.1.3e. Bản gợi ý của Pôlya  Bạn đã gặp bài toán này lần nào chưa? Hay đã gặp bài toán này ở dạng tương tự.  Bạn có biết một bài toán nào liên quan không? Một định lý nào có thể sử dụng ở đây được không?  Xét kĩ cái chưa biết và thử nhớ lại một bài toán quen thuộc cùng ẩn hay có ẩn tương tự.  Đây là một bài toán liên quan mà bạn đã có lần giải rồi, có thể sử dụng nó không? Có thể sử dụng kết quả, phương pháp của nó không? Có cần phải đưa thêm một số yếu tố phụ thì mới sử dụng được không?  Có thể phát biểu bài toán một cách khác không?  Nếu bạn vẫn chưa giải được bài toán đã cho thì hãy thử giải một bài toán liên quan mà dễ hơn không? Một bài toán tổng quát hơn? Một trường hợp đặc biệt? Một bài toán tương tự? Hoặc một phần của bài toán? Hãy giữ lại một số điều kiện, bỏ qua các điều kiện khác. Khi đó ẩn được xác định đến một chừng mực nào đó, nó biến đổi như thế nào? Bạn có thể từ các dữ kiện rút ra được một số yếu tố có ích không? Có thể nghĩ ra các dữ kiện khác giúp bạn xác định được ẩn không? Có thể thay đổi ẩn hoặc các dữ kiện sao cho các ẩn mới và các dữ kiện mới gần nhau hơn không?  Bạn đã sử dụng hết mọi dữ kiện chưa? Đã sử dụng hết các quan hệ 7 chưa? Đã để ý đến mọi khái niệm chủ yếu trong bài toán chưa? 1.1.4. Trình bày lời giải Khi đã tìm được lời giải rồi thì việc trình bày lời giải không còn khó khăn nữa, song tính chất hai công việc có khác nhau. Việc trình bày lời giải là văn bản để đánh giá kết quả hoạt động tìm tòi lời giải bài toán. Khi đang tìm tòi lời giải, ta có thể mò mẫm, dự đoán hoặc có thể dùng lập luận tạm thời, cảm tính. Nhưng khi trình bày lời giải thì chỉ được dùng những lý luận chặt chẽ, phải kiểm nghiệm lại từng chi tiết. Phải chú ý đến trình tự các chi tiết, đến tính chính xác của từng chi tiết, đến mối liên hệ giữa các chi tiết trong từng đoạn của lời giải và trong toàn bộ lời giải. Không có chi tiết nào bỗng dưng xuất hiện mà không căn cứ vào những kiến thức đã học hoặc những chi tiết mà ta trình bày trước đó. Khi trình bày lời giải, để cho ngắn gọn ta thường dùng những phương pháp tổng hợp. Lời giải được trình bày gọn gàng, sáng sủa, dễ đọc. 1.1.5. Khai thác một số bài toán Công việc này rất cần thiết trong học toán nhưng thường hay bị bỏ qua. Việc nhìn nhận lại toàn bộ cách giải một bài toán có thể giúp chúng ta phát hiện được cách giải khác tốt hơn, ngắn gọn hơn, hay hơn hoặc sâu sắc hơn. Việc nhìn nhận lại toàn bộ lời giải sẽ gợi ý cho ta tìm được những bài toán mới, mà bài toán vừa xét chỉ là một trường hợp đặc biệt. Công đoạn này được gọi là khai thác bài toán. Có thể khai thác một bài toán theo các hướng như sau: a) Hướng 1: Phát biểu bài toán tương tự, bài toán này có thể giải được không? b) Hướng 2: Khái quát hóa, có thể phát biểu bài toán tổng quát được không? Bài toán tổng quát có còn đúng nữa không? Trái lại với khát quát hóa là đặc biệt hóa luôn luôn đưa đến kết quả đúng, thậm chí có thể mạnh hơn. c) Hướng 3: Thay đổi giả thiết để được một bài toán mới. Phương pháp để giải một bài toán khác. d) Hướng 4: Từ ý nghĩa bài toán đã giải dẫn đến phương pháp giải một bài toán khác. 8 Ví dụ 1.1.1. Từ bài toán “ Chứng minh rằng tồn tại số có dạng: 20032003…200300…0 chia hết cho 2002”, ta có thể khai thác thành các bài toán sau: Bài toán tương tự: Có hay không một số có dạng 19911991…199100…0 chia hết cho 1990?. Bài toán tổng quát hóa: Có hay không một số có dạng: (n+1)(n+1)…(n+1)000…000 chia hết cho n. Ví dụ 1.1.2. Từ bài toán “Bên trong một cái sân hình chữ nhật có chiều dài là 4m và chiều rộng là 3m có 6 con chim đang ăn. Chứng minh rằng phải có ít nhất là 2 con chim mà khoảng cách giữa chúng nhỏ hơn 2”, ta có bài toán tương tự sau: Bài toán tương tự: “Trong hình tròn đường kính 5cm có 10 điểm. Chứng minh rằng tồn tại ít nhất hai điểm mà khoảng cách giữa chúng nhỏ hơn hoặc bằng 2”. Ví dụ 1.1.3. Từ bài toán “Chứng minh rằng tích hai số tự nhiên liên tiếp chia hết cho 2”, ta có thể khai thác thành các bài toán như sau: Bài toán tương tự 1: Chứng minh rằng tích 3 số tự nhiên liên tiếp chia hết cho 3. Bài toán tương tự 2: Chứng minh rằng tích bốn số tự nhiên liên tiếp chia hết cho 4. Bài toán đặc biệt hóa: Chứng minh rằng tích hai số chẵn liên tiếp chia hết cho 8. Bài toán tổng quát hóa: Chứng minh rằng tích của n số tự nhiên liên tiếp chia hết cho n. 1.2. Một số kiến thức về tập hợp Tập hợp con Định nghĩa 1.2.1: Cho tập hợp A , tập hợp B gọi là tập con của tập hợp A khi mọi phần tử của tập hợp B đều thuộc A . Tính chất: + Mọi tập hợp A đều có hai tập con là  và A . + Tập A có n phần tử thì số tập con của A là 2n . 9 Tập hợp sắp thứ tự Một tập hợp hữu hạn có m phần tử được gọi là sắp thứ tự nếu với mỗi phần tử của tập hợp đó ta cho tương ứng một số tự nhiên từ 1 đến m sao cho với những phần tử khác nhau ứng với những số khác nhau. Khi đó bộ sắp thứ tự m phần tử là một dãy hữu hạn m phần tử và hai bộ sắp thứ tự  a1, a2 ,..., am  và  b1, b2 ,..., bm  bằng nhau khi và chỉ khi mọi phần tử tương ứng bằng nhau, tức là:  a1, a2 ,..., am   b1, b2 ,..., bm   ai  bi , i  1, m . Số phần tử của một số tập hợp Tập hợp A có hữu hạn phần tử thì số phần tử của A được kí hiệu là: A hoặc n  A . Cho A, B, C là ba tập hữu hạn, khi đó: A B  A  B  A B . A B C  A  B  C  B C  A B  C  A  A B C . Tổng quát: Cho A1, A2 ,..., An là n tập hữu hạn  n  1 . Khi đó: n A1  A2  ...  An   Ai  i 1 n   1i  k l  n n  1i  k  n Ai  Ak  Ai  Ak  Al  ...   1 n 1  A1  ...  An  1.3. Quy tắc cộng và quy tắc nhân 1.3.1. Quy tắc cộng Định nghĩa 1.3.1: Một công việc được hoàn thành bởi một trong hai hành động. Nếu hành động này có m cách thực hiện, hành động kia có n cách thực hiện không trùng với bất kì cách nào của hành động thứ nhất thì công việc đó có m  n cách thực hiện. Quy tắc cộng dạng tổng quát: Một công việc được hoàn thành bởi một trong các hành động T1,T2 ,...,Tn . Trong đó: 10 T1 có m1 cách thực hiện. T2 có m2 cách thực hiện. … Tn có mn cách thực hiện. Giả sử không có hai việc nào có thể làm đồng thời thì công việc đó có m1  m2  ...  mn cách thực hiện. Biểu diễn dưới dạng tập hợp Nếu X ,Y là hai tập hợp hữu hạn, không giao nhau thì: X  Y  X  Y . Nếu X1, X 2 ,..., X n là n tập hữu hạn, từng đôi một không giao nhau thì: X1  X 2  ...  X n  X1  X 2  ...  X n Nếu X ,Y hai tập hữu hạn và X  Y thì: X  Y \ X  Y  X . 1.3.2. Quy tắc nhân Giả sử để hoàn thành một nhiệm vụ H cần thực hiện hai công việc nhỏ là H1 và H 2 . Trong đó: H1 có thể làm bằng n1 cách. H 2 có thể làm bằng n2 cách, sau khi đã hoàn thành công việc H1 . Khi đó để thực hiện công việc H sẽ có n1.n2 cách. Quy tắc nhân dạng tổng quát: Giả sử để hoàn thành một nhiệm vụ H cần thực hiện k công việc nhỏ là H1, H 2 ,..., H k , trong đó: H1 có thể làm bằng n1 cách. H 2 có thể làm bằng n2 cách, sau khi đã hoàn thành công việc H1 . … H k có thể làm bằng nk cách, sau khi đã hoàn thành công việc H k 1 . Khi đó để thực hiện công việc H sẽ có n1.n2 .....nk cách. 11 Biểu diễn dưới dạng tập hợp Nếu A1, A2 ,..., An là n tập hữu hạn  n  1 , khi đó số phần tử của tích đề các các tập hợp này bằng tích của số các phần tử mọi tập thành phần. Để liên hệ với quy tắc nhân hãy nhớ là việc chọn một phần tử của tích đề các A1  A2  ...  An được tiến hành bằng cách chọn lần lượt một phần tử của A1 , một phần tử của A2 ,…, một phần tử của An . Theo quy tắc nhân ta nhận được đẳng thức: A1  A2  ...  An  A1 . A2 ..... An . 1.4. Giai thừa và hoán vị 1.4.1. Giai thừa Định nghĩa 1.4.1: Giai thừa n , kí hiệu là n! là tích của n số tự nhiên liên tiếp từ 1 đến n . n!  1.2.3..... n  1.n, n  1 Quy ước: 0!  1 . 1!  1. 1.4.2. Hoán vị Định nghĩa 1.4.2: Cho tập hợp A gồm n phần tử  n  1 . Một cách sắp thứ tự n phần tử của tập hợp A được gọi là một hoán vị của n phần tử đó. Kí hiệu: Pn là số các hoán vị của n phần tử. Pn  n!  1.2..... n  1.n 1.5. Chỉnh hợp, tổ hợp 1.5.1. Chỉnh hợp Định nghĩa 1.5.1: Cho tập hợp A gồm n phần tử  n  1 . Kết quả của việc lấy k phần tử khác nhau từ n phần tử của tập hợp A và sắp xếp chúng theo một thứ tự nào đó được gọi là một chỉnh hợp chập k của n phần tử. Công thức: Ank  n!  n. n  1..... n  k  1  n  k ! với 1  k  n . Chú ý: Một chỉnh hợp n chập n được gọi là một hoán vị của n phần tử. Ann  Pn  n! 12 1.5.2. Tổ hợp Định nghĩa 1.5.2: Giả sử tập hợp A gồm n phần tử  n  1 . Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử đã cho với 1 k  n. Kí hiệu: Cnk , 1  k  n  là số tổ hợp chập k của n phần tử. Công thức: Cnk  n! . k ! n  k ! Chú ý: Cn0  1. Cnk  Cnnk ,  0  k  n  . Cnk  Cnk 1  Cnk11 , 1  k  n  . 1.6. Chỉnh hợp lặp, hoán vị lặp, tổ hợp lặp 1.6.1. Chỉnh hợp lặp Định nghĩa 1.6.1: Một cách sắp xếp có thứ tự r phần tử có thể lặp lại của một tập n phần tử được gọi là một chỉnh hợp lặp chập r từ tập n phần tử. Nếu A là tập gồm n phần tử đó thì mỗi chỉnh hợp như thế là một phần tử của tập A. Ngoài ra, mỗi chỉnh hợp lặp chập r từ tập n phần tử là một hàm từ tập r phần tử vào tập n phần tử. Vì vậy, số chỉnh hợp lặp chập r từ tập n phần tử là n k . 1.6.2. Hoán vị lặp Trong bài toán đếm, một số phần tử có thể giống nhau. Khi đó cần phải cẩn thận, tránh đếm chúng hơn một lần. Định lý 1.6.1: Số hoán vị của n phần tử trong đó có n1 phần tử như nhau thuộc loại 1, có n2 phần tử như nhau thuộc loại 2,…và có nk phần tử như nhau thuộc loại k bằng n! . n1 !n 2!..nk ! Chứng minh Để xác định số hoán vị trước tiên chúng ta nhận thấy có Cnn1 cách giữ n1 số cho n1 phần tử loại 1, còn lại n  n1 chỗ trống. 13 Sau đó có Cnn2 n1 cách đặt n2 phần tử loại 2 vòa hoán vị, còn lại n  n1  n2 chỗ trống. Tiếp tục đặt các phần tử loại 3, loại 4,…,loại k  1 vào chỗ trống trong hoán vị. Cuối cùng có Cnnk n1 n2 ...n k 1 cách đặt nk phần tử loại k vào hoán vị. Theo quy tắc nhân tất cả các hoán vị có thể là: Cnnk n1 n2 ...n k 1  n! . n1 !n 2!..nk ! 1.6.3. Tổ hợp lặp Một tổ hợp lặp chập k của một tập hợp là một cách chọn không có thứ tự k phần tử có thể lặp lại của tập đã cho. Như vậy một tổ hợp lặp kiểu này là một dãy không kể thứ tự gồm k thành phần lấy từ tập n phần tử. Do đó có thể là k  n . Định lý 1.6.2: Số tổ hợp lặp chập k từ tập n phần tử bằng Cnkk 1 . Chứng minh Mỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng một dãy n  1 thanh đứng và k ngôi sao. Ta dùng n  1 thanh đứng để phân cách các ngăn. Ngăn thứ i chứa thêm một ngôi sao mỗi lần khi phần tử thứ i của tập xuất hiện trong tổ hợp. Mỗi dãy n  1 thanh và k ngôi sao ứng với một tổ hợp lặp chập k của n phần tử. Do đó mỗi dãy ứng với một cách chọn k chỗ cho k ngôi sao từ n  k  1 chỗ chứa n  1 thanh và k ngôi sao. Đó là điều cần chứng minh. Chú ý: + Số tổ hợp có lặp chập p của n là Cnp  Cnp p1  Cnn1p1 . + Tổ hợp có lặp lại khi một phần tử có thể xuất hiện nhiều lần và thứ tự của các phần tử không cần để ý. 14 KẾT LUẬN CHƯƠNG 1 Trong chương 1, khóa luận trình bày hệ thống lý thuyết về tổ hợp đếm và các ví dụ về khai thác bài toán để làm cơ sở áp dụng vào làm bài tập của chương 2 và chương 3. 15 CHƯƠNG 2 GIẢI VÀ KHAI THÁC MỘT SỐ BÀI TOÁN ĐẾM CƠ BẢN 2.1. Một số bài toán đếm không lặp Trong các bài toán về phép đếm không lặp, mỗi phần tử cần đếm chỉ có thể xuất hiện tối đa một lần. Để giải các bài toán đếm không lặp người ta sử dụng hai quy tắc chính của phép đếm là quy tắc cộng và quy tắc nhân, cũng như sử dụng hai phương pháp đếm trực tiếp hoặc đếm gián tiếp. 2.1.1. Bài toán lập số Thông thường để lập được số n  a1a2 ...ar  a1  0  từ các số cho trước: +) Ta dùng phép chỉnh hợp – hoán vị. +) Nếu trong quá trình sắp xếp, nếu có các chữ số hoặc các số có điều kiện thì ta chọn trước và các chữ số có tính chất bình đẳng thì chọn sau. +) Sau đó vận dụng quy tắc nhân – quy tắc cộng trong phép đếm để có hiệu quả. Bài toán 2.1.1: Cho tập X  0,1,2,3,4,5,6 . Có thể lập được bao nhiêu số gồm năm chữ số mà các chữ số khác nhau từng đôi một.  Phân tích bài toán Theo yêu cầu bài toán số cần tìm có các chữ số khác nhau nên ta sử dụng kiến thức chỉnh hợp để giải bài toán này. Giải Gọi số thành lập là: n  a1a2a3a4a5 , ai  X .  Cách 1 - Chọn a1  0 , có 6 cách chọn. - Còn a2 , a3 , a4 , a5 là một bộ phân biệt có thứ tự được chọn từ X do đó nó là một chỉnh hợp chập 4 của 6 (Trừ đi số a1 đã chọn). Có A64 cách chọn. Vậy số các số thỏa mãn yêu cầu bài toán là: 6. A64 =2160 số.  Cách 2 - Chọn a1  0 , có 6 cách chọn.