- TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN. - MỘT SỐ DẠNG TOÁN TỔ HỢP. - Chuyên ngành: Phương pháp toán sơ cấp Mã số . - Một số kiến thức cơ bản. - Một số quy tắc cơ bản của phép đếm. - Nguyên lý Dirichlet. - Tổ hợp. - Một số cách tiếp cận tới bài toán tổ hợp. - Sử dụng phương pháp liệt kê. - Đếm các phần tử của phần bù. - Sử dụng nguyên lý bao gồm và loại trừ. - Sử dụng cách xây dựng phần tử đếm. - Sử dụng các công thức tổ hợp. - Sử dụng nguyên lý phân phối các đồ vật vào hộp. - Sử dụng công thức truy hồi. - Sử dụng phương pháp đánh số. - Phương pháp xây dựng song ánh. - Sử dụng phương pháp đếm bằng hai cách. - Kỹ năng giải toán bằng phương pháp bất biến. - Một số bài toán mở đầu. - Nguyên lý bất biến. - Một số bài tập vận dụng. - Toán tổ hợp – là một ngành toán học nghiên cứu các tổ hợp, hoán vị của các phần tử. - Trong một thời gian dài, mảng khoa học này nằm ngoài hướng phát triển cơ bản của toán học và các ứng dụng của nó. - Nhờ chúng người ta có thể thực hiện việc sắp xếp, phân loại mà trước đây cần hàng trăm đến hàng ngàn năm. - Ở thời buổi sơ khai của toán học rời rạc, vai trò của lĩnh vực cổ xưa nhất của toán học rời rạc là toán học tổ hợp cũng đã được thay đổi. - Từ lĩnh vực mà phần lớn chỉ những người biên soạn những bài toán thú vị quan tâm đến và phát hiện ra những ứng dụng cơ bản trong việc mã hóa và giải mã các văn tự cổ, nó đã được chuyển thành lĩnh vực nằm trong trục đường chính của sự phát triển khoa học.. - Trước hết cần khẳng định rằng hướng này của Bộ Giáo dục và Đào tạo đòi hỏi phát triển các kiểu tư duy chuyên biệt về tổ hợp và xác suất thống kê, vốn rất cần thiết đối với thế hệ hiện tại.. - Bởi thế, trong nhiều kì thi tuyển sinh vào đại học, thi học sinh giỏi, các bài toán tổ hợp cũng hay được đề cập và thường thuộc loại rất khó. - Bằng cái nhìn tổng quan, luận văn này cũng đã nêu ra một số ví dụ điển hình trong các kì thi tuyển sinh vào đại học, thi học sinh giỏi thời gian qua. - Một số kiến thức cơ bản.. - Chương này trình bày các kiến thức cơ bản trong tổ hợp gồm: Các quy tắc đếm cơ bản, hoán vị, chỉnh hợp, tổ hợp và nhị thức Newton. - Ngoài ra, nguyên lý Dirichlet được đề cập tới như một công cụ đắc lực trong việc giải quyết các bài toán tổ hợp ở chương sau.. - Một số cách tiếp cận tới bài toán tổ hợp.. - Chương này ta sẽ tiếp cận tới bài toán tổ hợp nhờ một số phương pháp cơ bản như: Phương pháp liệt kê, phương pháp đếm các phần tử của phần bù, sử dụng nguyên lý bao gồm và loại trừ, sử dụng các công thức tổ hợp, sử dụng nguyên lý phân phối các đồ vật vào hộp, sử dụng công thức truy hồi, phương pháp đánh số, phương pháp xây dựng song ánh và phương pháp đếm bằng hai cách.. - Kỹ năng giải toán bằng phương pháp bất biến.. - Chương này trình bày ba bài toán gồm: Bài toán về tính chất hữu hạn hoặc vô hạn của dãy lặp, bài toán về tính chất tuần hoàn của dãy lặp, bài toán về sự tồn tại của dãy lặp mà trạng thái cuối cùng thỏa mãn một số tính chất cho trước. - Cuối cùng, trình bày nguyên lý bất biến và một số bài tập vận dụng.. - Tuy nhiên, trong các kì thi đại học và thi học sinh giỏi, bài toán đếm đã gây ra không ít khó khăn cho các thí sinh.. - Trong mục này, chúng ta sẽ trình bày các quy tắc đếm cơ bản, nhờ đó có thể tính chính xác và nhanh chóng số phần tử của một tập hợp mà không cần đếm trực tiếp bằng cách liệt kệ.. - Quy tắc cộng. - A k là các tập hợp hữu hạn đôi một rời nhau, tức là. - với A i là số phần tử của tập hợp A i i. - Quy tắc nhân. - A k là các tập hợp hữu hạn và A 1 A 2. - Quy tắc cộng và quy tắc nhân cũng thường được phát biểu dưới dạng tương ứng dưới đây:. - Quy tắc cộng: Giả sử một công việc nào đó có thể thực hiện theo một trong k phương án A A 1 , 2. - Phương án A i có n i cách thực hiện i 1, 2, 3. - Khi đó công việc có thể thực hiện theo n 1 n 2. - Quy tắc nhân: Giả sử một công việc nào đó bao gồm k công đoạn A A 1 , 2. - Nếu công đoạn A 1 có thể làm theo n 1 cách. - A i 1 thì công đoạn A i có thể thực hiện theo n i cách. - Khi đó công việc có thể thực hiện theo n n 1 . - Quy tắc bù trừ. - Khi đó, ta có A X A . - Số phần tử của hợp hai hoặc ba tập hợp hữu hạn bất kì. - (Công thức tính số phần tử của hợp hai tập hợp bất kì) Cho A và B là hai tập hợp hữu hạn bất kì. - Khi đó, ta có. - Ta có B và A B \ là hai tập hợp không giao nhau và A B. - là hai tập hợp không giao nhau và. - là ba tập hợp hữu hạn bất kì. - Theo định lí 1.1.1 ta có. - Ví dụ áp dụng một số quy tắc đếm cơ bản. - Từ ba chữ số 2, 3, 4 có thể tạo ra bao nhiêu số tự nhiên gồm năm chữ số, trong đó có đủ cả ba chữ số nói trên?. - Bởi số tạo thành phải có đủ cả ba chữ số 2, 3, 4 nên ta xét các trường hợp sau:. - Trường hợp 1: Số tạo thành gồm ba chữ số 2, một chữ số 3 và một chữ số 4. - Ta xếp chữ số 4 có 5 cách chọn một trong các ví trí a a a a 1. - Xếp chữ số 3 vào một trong bốn vị trí còn lại có 4 cách. - Ba vị trí còn lại xếp ba chữ số 2 có 1 cách. - Theo quy tắc nhân, ta có số.. - Trường hợp 2: Số tạo thành gồm ba chữ số 4, một chữ số 2 và một chữ số 3.. - Tương tự trường hợp 1 có 20 số.. - Trường hợp 3: Số tạo thành gồm ba chữ số 3, một chữ số 2 và một chữ số 4. - Tương tự, ta có 20 số.. - Trường hợp 4: Số tạo thành gồm hai chữ số 2, hai chữ số 3 và một chữ số 4.. - Chọn một trong năm vị trí để xếp chữ số 4 có 5 cách. - Lấy ra hai vị trí từ bốn vị trí còn lại và xếp hai chữ số 2 có 6 cách. - Hai chữ số 3 xếp vào hai vị trí còn lại có 1 cách. - Trường hợp 5: Số tạo thành gồm hai chữ số 2, hai chữ số 4 và một chữ số 3.. - Tương tự trường hợp 4 có 30 số.. - Trường hợp 6: Số tạo thành gồm hai chữ số 3, hai chữ số 4 và một chữ số 2.. - Tương tự, ta có 30 số.. - Vậy theo quy tắc cộng có tất cả số.. - Hỏi có bao nhiêu cách xếp chỗ ngồi trong các trường hợp sau:. - (i) Theo yêu cầu của bài toán, ta có số cách chọn như sau:. - ngồi Theo quy tắc nhân, ta có cách.. - (ii) Theo yêu cầu của bài toán, ta có số cách chọn như sau:. - Xét tập hợp X. - Trần Nam Dũng, Vũ Đình Hòa, Nguyễn Văn Mậu, Đặng Huy Ruận, Đặng Hùng Thắng (2008), Chuyên đề chọn lọc Tổ hợp và Toán rời rạc, NXB Giáo Dục, Việt Nam.