BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG…………………….

Luận văn thạc sỹ
Mối liên hệ giữa các số phân hoạch, số tất
cả các phân hoạch chẵn , số tất cả các
phân hoạch lẻ
1
Mục lục
mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1 Kiến thức chuẩn bị 5
1.1 Các quy tắc đếm cơ bản . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Một số bài toán đếm và kết quả tổ hợp cơ bản . . . . . . . . . . 10
1.2.1 Chỉnh hợp - hoán vị - tổ hợp . . . . . . . . . . . . . . . . 10
1.2.2 Phân hoạch của tập hợp. Số Stirling loại hai và số Bell . 13
1.2.3 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 . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.4 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. . . . . . . . . . . . . . . . . . . 16
1.2.5 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 . . . . . . . . . . . . . . . . . . 16
2 Hàm sinh và công thức sàng 20
2.1 Hàm sinh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Hàm sinh mũ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Công thức sàng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.1 Nguyên lý bù trừ . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.2 Công thức ngược . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.3 Công thức sàng . . . . . . . . . . . . . . . . . . . . . . . . 40
3 Biến thể của công thức sàng 45
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2
tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3
mở đầu
lý thuyết tổ hợp xuất hiện vào thế kỷ 17. Trong một thời gian dài nó nằm
ngoài hướng phát triển chung và những ứng dụng của toán học. Song tình
hình đã thay đổi hẳn sau khi máy tính điện tử ra đời và tiếp theo sau đó là sự
phát triển nhảy vọt của toán học hữu hạn. Cùng với sự phát triển với tốc độ
nhanh của công nghệ thông tin, lý thuyết tổ hợp đã trở thành lĩnh vực toán
học quan trọng và cần thiết cho nhiều lĩnh vực khoa học và ứng dụng. Một
trong những ảnh hưởng mạnh mẽ nhất của lý thuyết tổ hợp là phần tính toán
với các tập hữu hạn. Trong chương trình toán ở bậc phổ thông hiện nay, đã
có sự chú trọng đặc biệt đến phần kiến thức về tổ hợp. Các bài toán về tổ hợp
cũng thường xuất hiện trong các kỳ thi học sinh giỏi Toán quốc gia và quốc tế.
Hướng nghiên cứu của luận văn là giới thiệu về phương pháp dùng hàm
sinh, hàm sinh mũ để giải một số bài toán tổ hợp và giới thiệu về một công
thức sàng lọc số phần tử của một tập hữu hạn theo hướng các phần tử này
có mặt trong đúng chẵn (lẻ) tập con của tập đã cho mà ta gọi là công thức
sàng. Từ tính hữu dụng của kỹ thuật hàm sinh và ý tưởng về việc sàng lọc
theo hướng chẵn (lẻ) của công thức sàng, trong luận văn chúng tôi đưa ra công
thức tính cho số phân hoạch chẵn (lẻ) của một tập hợp hữu hạn cho trước mà
nó sẽ được gọi là một biến thể của công thức sàng. Đặc biệt, mối liên hệ
giữa số tất cả các phân hoạch,số tất cả các phân hoạch chẵn,số tất
cả các phân hoạch lẻ (thành các tập con không rỗng) của một tập hữu hạn
là vấn đề mà chúng tôi rất quan tâm.
Luận văn gồm có ba chương, phần kết luận và tài liệu tham khảo.
Chương 1. Kiến thức chuẩn bị
Trong chương này, chúng tôi trình bày về một số quy tắc đếm, bài toán đếm
và một vài kết quả cơ bản về tổ hợp.
Chương 2. Hàm sinh và công thức sàng
Chương này gồm ba phần.
- Hàm sinh thường: Giới thiệu về hàm sinh thường và áp dụng vào giải một
4
vài bài toán tổ hợp điển hình.
- Hàm sinh mũ: Giới thiệu về hàm sinh mũ và áp dụng vào giải một vài bài
toán tổ hợp điển hình.
- Công thức sàng: Dùng công thức ngược cho các đồng nhất thức tổ hợp, kết
hợp với nguyên lý bù trù trừ để xây dựng công thức sàng.
Chương 3. Biến thể của công thức sàng
Trong chương này, chúng tôi đưa ra cách tính số tất cả các cách phân hoạch
một tập hợp hữu hạn thành các tập con không rỗng sao cho mỗi tập con có
một số chẵn (một số lẻ) phần tử bằng cách áp dụng kỹ thuật hàm sinh mũ kết
hợp với các phép biến đổi giải tích. Hơn nữa, chúng tôi cũng sẽ xác định các số
này bằng con đường sơ cấp hơn qua các công thức tính truy hồi. Mối liên hệ
giữa số tất cả các phân hoạch chẵn,số tất cả các phân hoạch lẻ này với số tất
cả các phân hoạch một tập hữu hạn thành các tập con không rỗng mà chúng ta
đã biết trong một số tài liệu về tổ hợp cũng sẽ được đưa ra. Sau cùng là một
vài ví dụ.
Tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy Nguyễn Thái Hòa -Trường
ĐHQN. Thầy đã tận tình hướng dẫn, động viên, giúp đỡ trong quá trình nghiên
cứu và hoàn chỉnh luận văn.
Tác giả xin bày lòng biết ơn sâu sắc đến thầy Phạm Xuân Bình -Trường
ĐHQN. Các vấn đề mới của luận văn được thực hiện dựa trên ý tưởng ban
đầu mà thầy đã gợi ý cho tác giả.
Tác giả xin chân thành cám ơn đến Ban lãnh đạo Trường Đại Học Quy
Nhơn, Phòng quản lý khoa học, Phòng đào tạo, các thầy cô giáo đã tham gia
giảng dạy lớp cao học toán khóa 8, Sở Giáo dục và Đào tạo tỉnh Bình Định,
Trường THPT An Lương - Bình Định, cùng tất cả các bạn bè đồng nghiệp đã
tạo điều kiện, giúp đỡ cho tác giả trong suốt thời gian học tập và thực hiện
luận văn này.
Quy Nhơn, 2008
Phạm Triều Đại