Một số chuyên đề về tổ hợp dành cho học sinh giỏi Toán

Mục lục

Lời cảm ơn 1

Mở đầu 3

Chương 1. Kiến thức cơ bản 6

1.1. Quy tắc cộng và quy tắc nhân . . . . . . . . . . . . . . . . . 6

1.2. Hoán vị và tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3. Nguyên lý chuồng chim bồ câu (Nguyên lý Dirichlet) . . . . 9

1.4. Hoán vị và tổ hợp tổng quát . . . . . . . . . . . . . . . . . . 11

1.5. Công thức bao hàm và loại trừ . . . . . . . . . . . . . . . . . 14

Chương 2. Một số chuyên đề về tổ hợp dành cho học sinh có năng

khiếu toán bậc trung học phổ thông 17

2.1. Chuyên đề 1: Quy tắc cộng và quy tắc nhân . . . . . . . . . . 18

2.2. Chuyên đề 2: Hoán vị và tổ hợp . . . . . . . . . . . . . . . . 23

2.3. Chuyên đề 3: Nguyên lý chuồng chim bồ câu . . . . . . . . . 29

2.4. Chuyên đề 4: Các số Ramsey . . . . . . . . . . . . . . . . . . 32

2.5. Chuyên đề 5: Các số Catalan . . . . . . . . . . . . . . . . . . 38

2.6. Chuyên đề 6: Các số Stirling . . . . . . . . . . . . . . . . . . 41

2.7. Chuyên đề 7: Hoán vị và tổ hợp tổng quát . . . . . . . . . . . 47

2.8. Chuyên đề 8: Nguyên lý bao hàm và loại trừ . . . . . . . . . 50

2.9. Chuyên đề 9: Những sự xáo trộn và những sự sắp đặt trước . . 54

2.10. Chuyên đề 10: Đại lượng bất biến . . . . . . . . . . . . . . . 57

Chương 3. Một số bài tập đề nghị 60

2

Mở đầu

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 cổ

Hy lạp, nhà triết học Kxenokrat, sống ë thế kỷ thứ 4 trước công nguyên, đã

biết tính số các từ khác nhau lập 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. Tuy nhiên, có thể nói rằng, lý thuyết tổ hợp được hình thành như

một ngành toán học mới và quãng thế kỷ 17 bằng một 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, Fermat,

Leibnitz, Euler...Mặc dù vậy, trong suốt hai thế kỷ rưỡi, 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ả có ích cho con người.

Nhận thức được vai trò của lý thuyết tổ hợp đối với đời sống hiện đại. Lý

thuyết tổ hợp đã được đưa vào chương trình học phổ thông và chiếm một

phần trong các kỳ thi toán quốc gia và quốc tế. Tuy nhiên, ë nước ta, tài liệu

viết về tổ hợp chưa nhiều. Do đó, bản luận văn này sẽ cung cấp thêm một tài

liệu về tổ hợp cho học sinh phổ thông; đặc biệt là dành cho những em học

sinh có năng khiếu môn toán. Chúng tôi hi vọng luận văn này sẽ đáp ứng

được phần nào lòng yêu thích khám phá toán học của các em. Đồng thời đây

cũng là một tài liệu để các đồng nghiệp tham khảo.

Luận văn gồm ba chương. Chương một chúng tôi trình bày một số kiến

4

thức cơ bản của tổ hợp theo một lôgic khác so với sách phổ thông nhằm gây

sự mới lạ cho học sinh. Chương hai là trọng tâm của luận văn. Trong chương

này, học sinh được tìm hiểu mười chuyên đề:

Chuyên đề 1: Quy tắc cộng và quy tắc nhân.

Chuyên đề 2: Hoán vị và tổ hợp.

Chuyên đề 3: Nguyên lý chuồng chim bồ câu.

Chuyên đề 4: Các số Ramsey.

Chuyên đề 5: Các số Catalan.

Chuyên đề 6: Các số Stirling.

Chuyên đề 7: Hoán vị và tổ hợp tổng quát.

Chuyên đề 8: Nguyên lý bao hàm và loại trừ.

Chuyên đề 9: Những sự xáo trộn và những sự sắp đặt trước.

Chuyên đề 10: Đại lượng bất biến.

Trong mỗi chuyên đề, các bài tập thường được dẫn dắt theo những chủ đề

nhất định. Qua đó học sinh tự tìm thấy cho mình những kiến thức liên quan

đến chủ đề được nêu. Đồng thời, mỗi bài đều có lời giải chi tiết, ngắn gọn,

đầy sáng tạo và bất ngờ. Các lời giải này ít gặp trong các tài liệu về tổ hợp có

trên thị trường. Tác giả hi vọng chính điều này kích thích sự ham hiểu biết,

lòng say mê của các học sinh có năng khiếu toán. Chương ba có nội dung là

những bài tập đề nghị được chọn lựa kĩ lưỡng; nhằm giúp các …