Phép đếm - các kĩ thuật cơ bản, nâng cao, cực hay

Phép đếm hay còn gọi là Giải tích tổ hợp đóng một vai trò khá quan trọng trong các môn khoa học và đặc biệt là trong Tin học và Toán ứng dụng. Có thể nói, lý thuyết xác suất cổ điển có cơ sở là các bài tóan đếm, sinh học di truyền cũng sử dụng đến phép đếm, rồi hóa học cấu trúc …

Nhưng giải một bài tóan đếm không hề đơn giản. Khi mới làm quen với giải tích tổ hợp, chúng ta vẫn liên tục đếm nhầm vì những vụ đếm lặp, đếm thiếu, không phân biệt được các đối tượng tổ hợp cần áp dụng, không biết khi nào thì dùng quy tắc cộng, khi nào quy tắc nhân. Khi đã vượt qua những khó khăn ban đầu này, ta lại gặp những bài tóan mà việc áp dụng trực tiếp các quy tắc đếm cơ bản và các đối tượng tổ hợp không đem lại kết quả mong muốn ngay lập tức. Với những bài tóan như vậy, ta cần đến các phương pháp đếm nâng cao hơn.

Trong bài viết này, để có tính hệ thống, trước hết chúng tôi sẽ trình bày một cách vắn tắt phần lý thuyết cơ bản của phép đếm, sau đó, chúng tôi sẽ tập trung vào giới thiệu các phương pháp đếm nâng cao gồm phương pháp song ánh, phương pháp quỹ đạo, phương pháp thêm bớt, phương pháp quan hệ đệ quy và phương pháp hàm sinh.

Bài viết này được xây dựng dựa trên bài giảng của chúng tôi tại các khóa cao học, các lớp cử nhân tài năng và lớp tập huấn cho đội tuyển Việt Nam thi toán quốc tế. Các tài liệu tham khảo được trình bày ở cuối bài viết.

Phep dem - Cac van de co ban va nang cao của TS. Trần Nam Dũng. Download.