Một số bài toán tổ hợp đếm

- MỘT SỐ BÀI TOÁN TỔ HỢP ĐẾM.
- CHƯƠNG 1 - CƠ SỞ LÍ THUYẾT VỀ TỔ HỢP.
- 1.1 Nhắc lại về tập hợp.
- 1.3 Giai thừa và hoán vị.
- 1.4 Chỉnh hợp, tổ hợp.
- 1.5 Chỉnh hợp lặp, hoán vị lặp và tổ hợp lặp.
- 1.5.1 Chỉnh hợp lặp.
- 1.5.2 Hoán vị lặp.
- 7 1.5.3 Tổ hợp lặp.
- CHƯƠNG 2 - MỘT SỐ BÀI TOÁN TỔ HỢP CƠ BẢN Error!.
- 2.1 Một số bài toán đếm không lặp.
- 2.1.1 Bài toán lập số.
- 2.1.2 Bài toán chọn vật, chọn người, sắp xếp.
- 2.1.3 Bài toán tương tự.
- 2.2 Một số bài toán đếm có lặp.
- 2.2.1 Bài toán lập số.
- 2.2.2 Bài toán đếm sử dụng tổ hợp lặp.
- 2.2.3 Bài toán đếm sử dụng chỉnh hợp lặp.
- 2.2.4 Bài toán đếm sử dụng hoán vị lặp.
- 2.2.5 Bài toán phân bố các đồ vật vào trong hộp.
- 2.2.6 Bài toán tương tự.
- CHƯƠNG 3 - MỘT SỐ BÀI TOÁN TỔ HỢP SỬ DỤNG PHÉP ĐẾM NÂNG CAO.
- 3.1 Một số bài toán sử dụng nguyên lý bù trừ.
- 3.1.2 Các bài toán giải bằng phương pháp bù trừ.
- 3.2 Một số bài toán giải bằng phương pháp song ánh Error! Bookmark not defined..
- 3.2.2 Các bài toán tổ hợp giải bằng phương pháp song ánh.
- 3.3 Một số bài toán giải bằng phương pháp hàm sinh Error! Bookmark not defined..
- 3.3.1 Bài toán chọn các phần tử riêng biệt.
- 3.3.2 Bài toán chọn các phần tử có lặp Error! Bookmark not defined..
- 3.4 Một số bài toán giải bằng phương pháp hệ thức truy hồi.
- 3.4.2 Các bài toán tổ hợp giải bằng hệ thức truy hồi Error! Bookmark not defined..
- 3.4.3 Các bài toán tương tự.
- 3.5 Bài toán giải bằng nguyên lí cực hạn - khả năng xảy ra nhiều nhất, ít nhất.
- 3.6 Bài toán giải bằng phương pháp sắp xếp thứ tự.
- 3.7 Bài toán giải bằng phương pháp liệt kê các trường hợp.
- Toán học tổ hợp là một trong những lĩnh vực được nghiên cứu từ khá sớm.
- Hiện nay trong giáo dục phổ thông, toán học tổ hợp là một trong những nội dung quan trọng, nó thường xuyên xuất hiện trong các đề thi đại học và cao đẳng ở nước ta.
- Mặc dù ở mức độ không khó nhưng học sinh vẫn gặp khó khăn khi giải quyết các bài toán này.
- Còn trong các kỳ thi Quốc gia và Quốc tế, các bài toán tổ hợp luôn có mặt và là một thử thách thực sự với các thí sinh, thậm chí quyết định thành tích đối với các đội tuyển dự thi..
- Trong luận văn này đã đề cập đến một số bài toán tổ hợp trong toán học phổ thông, cụ thể là các bài toán tổ hợp sử dụng các phương pháp đếm từ cơ bản đến nâng cao.
- Chương 1- Cơ sở lý thuyết về tổ hợp..
- Chương 2- Một số bài toán tổ hợp cơ bản..
- Chương 3- Một số bài toán tổ hợp sử dụng phép đếm nâng cao..
- Do sự hạn chế về trình độ kiến thức và thời gian nên các bài toán tổ hợp trong luận văn còn ít, chưa có nhiều bài toán khó.
- Chương này sẽ nhắc lại một số lý thuyết về tập hợp và hệ thống lý thuyết cơ bản của toán tổ hợp như: Hoán vị, chỉnh hợp, tổ hợp.
- 1.1 Nhắc lại về tập hợp Tập hợp con.
- Định nghĩa: Cho tập hợp A .
- Tập hợp B gọi là tập con của tập A khi mọi phần tử của tập B đều thuộc A.
- Mọi tập hợp A đều có 2 tập con là  và A.
- Tập A có n phần tử thì số tập con của A là 2 n .
- 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ự  a a 1 , 2.
- b m  bằng nhau khi mọi phần tử tương ứng bằng nhau..
- 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 B C là 3 tập hợp hữu hạn, khi đó.
- A n là n tập hợp hữu hạn ( n  1.
- 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  X Quy tắc nhân (Tài liệu chuẩn kiến thức 12)..
- A n là n tập hợ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 A 1  A 2.
- A n được tiến hành bằng cách chọn lần lượt một phần tử.
- của A 1 , một phần tử của A 2.
- một phần tử của A n .
- 1.3 Giai thừa và hoán vị Giai thừa.
- Hoán vị.
- 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: P n là số các hoán vị của n phần tử..
- 1.4 Chỉnh hợp, tổ hợp Chỉnh hợp.
- 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ử đã cho..
- Kí hiệu: A n k là số các chỉnh hợp chập k của n phần tử..
- 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ử..
- Tổ hợp.
- Giả sử tập A có 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 (1.
- k n ) là số các tổ hợp chập k của n phần tử..
- 1.5 Chỉnh hợp lặp, hoán vị lặp và tổ hợp lặp 1.5.1 Chỉnh hợp lặp.
- 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 r .
- 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.
- Định lý 1.5.1 Số các chỉnh hợp lặp chập r từ tập n phần tử bằng n r.
- Rõ ràng có n cách chọn một phần tử từ tập n phần tử cho mỗi một trong r vị trí của chỉnh hợp khi cho phép lặp.
- n r chỉnh hợp lặp chập r từ tập n phần tử..
- Số các chỉnh hợp lặp chập p của n phần tử là n p.
- Như vậy chỉnh hợp có lặp lại là khi giữa các phần tử yếu tố thứ tự là cốt lõi, còn yếu tố khác biệt không quan trọng..
- Trong bài toán đếm, một số phần tử có thể giống nhau.
- Định lý 1.5.2 Số hoán vị của n phần tử trong đó có n 1 phần tử như nhau thuộc loại 1, có n 2 phần tử như nhau thuộc loại 2.
- và có n k phần tử như nhau thuộc loại k bằng.
- Để xác định số hoán vị trước tiên chúng ta nhận thấy có C n n 1 cách giữ n 1 số cho n 1 phần tử loại 1, còn lại n – n 1 chỗ trống..
- Sau đó có C n n n  2 1 cách đặt n 2 phần tử loại 2 vào hoán vị, còn lại n – n 1 – n 2 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ị.
- n k  1 cách đặt n k 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à: