ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------
PHẠM THỊ HIÊN
MỘT SỐ BÀI TOÁN TỔ HỢP ĐẾM
LUẬN VĂN THẠC SĨ KHOA HỌC
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN -------------------
PHẠM THỊ HIÊN
MỘT SỐ BÀI TOÁN TỔ HỢP ĐẾM
Chuyên ngành: Phương pháp toán sơ cấp Mă số: 60460113
LUẬN VĂN THẠC SĨ KHOA HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
Hà Nội – Năm 2014 Hà Nội – Năm 2014MỤC LỤC
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. Đây có thể coi là tài liệu tham khảo hữu ích cho giáo viên và học sinh THPT về chủ đề này.
Luận văn gồm ba chương:
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ề tŕ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ó. Ngoài ra khoá luận cũng không thể tránh khỏi những sai sót ở nhiều góc độ, rất mong nhận được sự đóng góp ư kiến của quư thầy cô và các bạn.
CHƯƠNG 1 - CƠ SỞ LÍ THUYẾT VỀ TỔ HỢP
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. Các nội dung này cũng được giảng dạy cho học sinh trung học phổ thông hệ cơ bản, nâng cao và hệ chuyên nghành toán.
1.1 Nhắc lại về tập hợp
Tập hợp con
Định nghĩa: Cho tập hợp . Tập hợp gọi là tập con của tập khi mọi phần tử của tập đều thuộc .
Tính chất:
- Mọi tập hợp đều có 2 tập con là và .
- Tập có phần tử th́ số tập con của là .
Tập hợp sắp thứ tự
Một tập hợp hữu hạn có 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 , 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ự phần tử là một dăy hữu hạn phần tử và hai bộ sắp thứ tự và bằng nhau khi mọi phần tử tương ứng bằng nhau.
= =
Số phần tử của một số tập hợp
Tập hợp có hữu hạn phần tử th́ số phần tử của được kí hiệu là: hoặc .
là 3 tập hợp hữu hạn, khi đó
Tổng quát: Cho là tập hợp hữu hạn .
Khi đó
│ … │=
+ +…+ .
1.2 Quy tắc cộng và quy tắc nhân
Quy tắc cộng
Định nghĩa (Tài liệu chuẩn kiến thức 12).
Một công việc được hoàn thành bởi một trong hai hành động. Nếu hành động này có m cách thực hiện, hành động kia có n cách thực hiện không trùng với bất ḱ cách nào của hành động thứ nhất th́ công việc đó có m + n cách thực hiện.
Tổng quát
Một công việc được hoàn thành bởi một trong các hành động .
T1 có m1 cách thực hiện.
T2 có m2 cách thực hiện
...
Tn có mn cách thực hiện.
Giả sử không có hai việc nào có thể làm đồng thời th́ công việc đó có cách thực hiện.
Biểu diễn dưới dạng tập hợp:
Nếu là hai tập hợp hữu hạn, không giao nhau th́
Nếu là tập hữu hạn, từng đôi một không giao nhau th́
Nếu là hai tập hữu hạn và th́
Quy tắc nhân (Tài liệu chuẩn kiến thức 12).
Giả sử để hoàn thành một nhiệm vụ H cần thực hiên hai công việc nhỏ là H1 và H2. Trong đó:
có thể làm bằng cách.
có thể làm bằng cách, sau khi đă hoàn thành công việc .
Khi đó để thực hiện công việc sẽ có cách.
Tổng quát
Giả sử để hoàn thành một nhiệm vụ cần thực hiện công việc nhỏ là , ,…, trong đó:
có thể làm bằng cách.
có thể làm bằng cách, sau khi đă hoàn thành công việc .
…
có thể làm bằng cách, sau khi đă hoàn thành công việc .
Khi đó để thực hiện công việc sẽ có cách.
Biểu diễn dưới dạng tập hợp:
Nếu là tập hợp hữu hạn , 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 được tiến hành bằng cách chọn lần lượt một phần tử của , một phần tử của ,…, một phần tử của . Theo quy tắc nhân ta nhận được đẳng thức: .
Chia sẻ với bạn bè của bạn: |