ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
------------------
NGUYỄN NGỌC MAI
MỘT VÀI NGUYÊN LÝ
VÀ
BÀI TOÁN TỔ HỢP
LUẬN VĂN THẠC SỸ TOÁN HỌC
HÀ NỘI- 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
------------------
NGUYỄN NGỌC MAI
MỘT VÀI NGUYÊN LÝ
VÀ
BÀI TOÁN TỔ HỢP
Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số: 60460113
LUẬN VĂN THẠC SỸ TOÁN HỌC
Người hướng dẫn khoa học
PGS. TS. ĐÀM VĂN NHỈ
HÀ NỘI- 2014
Mục lục
Mở đầu 3
1 Kiến thức chuẩn bị 5
1.1 Nguyên lý quy nạp . . . . . . . . . . . . . . . . . . . . 5
1.2 Hai quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . 8
1.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5.1 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . 14
1.5.2 Ứng dụng trong số học . . . . . . . . . . . . . . 16
1.6 Nhị thức Newton . . . . . . . . . . . . . . . . . . . . . 18
1.7 Đồ thị cây . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Một vài nguyên lý trong tổ hợp 26
2.1 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . 26
2.1.1 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . 26
2.1.2 Nguyên lý Dirichlet áp dụng trong hình học tổ hợp 31
2.2 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . 34
2.3 Nguyên lý cực hạn . . . . . . . . . . . . . . . . . . . . . 42
2.4 Nguyên lý bất biến . . . . . . . . . . . . . . . . . . . . 51
3 Một vài đồng nhất thức trong tổ hợp 60
3.1 Xây dựng đồng nhất thức qua hệ phương trình . . . . . 60
3.2 Xây dựng đồng nhất thức qua số phức . . . . . . . . . 66
3.3 Xây dựng đồng nhất thức qua hàm sinh . . . . . . . . . 69
3.3.1 Khái niệm hàm sinh . . . . . . . . . . . . . . . . 70
3.3.2 Một số đồng nhất thức liên quan đến hàm sinh . 70
3.3.3 Ứng dụng của hàm sinh . . . . . . . . . . . . . . 71
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . 78
1
Lời cảm ơn
Tôi xin được bày tỏ lòng kính trọng và biết ơn sâu sắc đến PGS.TS Đàm Văn
Nhỉ. Thầy đã dành nhiều thời gian hướng dẫn cũng như giải đáp các thắc
mắc của tôi trong suốt quá trình tôi thực hiện đề tài.
Tôi xin gửi lời cảm ơn chân thành tới các thầy cô Khoa Toán - Cơ - Tin
học, Phòng Sau đại học - Trường Đại học Khoa học Tự nhiên- Đại học Quốc
gia Hà Nội; các thầy cô đã tham gia giảng dạy khóa cao học 2011-2013.
Cuối cùng, tôi xin chân thành cảm ơn gia đình và bạn bè đã luôn động
viên tôi trong suốt quá trình học tập và thực hiện luận văn.
2
Mở đầu
Tư duy về tổ hợp xuất hiện từ rất sớm trong lịch sử phát triển của nhân loại.
Tuy nhiên, lý thuyết tổ hợp được xem hình thành như một ngành toán học
vào khoảng thế kỷ 17 bằng một loạt các công trình nổi tiếng của các nhà toán
học như Passcal, Fermat, Leibniz, Euler, . . . . Kể từ sau khi tin học ra đời, lý
thuyết tổ hợp phát triển ngày càng mạnh mẽ. Các vấn đề liên quan đến lý
thuyết tổ hợp là một bộ phận quan trọng, hấp dẫn và lí thú của toán học nói
chung và của toán rời rạc nói riêng. Nó không chỉ có nội dung phong phú, đa
dạng, mà còn có nhiều ứng dụng trong thực tế đời sống.
Trong toán sơ cấp, tổ hợp cũng xuất hiện với nhiều bài toán hay với độ khó
cao. Khi giải các bài toán tổ hợp, ta phải liệt kê, đếm các đối tượng theo các
tính chất nào đó. Để làm được việc này, ngoài việc sử dụng hai quy tắc đếm
cơ bản, các kiến thức về hoán vị, chỉnh hợp, tổ hợp, trong nhiều bài toán ta
phải sử dụng một số nguyên lý khác trong tổ hợp. Vì vậy, để hiểu rõ và nắm
bắt sâu hơn vể vấn đề này, tôi đã chọn đề tài Một vài nguyên lý và bài
toán tổ hợp. Luận văn đã trình bày một số nguyên lý cơ bản trong tổ hợp
và xây dựng một số bài toán áp dụng.
Luận văn gồm phần mở đầu, ba chương, kết luận và danh mục tài liệu tham
khảo.
Chương 1:Kiến thức chuẩn bị. Trong chương này, tác giả đã trình bày
một số lý thuyết về nguyên lý quy nạp, hai quy tắc đếm cơ bản, hoán vị,
chỉnh hợp, tổ hợp, nhị thức Newton và đồ thị cây.
Chương 2:Một vài nguyên lý trong tổ hợp. Chương 2 gồm 4 nội dung
chính, trình bày bốn nguyên lý cơ bản trong tổ hợp và các ví dụ áp dụng các
nguyên lý đó. Cụ thể là:
Mục 2.1 trình bày nguyên lý thứ nhất: Nguyên lý Dirichlet. Nguyên lý này
còn được gọi là nguyên lý lồng chim bồ câu. Giả sử có một đàn chim bồ câu
bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất có ngăn
3