Chuyên đề một số phương pháp đếm trong các bài toán tổ hợp

MỤC LỤC

1 Lý do chọn đềtài . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Mục đích nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Xây dựng mô hình trong các bài toán đếm của tổhợp . . . . . . . . . . . . . . . . . 6

3.1 SốCatalan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.2 Đường đi của con Kiến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.3 Bài toán chia kẹo Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Đếm bằng hai cách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.1 Tổng quan vềphương pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.2 Một sốví dụ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.3 Bài tập đềnghị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5 Đếm bằng cách thiết lập quan hệtruy hồi . . . . . . . . . . . . . . . . . . . . . . . . 42

5.1 Các bài toán kinh điển . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.2 Các bài toán trong các đềthi học sinh giỏi, Olympic . . . . . . . . . . . . . . 44

5.3 Bài tập đềnghị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6 Đếm bằng ánh xạ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

6.1 Kiến thức cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

6.2 Phương pháp ánh xạ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.3 Bài tập đềnghị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

7 Sửdụng sốphức trong phép đếm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

7.1 Sửdụng sốphức trong tính toán các biểu thức tổhợp . . . . . . . . . . . . . 99

7.2 Sửdụng đa thức và sốphức trong các bài toán đếm . . . . . . . . . . . . . . 101

8 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

9 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

1. LÝ DO CHỌN ĐỀTÀI MỤC LỤC

1. Lý do chọn đềtài

Các bài toán tổhợp là một phần quan trọng của chuyên ngành toán rời rạc và là một mảng khó

trong chương trình toán THPT chuyên. Trong các kì thi học sinh giỏi quốc gia, Olympic Toán quốc

tếvà khu vực, những bài toán tổhợp thường xuyên được đềcập và thường là những bài toán khó,

mang tính chất phân loại. Đềthi VMO cũng như các đềthi Olympic 30/4, Olympic DHBB trong

vài năm gần đây cũng đang có xu hướng giảm sốlượng các bài toán hình học phẳng và thay vào

đó là các bài toán tổhợp. Tuy nhiên, so với các phân môn khác thì các bài toán tổhợp đem lại

không ít khó khăn rắc rối cho các em học sinh bậc Trung học phổthông trong quá trình học cũng

như trong các kỳthi. Những học sinh mới bắt đầu làm quen một sốdạng toán tổhợp thường

chưa hiểu tường tận tư tưởng cũng như phương pháp tiếp cận bài toán. Đểhiểu và vận dụng tốt

một sốdạng toán cơ bản và vận dụng kiến thức tổhợp vào giải toán đòi hỏi học sinh phải có kiến

thức nền tảng tổhợp tương đối đầy đủvà chắc chắn trên tất cảcác lĩnh vực của ngành toán rời

rạc. Đó là một khó khăn rất lớn đối với giáo viên và học sinh khi giảng dạy và học tập phần này.

Chính vì khó nên dẫn đến nhiều học sinh nản trong quá trình học, có tâm lý sợcác bài toán tổ

hợp và có xu hướng không đầu tư cho việc giải chúng trong các kỳthi mà đểdành thời gian cho

các bài toán thuộc các phân môn khác. Từđó có thểthấy khó khăn lớn nhất của giáo viên là làm

sao đểhọc sinh hứng thú học và có khảnăng vận dụng các phương pháp vào giải các bài toán tổ

hợp, do đó vấn đềđặt ra là cần trang bịcho các em những kiến thức gì? Cần bắt đầu từnhững bài

toán nào? Cần phân dạng các bài tập áp dụng từng phương pháp giải toán tổhợp theo mức độtừ

thấp đến cao và những dấu hiệu của các bài toán như thếnào thì dùng phương pháp tương ứng?

Một trong những vấn đềđầu …