1
2
BỘ GIÁO DỤC VÀ ĐÀO TẠO
Công trình ñược hoàn thành tại
ĐẠI HỌC ĐÀ NẴNG
ĐẠI HỌC ĐÀ NẴNG
TRẦN LÊ HẠNH ĐOAN
Người hướng dẫn khoa học: PGS.TSKH.Trần Quốc
Chiến
NGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀ
Phản biện 1: TS. Cao Văn Nuôi
ỨNG DỤNG
Phản biện 2: PGS. TS. Trần Đạo Dõng
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số: 60.46.40
Luận văn sẽ ñược bảo vệ tại Hội ñồng chấm Luận văn
tốt nghiệp thạc sĩ khoa học tại Đại học Đà Nẵng ngày
29 tháng 05 năm 2011.
TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC
Có thể tìm hiểu luận văn tại:
Đà Nẵng - Năm 2011
-
Trung tâm thông tin - Học liệu, Đại học Đà Nẵng
-
Thư viện trường Đại học sư phạm, Đại học Đà
Nẵng.
4
3
MỞ ĐẦU
2. Mục ñích nghiên cứu
Từ các ứng dụng nguyên lý bao hàm và loại trừ giải lớp các bài
1. Lý do chọn ñề tài
Cùng với sự phát triển với tốc ñộ nhanh của công nghệ thông
toán tương tự cụ thể.
tin, lý thuyết tổ hợp ñã trở thành lĩnh vực toán học quan trọng và cần
3. Đối tượng nghiên cứu
thiết cho nhiều lĩnh vực khoa học và ứng dụng. Nhiều bài toán hiện
Đối tượng nghiên cứu: nguyên lý bao hàm và loại trừ.
nay ñược giải quyết bằng cách quy chúng về các bài toán tổ hợp.
Phạm vi nghiên cứu: nội dung của nguyên lý bao hàm và loại
Lý thuyết tổ hợp nghiên cứu việc phân bố, sắp xếp các phần tử
của một hoặc nhiều tập hợp, thoả mãn một số ñiều kiện nào ñó.
Các bài toán tổ hợp rất phong phú và ña dạng: bài toán tồn tại,
bài toán ñếm, bài toán liệt kê và bài toán tối ưu. Trong các bài toán
ñó thì bài toán ñếm ñược ứng dụng rộng rãi và ña dạng. Từ các cấu
hình tổ hợp cơ bản người ta hình thành nên hệ thống các cấu hình tổ
hợp mở rộng và nâng cao.
trừ, ứng dụng của nguyên lý này.
4. Phương pháp nghiên cứu
Gián tiếp thông qua các tài liệu: sách, giáo trình, tạp chí toán
học tuổi trẻ, truy cập các trang web.
Trực tiếp thông qua sự hướng dẫn của thầy và việc trao ñổi
thảo luận với các bạn.
5. Ý nghĩa khoa học và thực tiễn
Công thức xác ñịnh số phần tử của hợp một số tập hữu hạn
Đề tài góp phần nghiên cứu, hỗ trợ học sinh khi học phần tổ
thường ñược dùng trong nhiều bài toán ñếm. Một trong những công
hợp, giải một số bài toán số học mà việc giải chúng có nhiều ứng
thức ñó là nguyên lý bao hàm và loại trừ của tập hợp. Sử dụng
dụng trong trong các lĩnh vực toán học, tin học.
nguyên lý này và phối hợp một số phương pháp khác trên tập hợp
6. Nội dung luận văn
chẳng hạn phương pháp ánh xạ, ta có thể giải một số dạng toán.
1) Mở ñầu
Trong lý thuyết tổ hợp, nguyên lý bao hàm và loại trừ là
2) Chương 1. Đại cương về tổ hợp
phương pháp ñếm nâng cao giải các bài toán ñếm, nó có nhiều ứng
3) Chương 2. Nguyên lý bao hàm và loại trừ
dụng hay. Trong các kỳ thi học sinh giỏi quốc gia, thi Olympic toán
4) Chương 3. Ứng dụng của nguyên lý bao hàm và loại trừ
quốc tế, thi Olympic sinh viên giữa các trường ñại học và cao ñẳng
5) Kết luận
các bài toán liên quan ñến dạng này hay ñược ñề cập và thường thuộc
loại rất khó.
Chính vì các lý do trên,
tôi ñã nghiên cứu và chọn:
“NGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀ ỨNG DỤNG ” làm
ñề tài luận văn thạc sĩ của mình.
6
5
CHƯƠNG 1. ĐẠI CƯƠNG VỀ TỔ HỢP
Nếu ta ký hiệu số chỉnh hợp có lặp chập k của n phần tử của A
bằng AR (n, k) thì
1.1 Sơ lược lịch sử
AR (n, k) = nk
1.2 Các quy tắc ñếm cơ bản
1.2.1 Quy tắc tương ứng một – một. Nếu tồn tại tương ứng
1.3.2 Chỉnh hợp không lặp
• Định nghĩa. Một chỉnh hợp không lặp chập k của n phần tử
một – một giữa các phần tử của các tập hữu hạn A 1 và A 2 , thì A 1
khác nhau là một bộ có thứ tự gồm k thành phần lấy từ n phần tử ñã
và A 2 có cùng số các phần tử.
cho. Các thành phần không ñược lặp lại. Chỉnh hợp không lặp ñơn
Giả sử A 1 , A 2 ,...A n là các tập hữu hạn bất kỳ. Ta ñịnh nghĩa
giản gọi là chỉnh hợp.
tích Đề-các của A 1 , A 2 ,...A n , kí hiệu là A 1 × A 2 ...× A n , là tập
bao gồm tất cả các bộ có thứ tự
( a1 , a2 , ..., an )
gồm n thành phần
a1 , a2 , ..., an sao cho a1 ∈ A1 , a2 ∈ A2 ,..., an ∈ An
1.2.2 Quy tắc nhân. Nếu A 1 , A 2 ,...A n là các tập hữu hạn bất
kỳ và A 1 × A 2 ...× A n là tích Đề các của các tập ñó thì
A1 × A2 × ... × An = A1 A2 ... An
1.2.3 Quy tắc cộng. Nếu A 1 , A 2 ,...A n là các tập hữu hạn ñôi
một rời nhau, tức là Ai ∩ AJ = φ nếu i ≠ j thì
Kí hiệu số các chỉnh hợp chập k của n phần tử của A là A(n, k)
ta có
n!
A ( n, k ) = ( n − k ) !
0
1.3 Cấu hình tổ hợp cơ bản
1.3.1 Chỉnh hợp lặp
• Định nghĩa. Một hoán vị của n phần tử khác nhau là một
cách sắp xếp thứ tự các phần tử ñó.
Hoán vị có thể coi là trường hợp riêng của chỉnh hợp không
lặp chập k của n trong ñó k = n. Ta có số hoán vị là
P(n) = n!
1.3.4 Hoán vị vòng quanh
Số hoán vị vòng quanh của n phần tử khác nhau ( Qn ) ñược
tính bằng công thức
Qn = (n − 1)!
• Định nghĩa. Một chỉnh hợp lặp chập k của n phần tử khác
nhau là một bộ có thứ tự gồm k thành phần lấy từ n phần tử ñã cho.
Các thành phần có thể ñược lặp lại.
khi k > n
1.3.3 Hoán vị không lặp
A1 ∪ A2 ∪ ... − ∪ An = A1 + A2 + ... + An
Ở ñây Ai là lực lượng ( số các phần tử ) của tập A i
khi k ≤ n
1.3.5 Tổ hợp
• Định nghĩa. Một tổ hợp chập k của n phần tử khác nhau là
một bộ không kể thứ tự gồm k thành phần khác nhau lấy từ n phần tử
7
8
ñã cho. Nói cách khác ta có thể coi một tổ hợp chập k của n phần tử
với m = m1 + m2 + ... + mn .
khác nhau là một tập con có k phần tử từ n phần tử ñã cho.
• Hệ quả. Giả sử tập S có n phần tử, trong ñó có n1 phần tử
Nếu ta ký hiệu số tổ hợp chập k của n phần tử của A bằng C(n,
kiểu 1, n2 phần tử kiểu 2, ... , nk phần tử kiểu k. Khi ñó số các hoán
k) thì
vị n phần tử của S là
n!
khi 1 ≤ k ≤ n
C (n, k ) = k!(n − k )!
0
khi k > n
P ( n ; n 1 , n 2 , . .. , n k
Mỗi tổ hợp chập k của n phần tử của A có thể xem như là 1 tập
)
=
n!
n 1 ! n 2 ! . . .n k !
1.4.2 Tổ hợp lặp
con lực lượng k của A. Vì vậy C(n, k) chính bằng số các tập con lực
• Định nghĩa. Tổ hợp lặp chập k từ n phần tử khác nhau là
lượng k của A. Với k = 0, vì chỉ có 1 tập con của A lực lượng 0 là tập
một nhóm không phân biệt thứ tự gồm k phần tử trích từ n phần tử ñã
rỗng nên ta có thể ñịnh nghĩa một cách tự nhiên rằng C(n, 0) = 1. Khi
cho, trong ñó các phần tử có thể ñược lặp lại.
ñó ñẳng thức C (n, k ) =
• Định lý 2. Giả sử X có n phần tử khác nhau. Khi ñó số tổ
n!
cũng ñúng cho cả k = 0.
k !(n − k )!
hợp lặp chập k từ n phần tử của X, ký hiệu CR(n, k), là
1.4 Cấu hình tổ hợp mở rộng
CR(n, k) = C(k + n – 1, n - 1) = C(k + n – 1, k).
1.4.1 Hoán vị lặp
1.4.3 Phân hoạch của tập hợp. Số Sterling loại 2 và số Bell
• Định nghĩa. Hoán vị lặp là hoán vị trong ñó mỗi phần tử
Giả sử A là tập hữu hạn với A = n , còn k là 1 số nguyên
ñược ấn ñịnh một số lần lặp lại cho trước.
Ký hiệu số các hoán vị có lặp của các phần tử
a 1 , a 2 , ... , a n với
tham
số
lặp
m1 , m2 , ..., mn
là
P ( m; m1 , m2 , ..., mn ) .
• Định lý 1. Số hoán vị lặp của n phần tử khác nhau, trong ñó
phần tử thứ nhất lặp m1 lần, phần tử thứ hai lặp m2 lần, ... , phần tử
dương. Ta cũng giả sử A1 = A .
S là sơ ñồ sắp xếp “tập { X1 , X 2 , ... , X k } với X1 , X 2 , ... , X k
cũng là các “tập” ñể ta xếp các phần tử của A 1 vào ”,
R1 là ñiều kiện “mọi phần tử của A 1 ñều ñược sắp xếp vào
một trong các “tập” X1 , X 2 , ... , X k ”,
R2 là ñiều kiện “với mọi i = 1, ... , k có ít nhất một phần tử của
thứ n lặp mn lần là
m!
P (m; m1, m2,...mn) = m !m !...m !
1
2
n
A1 ñược xếp vào Xi ”.
10
9
Khi ñó, một cấu hình tổ hợp trên A1 theo S thỏa mãn các ñiều
kiện R1 và R2 ñược gọi là một phân hoạch của A thành k khối.
Số tất cả các phân hoạch thành k khối của một tập A lực lượng
1.4.5 Phân hoạch không thứ tự tổ hợp
• Định nghĩa. Cho X là tập n phần tử khác nhau, các số
nguyên dương n1 , n2 , ... , nk và p1 , p2 , ... , pk thỏa
n1 p1 + n 2 p 2 + ... + n k p k = n
n ñược gọi là số Sterling loại 2 và ñược ký hiệu là S(n, k). Dễ thấy
rằng S(n, k) = 0 nếu k > n. Ta cũng quy ước rằng S(n, 0) = 0.
Số
Tn = S(n, 1) + S ( n, 2 ) + ... + S(n, n) ñược gọi là số
Bell. Như vậy, số Bell chính là số tất cả các phân hoạch của tập A lực
lượng n.
Việc tính S(n, k) và Tn sẽ ñược trình bày trong phần ứng dụng
của nguyên lý bao hàm và loại trừ.
1.4.4 Phân hoạch thứ tự tổ hợp
• Định nghĩa. Cho X là tập n phần tử khác nhau, r ≤ n và
S ⊂ X có r phần tử. Một phân hoạch {S1 , S2 , ... , Sn } có thứ tự của
S gọi là 1 phân hoạch thứ tự tổ hợp chập r của X. Nếu r = n, thì gọi là
các
số
nguyên
dương
n1 , n2 , ... , nk
thỏa
n1 + n2 + ... + nk = r . Số các phân hoạch thứ tự tổ hợp chập r của
X dạng
{S1 , S2 , ... , Sk }
có S1 = n1 , S2 = n2 , ... , Sk = nk ñược
ký hiệu là C ( n; n1 , n2 , ... , nk ) .
• Định lý3.
C ( n; n1 , n2 , ... , nk )
tập lực lượng n2 , ... , pk tập lực lượng nk gọi là phân hoạch không
thứ tự của X.
• Định lý 4. Số phân hoạch không thứ tự của X với p1 tập lực
lượng n1 , p2 tập lực lượng n2 , ... , pk tập lực lượng nk là
C (n; n1 ..., n1 , n2 ,..., n2 , nk ,..., nk )
n!
=
p1
p
p
p1! p2 !... pk !
p1!(n1!) p2 !(n2 !) 2 ... p k !(nk !) k
(trong tử số C ( n; n1 , ..., n1 , n2 , ... , n2 , nk , ... , nk ) số n1 lặp lại p1
lần, số n2 lặp lại p2 lần,..., số nk lặp lại pk lần).
◊ Ví dụ 9
phân hoạch thứ tự của X.
Cho
Một hệ thống các tập con của X gồm p1 tập lực lượng n1 , p2
n!
=
= P(n; n1 , n2 , ..., nk , n − r )
n1 !.n2 !...nk ! ( n − r )!
C ( n; n1 , n2 , ... , nk ) ñược gọi là hệ số ña thức.
(i) Số cách chia 21 học sinh vào 3 lớp học buổi sáng, buổi
chiều và buổi tối, mỗi lớp 7 sinh viên là
C ( 21; 7, 7, 7 ) =
21!
( 7!)
(phân hoạch thứ tự)
3
(ii) Số cách chia 21 học sinh thành 3 tổ, mỗi tổ 7 học sinh là
C ( 21; 7, 7, 7 )
3!
=
21!
( 7!)
3
3!
(phân hoạch không thứ tự).
11
CHƯƠNG 2. NGUYÊN LÝ BAO HÀM VÀ LOẠI TRỪ
2.1 Nguyên lý bao hàm và loại trừ dạng kinh ñiển
2.1.1 Công thức 1 (Nguyên lý bao hàm và loại trừ cho hai
12
2.1.3 Công thức 3 (Nguyên lý bao hàm và loại trừ dạng
kinh ñiển)
X1 ∪ X 2 ∪ ... ∪ X n =
tập hợp)
Có bao nhiêu phần tử trong hợp của hai tập hữu hạn phần tử?
Số các phần tử trong hợp hai tập A và B bằng tổng các phần tử của
mỗi tập trừ ñi số phần tử của giao hai tập hợp, tức là
A ∪ B = A + B − A ∩ B
+(−1)k +1
∑
1≤i1 4 và có tính chất A 3 là x3 > 6 . Khi ñó số nghiệm thỏa mãn
các bất ñẳng thức x1 ≤ 3 , x2 ≤ 4 và x 3 ≤ 6 bằng
A1 ∩ A2 ∩ A3 =
A − A1 − A2 − A3 + A1 ∩ A2 + A1 ∩ A3 + A2 ∩ A3 − A1 ∩ A2 ∩ A3
= 78 - 36 - 28 - 15 + 6 + 1 + 0 – 0 = 6.
Có bao nhiêu số nguyên dương từ 1 ñến 1000 mà không chia
hết cho 2, không chia hết cho 3 và cũng không chia hết cho 7?
Giải.
Ký hiệu A ={1, 2, 3,…,1000}, A2 = {a ∈ A / a không
chia hết cho 2}, A 3 = {a ∈ A / a không chia hết cho 3}, A 7 =
3.3. Sàng Eratosthenes
Nguyên lý bù trừ cũng có thể ñược dùng ñể tìm số các số
nguyên tố nhỏ hơn một số nguyên dương nào ñó. Cần nhớ rằng một
hợp số chia hết cho một số nguyên tố không lớn hơn căn bậc hai của
{a ∈ A / a không chia hết cho 7}. Khi ñó A \ ( A2 ∪ A3 ∪ A7 ) là tập
nó. Do ñó, ñể tìm các số nguyên tố không vượt quá 100 thì ñiều cần
tất cả các số từ 1 ñến 1000 mà không chia hết cho 2, không chia hết
chú ý ñầu tiên là một hợp số nhỏ hơn 100 phải có một thừa số nguyên
cho 3 và cũng không chia hết cho 7.
tố không lớn hơn 10. Vì nhỏ hơn 10 chỉ có các số nguyên tố là 2, 3,
5, 7, nên các số nguyên tố không vượt quá 100 gồm bốn số nguyên tố
Theo nguyên lý bao hàm và loại trừ , ta có
A \ ( A 2 ∪ A3 ∪ A 7 ) = A − A 2 ∪ A3 ∪ A 7
= 1000 -714 =286
3.2. Bài toán xác ñịnh số nghiệm nguyên của một phương
trình với một số ràng buộc nào ñó
Phương trình x1 + x2 + x3 = 11 có bao nhiêu nghiệm, trong
ñó x 1 , x 2 và x 3 là các số nguyên không âm với x1 ≤ 3 , x2 ≤ 4 và
x3 ≤ 6?
Giải. Để áp dụng nguyên lý bao hàm và loại trừ, gọi tổng số
nghiệm là A ; nghiệm có tính chất A 1 là x1 > 3 , có tính chất A 2 là
trên và tất cả các số nguyên dương nhỏ hơn 100 không chia hết cho
2, 3, 5, 7. Để áp dụng nguyên lý bao hàm và loại trừ , ta gọi A1 là
tính chất chia hết cho 2, A2 là tính chất chia hết cho 3, A3 là tính
chất chia hết cho 5, A4 là tính chất chia hết cho 7. Vậy số nguyên tố
không vượt quá 100 là
A1 ∩ A2 ∩ A3 ∩ A4 + 4 = 21 + 4 = 25
Do ñó có 25 số nguyên tố không vượt quá 100.
3.4. Bài toán ñếm số các số nguyên dương nhỏ hơn số
nguyên dương n và nguyên tố cùng nhau với n ( ϕ - hàm Euler)
Hai số nguyên ñược gọi là nguyên tố cùng nhau nếu chúng
không có ước số chung khác 1. Với mỗi số nguyên dương n, ký hiệu
18
17
bằng ϕ ( n) số các số nguyên dương nhỏ hơn hoặc bằng n mà nguyên
tố cùng nhau với n. Hàm ϕ ( n) ñược gọi là ϕ - hàm Euler.
Giả sử kí hiệu D n là số mất thứ tự của một tập có n phần tử.
Bây giờ ta xét bài toán sau:
Bài toán: Hãy tính giá trị của ϕ ( n) theo n.
Giải. Giả sử n =
p1α1 p2α2 ... pk αk
Bài toán: Hãy tìm số mất thứ tự của một tập có n phần tử.
là phân tích chính tắc của n
Giải . Giả sử A là tập tất cả các hoán vị của tập X,
Ai = {a ∈ A / xi là ñiểm bất ñộng của a}. Khi ñó A\ ( A1 ∪ ... ∪ An )
thành tích các thừa số nguyên tố, ở ñây α1 , α 2 ,..., α k là các số
là tập tất cả các hoán vị của x mà không có ñiểm bất ñộng nào. Theo
nguyên dương. Ta cũng giả sử A = {1, 2, …,n}, A pi = {a ∈ A / a
nguyên lý bao hàm và loại trừ , ta có
A1 ∪... ∪ An =
chia hết cho p i }, i = 1, 2, …,k. Khi ñó
n
n
Api = , Api ∩ Ap j =
(i ≠ j ),...
pi
pi p j
1
k
1
1≤i ≤n
i
D n = A \ ( A1 ∪ ... ∪ An ) = A − A1 ∪ ... ∪ An
1
1 1 1
= n !1 − + − + ... + (−1) n
n!
1! 2! 3!
k
n
n
n
n
n
= n − + ... + −
− ... −
+ ... + (−1)k +1
p
p
p
p
p
p
p
p
k
1 2
k −1 k
1 2... pk
1
1 1 1
= n 1− 1− ....1−
p1 p2 pk
3.5. Bài toán tìm số xáo trộn của một hoán vị có n phần tử
Trước tiên ta lưu ý: Cho tập hợp có n phần tử. Khi ñó mỗi
hoán vị của n phần tử trên sao cho không có phần tử nào ở nguyên vị
trí ban ñầu ñược gọi là một xáo trộn của tập n phần tử ñã cho. Số tất
cả các xáo trộn ñược gọi là số mất thứ tự.
Ví dụ hoán vị 21453 là một xáo trộn của 12345 vì không có số
3.6. Bài toán bỏ thư. Có n lá thư và n phong bì ghi sẵn ñịa chỉ.
Bỏ ngẫu nhiên các thư vào các phong bì sao cho mỗi phong bì chỉ
chứa một thư.
a) Hỏi xác suất ñể không lá thư nào ñúng ñịa chỉ bao nhiêu ?
b) Hỏi xác suất ñể ñúng r lá thư ñúng ñịa chỉ là bao nhiêu
(r ≤ n )
?
Sử dụng nguyên lý bao hàm và loại trừ, ta có
a) Xác suất cần tìm là 1 −
nào ở nguyên vị trí ban ñầu của nó. Tuy nhiên, 21543 không phải là
một xáo trộn của 12345 vì hoán vị này ñể số 4 ở nguyên vị trí ban
ñầu của nó.
1≤i < j ≤n
Ai ∩ Aj + ... + (−1)n+1 A1 ∩... ∩ An ,
Vậy
Áp dụng nguyên lý bao hàm và loại trừ , ta ñược
ϕ ( n ) = A \ ( A p ∪ ... ∪ A p ) = A − A p ∪ ... ∪ A p
∑A− ∑
b) Xác suất cần tìm là
1 1 1
1
+ − + ... + (−1)n
1! 2! 3!
n!
1 1 1 1
(−1) n− r
1
−
+
−
+
...
+
r ! 1! 2! 3!
(n − r )!
20
19
3.7. Bài toán ñếm số các hàm toàn ánh.
Nguyên lý bù trừ cũng có thể ñược dùng ñể xác ñịnh số các
k ! S ( n, k ) =
Hãy ñếm số toàn ánh từ tập X vào tập Y.
Giải. Ký hiệu T là tập hợp tất cả các toàn ánh từ X vào Y.
Theo nguyên lý bao hàm và loại trừ , ta có
T
=
k
( − 1) r C ( k , r )( k − r ) n
∑
r =0
3.8. Bài toán xếp n cặp vợ chồng (Lucas)
Một bàn tròn có 2n ghế. Cần sắp n cặp vợ chồng sao cho ñàn
r
C ( k , r )( k − r ) n ⇒ S ( n , k ) =
r =0
1 k
∑ ( − 1) r C ( k , r )( k − r ) n
k ! r=0
3.10. Một số bài toán sử dụng nguyên lý bao hàm và loại
hàm toàn ánh từ tập có n phần tử ñến tập có k phần tử.
Bài toán: Cho hai tập hợp X và Y có X = n , Y = k , n ≥ k .
k
∑ ( − 1)
trừ trong kỳ thi Olympic quốc tế, thi học sinh giỏi quốc gia và tạp
chí toán học tuổi trẻ.
Bài 1
{ x1 , x2 , , ... , xn } của
Một hoán vị
{1, 2, ... , 2n} với
tập hợp
n nguyên dương, ñược gọi là có tính chất P nếu
xi − xi +1 = n , với ít nhất một giá trị i ∈ {1, 2, ... , 2 n − 1} . Chứng
minh rằng với mỗi số n, số hoán vị có tính chất P lớn hơn số hoán vị
không có tính chất P.
{1, 2, ... , n, n + 1, n + 2, ... ,2 n} .
Giải. Đặt M =
ông ngồi xen kẽ ñàn bà và không có cặp vợ chồng nào ngồi cạnh
Lưu ý
nhau (có tính ñến vị trí ghế và thứ tự chỗ ngồi). Hỏi có bao nhiêu
1 − ( n + 1) = n và 2 − ( n + 2 ) = n . Gọi
cách xếp?
của M sao cho trong các hoán vị ñó, hai phần tử k và k + n ñứng kề
Giải. Gọi số phải tìm là M n . Theo nguyên lý bao hàm và loại
nhau. Gọi A là tập tất cả các hoán vị có tính chất P. Ta thấy
A = U Ak nên
trừ, ta có.
n
M n = 2.n !.∑ (−1)
k =0
k
k
2n
C (2n − k , k ).(n − k )!
2n − k
A =
UA
k
k
3.9. Bài toán tính số Sterling loại 2
Bài toán: Tính số Sterling loại hai S ( n, k ) qua n và k.
Giải.
Ak là tập tất cả các hoán vị
Mỗi phân hoạch k khối của tập X có n phần tử có thể
=
∑A
k
−
(không kể thứ tự) sao cho thùng nào cũng có phần tử của X. Hoán vị
các thùng B1 ,..., Bk , ta thấy một phân bố như vậy sẽ sinh k! hàm
toàn ánh từ tập X vào tập { B1 ,..., Bk } . Suy ra
k
∩ Ah +
∑
k
( 2n )!
Y = {( x, y, z ) y ∈ D , x ∈ E , z ∈ E , x + y + z M m} ,
2
Z = {( x, y, z ) z ∈ D , x ∈ E , y ∈ E , x + y + z M m} ,
Bài 2 Cho hai số nguyên dương m và n sao cho n + 2 chia hết
Khi ñó C = X ∪ Y ∪ Z . Do ñó
cho m. Hãy tính các bộ ba số nguyên dương ( x , y, z ) sao cho tổng
x + y + z chia hết cho m, trong ñó mỗi số x, y, z ñều không lớn hơn
C = X + Y + Z − X ∩Y − X ∩ Z − Y ∩ Z + X ∩Y ∩ Z
Tương tự X = Y = Z = 2k 2 m ,
n.
Giải. Đặt k =
n+2
∈ N * . Ta có n = km – 2.
m
X ∩ Y = X ∩ Z = Y ∩ Z = 4k,
24 −m khi m = 1, 2, 3
X ∩ Y ∩ Z = τ (m) =
khi m > 3
1
Xét các tập hợp:
D = {km − 1, km} ; E = {1, 2,..., km} ;
Do ñó C = 6 k 2 m − 12k + τ ( m ) . Thay k =
A = {( x, y, z ) x, y, z ∈ E \ D; x + y + z M m} ;
B = {( x , y, z ) x, y, z ∈ E; x + y + z M m} ;
C = {( x , y, z ) x, y, z ∈ E; x ∈ D
hoặc
A = B − C =
y∈D
hoặc
z ∈ D; ; x + y + z M m} .
Ta có A = B − C
• Tính B . Có km cách chọn x ∈ E. Với mỗi cách chọn x ∈
E, ta có km cách chọn y ∈ E. Với mỗi cách chọn x và y như trên, ta
có k cách chọn z ∈ E sao cho x + y + z M m. Do ñó B = km.km.k =
k 3 m2 .
• Tính C . Đặt
X = {( x, y, z ) x ∈ D , y ∈ E , z ∈ E , x + y + z M m} ,
( ∗)
n+2
ñược
m
n3 + 8
− τ ( m ) với τ ( m ) xác ñịnh bởi ( ∗)
m
Bài 3 (VMO-1995, Bảng B). Hỏi từ các số 1, 2, 3, 4, 5 có thể
lập ñược bao nhiêu số có 10 chữ số thỏa mãn ñồng thời các ñiều kiện
sau:
1) Trong mỗi số, mỗi chữ số có mặt ñúng hai lần;
2) Trong mỗi số, hai chữ số giống nhau không ñứng cạnh nhau ?
Giải. Gọi s là số cần tìm và A là tập gồm tất cả các số có 10
chữ số, lập ñược từ các chữ số 1, 2, 3, 4, 5 thỏa mãn ñiều kiện 1 của
ñề bài. Khi ñó, theo nguyên lý bao hàm và loại trừ ta tính ñược:
A =
s=
10!
25
10!
9!
8!
7!
6! 5!
− C51 4 + C52 3 − C53 2 + C54 1 − 0 = 39480
5
2
2
2
2
2 2
24
23
167
Bài 4 Một cuộc hội thảo toán học quy tụ 1990 nhà toán học
(1) ∑ | Ai | = 2004;
trên toàn thế giới. Cho biết cứ mỗi nhà toán học ñều ñã có dịp làm
i =1
chung với 1327 nhà toán học khác tham dự hội thảo. Chứng minh
rằng ta có thể tìm ñược 4 nhà toán học từng ñôi một ñã làm việc
(2)
A j = Ai Ai ∩ A j với mọi i, j ∈ {1, 2, ....,167} và i
Tính
UA
≠ j
chung với nhau.
167
Giải. Mỗi nhà toán học ñược xem như là một ñiểm. Hai nhà
i =1
toán học ñã làm việc chung với nhau xem như 2 ñiểm ñược nối với
i
.
nhau bởi một ñoạn thẳng. Lý luận tương tự như bài toán trên ñây, gọi
Giải.
v1 và v2 là 2 ñiểm ñược nối với nhau. Gọi A là tập hợp các ñiểm
• Ta có Aj = Ai . A j ∩ Ai ; Ai = Aj . Ai ∩ Aj
khác v 2 ñược nối với v 1 và B là tập hợp các ñiểm khác v 1 ñược nối
Suy ra Ai = Ai . Ai ∩ A j
với v 2 . Lúc ñó:
Nếu Ai = 0 thì từ ( 2 ) suy ra A j = 0, ∀j ≠ i . Điều này
A ∩ B = A + B − A ∪ B = 2 × 1326 − 1998 = 664
Nghĩa là ta có thể tìm ñược nhà toán học v3 ñã làm việc chung
với v1 và v 2 . Gọi C là tập hợp các ñiểm ñược nối với v 3 nhưng
không nối với v1 và v 2 . Ta có C ≥ 1325 , vậy
1998 ≥ ( A ∩ B ) ∪ C = A ∩ B + C − A ∩ B ∩ C
Nghĩa là
A ∩ B ∩ C ≥ A ∩ B + C − 1998 ≥ 664 + 1325 − 1988 = 1 > 0
Vậy A ∩ B ∩ C ≠ ∅ và ta tìm ñược v4 ∈ A ∩ B ∩ C . Tập
hợp gồm 4 nhà toán học v1 , v2 , v3 , v4 ñã làm việc với nhau từng ñôi
một và ñó là ñpcm.
Bài 5 Cho 167 tập hợp A1 , A2 , ... A167 thỏa mãn các ñiều kiện
sau:
2
mâu thuẫn với (1). Vậy Ai ≠ 0 .
Do ñó Ai ∩ A j = 1
( i ≠ j ) và
Ai = Aj .
Do ñó Ai = 12, ∀i
• Xét tập A 1 . Mỗi tập A2 , ... , A167 ñều chứa và chỉ chứa 1
phần tử của A 1 . Không giảm tổng quát giả sử 14 tập A2 , ... , A15
cùng chứa phần tử a ∈ A1 . Ta sẽ chứng minh a ∈ Ai , ∀i .
Thật vậy, giả sử tồn tại i > 15; a ∉ Ai . Đặt Bi = Ai \ {a}
Khi ñó với mỗi A j
( j = 2, ... 15)
ta có A j ∩ Ai = 1 do ñó
Aj ∩ Bi = 1 . Giả sử A j ∩ Bi = bj . Ta có b j1 ≠ b j2 vì nếu
26
25
b j1 = b j2 thì hai tập hợp A j1 và A j2 có 2 phần tử chung là a và b j1
KẾT LUẬN
trái với Ai ∩ A j = 1 .
Đề tài nguyên lý bao hàm & loại trừ và ứng dụng bước ñầu ñã
Như vậy b2 , ..., b15 là 14 phần tử thuộc Ai . Điều này không
hệ thống hóa ñược một mảng kiến thức về giải các bài toán tổ hợp từ
xảy ra vì Ai = 12.
những dạng cơ bản ñến phức tạp hơn. Thông qua nghiên cứu lý
Vậy với mọi i ≠ j ta có Ai ∩ A j = {a} .
thuyết về nguyên lý bao hàm và loại trừ, ñề tài ñã ứng dụng trong
Đặt Bi = Ai \ {a} với mọi i thì Bi ∩ B j = ∅ với mọi i, j mà
việc giải các bài toán tổ hợp có liên quan. Đặc biệt là những bài toán
i ≠ j . Do vậy:
Từ nguyên lý bao hàm và loại trừ ta có thể giải ñược lớp các
167
UA
i =1
ứng dụng phương pháp sử dụng nguyên lý bao hàm và loại trừ.
i
=
167
UB
i =1
i
∩ {a} =
167
∑B
i =1
i
+ {a} = 167.11 + 1 = 1838
bài toán có nhiều ứng dụng trong thực tiễn, ñời sống.
Bằng cách thay ñổi các tập hợp, số lượng tập hợp và quan hệ
giữa các phần tử ta có thể tạo ra nhiều bài toán khác nhau về nguyên
lý bao hàm và loại trừ mà việc giải chúng giúp học sinh rèn luyện
việc sử dụng linh hoạt các cấu hình tổ hợp cơ bản và mở rộng.
Hơn nữa ñề tài cũng có hướng mở ñể tiếp tục nghiên cứu ứng
dụng trong giải các bài toán phức tạp và các bài toán ứng dụng trong
lĩnh vực tin học. Đây là một vấn ñề nghiên cứu khá hay, trong thời
gian ñến tôi sẽ tiếp tục dành thời gian cho việc nghiên cứu vấn ñề
này.
- Xem thêm -