BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG…………………….

Luận văn tốt nghiệp
Các số tổ hợp liên quan đến số
các phân hoạch
1
Mục lục
mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1 Một số bài toán đếm và các số tổ hợp 5
1.1 Một số quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Quy tắc tương ứng một-một . . . . . . . . . . . . . . . . 5
1.1.2 Quy tắc cộng . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 Quy tắc nhân . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Một số bài toán đếm cơ bản . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Chỉnh hợp có lặp . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Chỉnh hợp không lặp . . . . . . . . . . . . . . . . . . . . 7
1.2.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.4 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 Phân hoạch tập hợp. Số Stirling loại hai và số Bell . . 8
1.3 Một vài ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Bài toán tính số nghiệm của phương trình . . . . . . . 10
1.3.2 Bài toán đếm tất cả các hàm từ một tập hữu hạn vào
một tập hữu hạn . . . . . . . . . . . . . . . . . . . . . . 11
1.3.3 Bài toán đếm tất cả các hàm đơn ánh từ một tập hữu
hạn vào một tập hữu hạn . . . . . . . . . . . . . . . . . 12
1.3.4 Bài toán đếm tất cả các hàm toàn ánh từ một tập hữu
hạn lên một tập hữu hạn . . . . . . . . . . . . . . . . . 13
2
1.4 Sự mở rộng về số các phân hoạch . . . . . . . . . . . . . . . . . 17
1.5 Một số kết quả về số Stirling loại một . . . . . . . . . . . . . . 29
2 Phương pháp đếm dùng hàm sinh 37
2.1 Phương pháp đếm dùng hàm sinh thông thường . . . . . . . . 37
2.2 Phương pháp đếm dùng hàm sinh mũ . . . . . . . . . . . . . . 48
3 Một số phương pháp và kỹ thuật đếm cơ bản khác 63
3.1 Phương pháp đếm bằng nguyên lý bao hàm và loại trừ. . . . . 63
3.2 Phương pháp đếm bằng công thức ngược . . . . . . . . . . . . 69
3.2.1 Công thức nghịch đảo nhị thức . . . . . . . . . . . . . . 72
3.2.2 Công thức nghịch đảo Stirling . . . . . . . . . . . . . . . 73
4 Dãy nhị thức 75
4.1 Khái niệm về dãy nhị thức . . . . . . . . . . . . . . . . . . . . . 75
4.2 Biểu diễn dãy nhị thức . . . . . . . . . . . . . . . . . . . . . . . 75
4.3 Dãy nhị thức sinh bởi một hàm số . . . . . . . . . . . . . . . . 79
4.4 Một số ví dụ về dãy nhị thức . . . . . . . . . . . . . . . . . . . 81
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3
mở đầu
Tổ hợp như là một lĩnh vực của toán học rời rạc, xuất hiện vào đầu
thế kỷ 17 bằng một loạt các công trình nghiên cứu của các nhà toán học xuất
sắc như Pascal, Fermat, Leibnitz, Euler.... Mặc dù vậy, tổ hợp vẫn là lĩnh vực
mờ nhạt và ít được chú ý tới trong quãng thời gian hơn hai thế kỷ. Tình thế
bắt đầu đổi khác khi xuất hiện các máy tính và cùng với nó là sự phát triển
của toán hữu hạn.
Hiện nay lý thuyết tổ hợp được áp dụng trong nhiều lĩnh vực khác nhau
như lý thuyết số, hình học hữu hạn, quá trình ngẫu nhiên, thống kê xác suất,...
Hướng nghiên cứu của luận văn là xây dựng các số tổ hợp cơ bản được
hình thành từ kết quả của một số bài toán đếm. Chúng tôi xét bài toán phân
hoạch tập hợp hữu hạn cùng với các điều kiện được đặt thêm vào. Trên cơ sở
đó luận văn đi đến một số kết quả mới về các số tổ hợp có liên quan đến số
các phân hoạch.
Luận văn được chia làm 4 chương:
Chương 1: Một số bài toán đếm và các số tổ hợp. Chương này
nhắc lại một số quy tắc và bài toán đếm cơ bản. Thông qua một số bài toán
đếm, luận văn xây dựng các số tổ hợp cơ bản. Hơn nữa, thông qua bài toán
phân hoạch tập hợp, chúng tôi tìm được các số tổ hợp mới cũng như mối liên
hệ giữa các số tổ hợp cơ bản đã biết với các số tổ hợp mới.
Chương 2: Phương pháp đếm dùng hàm sinh. Nội dung chính của
chương là giới thiệu phương pháp đếm dùng hàm sinh thông thường và hàm
sinh mũ. Với phương pháp này, luận văn giải quyết một số bài toán đếm cũng
như thiết lập được công thức tính cho các số tổ hợp quan trọng (số xáo trộn
tổng quát Dn, số Fibonaci Fn, số Bell Bn,...). Hơn nữa, chúng tôi cũng đưa ra
hàm sinh mũ cho các số tổ hợp mới vừa tìm được trong Chương 1.
4
Chương 3: Một số phương pháp và kỹ thuật đếm cơ bản khác.
Chúng tôi giới thiệu thêm hai phương pháp đếm cơ bản: Phương pháp đếm
bằng nguyên lý bao hàm và loại trừ và phương pháp đếm bằng công thức
ngược. Với các phương pháp đếm này, chúng tôi thiết lập công thức tính cho
các số tổ hợp Dn,Sn,k (số Stirling loại hai) và xây dựng công thức hàm Euler.
Chương 4: Dãy nhị thức. Sau khi trình bày sơ lược về dãy nhị thức,
chúng tôi chứng minh một số dãy các đa thức được trình bày trong Chương
2 là dãy nhị thức.
Tuy có nhiều cố gắng nhưng kết quả của luận văn vẫn còn nhiều hạn
chế, nội dung và cách trình bày khó tránh khỏi thiếu sót, tác giả rất mong
nhận được sự góp ý của các thầy cô giáo và các bạn đồng nghiệp để nâng cao
hơn nữa chất lượng của luận văn.
Quy Nhơn, tháng 2 năm 2008
Đoàn Nhật Thịnh