Professional Documents
Culture Documents
Chương 3
NGUYÊN LÝ BÙ TRỪ
lvluyen @ hcmus.edu.vn
http://bit.do/toantohop
FB: http://bit.do/fbtoantohop
2. Nguyên lý bù trừ
3. Đa thức quân xe
Ta ký hiệu
Khi đó
Giải. Gọi là U là tập hợp sinh viên của trường. Gọi A là tập hợp sinh
viên học tiếng Anh và P là tập hợp sinh viên học tiếng Pháp. Ta có
N = N (U) = 100, N (A) = 50, N (P ) = 40 và N (A ∩ P ) = 20.
Theo yêu cầu bài toán ta cần tính N (A ∩ P ). Ta có
N (A ∩ P ) = N − N (A) − N (P ) + N (A ∩ P )
= 100 − 50 − 40 + 20 = 30.
Câu hỏi. Hãy mở rộng công thức (1) cho trường hợp 3 tập hợp.
Ví dụ. Một trường có 100 sinh viên, trong đó có 40 sinh viên học tiếng
Anh, 40 sinh viên học tiếng Pháp, 40 sinh viên học tiếng Đức, mỗi cặp
ngôn ngữ có 20 sinh viên học và có 10 sinh viên học cả 3 ngôn ngữ. Hỏi
trường có bao nhiêu sinh viên không học cả 3 tiếng Anh, Pháp và Đức?
Giải. Gọi U là tập hợp sinh viên của trường. Gọi A là tập hợp sinh
viên học tiếng Anh, P là tập hợp sinh viên học tiếng Pháp và D là tập
hợp sinh viên học tiếng Đức. Khi đó N = 100,
• N (A) = N (P ) = N (D) = 40,
• N (A ∩ P ) = N (P ∩ D) = N (A ∩ D) = 20,
• N (A ∩ P ∩ D) = 10.
Theo công thức (2) ta được
N (A ∩ P ∩ D) = 100 − (40 + 40 + 40) + (20 + 20 + 20) − 10 = 30.
lvluyen @ hcmus.edu.vn Chương 3. Nguyên lý bù trừ Tháng 9 - 2018 6/35
Nhận xét. Số các số nguyên dương ≤ n mà chia hết cho k là phần
nguyên [n/k] .
Ví dụ. Có bao nhiêu số nguyên dương nhỏ hơn 1000 mà chia hết cho 7?
h 999 i
Đáp án. = 142
7
Giải. Gọi U là tập hợp các số nguyên dương ≤ 1000. Ta có ước nguyên
tố của 70 là 2, 5 và 7. Do đó muốn đếm các số nguyên tố cùng nhau với
70 ta cần đếm những số không chia hết cho 2, 5 và 7.
Gọi A1 , A2 và A3 lần lượt là tập các số nguyên trong U chia hết cho 2, 5
và 7. Khi đó đáp án cần tìm của bài toán là N (A1 ∩ A2 ∩ A3 ). Ta có
Ta có một số chia hết cho 2 và 5 khi và chỉ khi số đó chia hết cho
10. Do đó N (A1 ∩ A2 ) = [1000/10] = 100.Tương tự ta có,
1000 1000
N (A1 ∩ A3 ) = = 71, N (A2 ∩ A3 ) = = 28.
2×7 5×7
1000
N (A1 ∩ A2 ∩ A3 ) = = 14.
2×5×7
Áp dụng công thức (2) ta được
a) N (A1 A2 A3 A4 ) = N − S1 + S2 − S3 + S4 = 8682544.
b) N (A1 ∪ A2 ∪ A3 ∪ A4 ) = S1 − S2 + S3 − S4 = 11675976.
x1 + x2 + x3 + x4 = 20 (∗)
Ví dụ. Có bao nhiêu toàn ánh từ tập hợp có 6 phần tử vào tập hợp có
3 phần tử?
lvluyen @ hcmus.edu.vn Chương 3. Nguyên lý bù trừ Tháng 9 - 2018 13/35
Giải. Giả sử tập nguồn là A, tập đích là B = {b1 , b2 , b3 }. Gọi U là tập
hợp các ánh xạ từ A vào B và Pi là tập hợp các ánh xạ mà có ảnh
không chứa bi (với i = 1, 2, 3). Khi đó kết quả của bài toán là
N (P 1 P 2 P 3 ).
Bằng việc giải những bài toán tìm số ánh xạ ta được
Giải. Gọi U là tập hợp tất cả những chuỗi tam phân có độ dài 4. Gọi
Ai là tập hợp tất cả các chuỗi tam phân có chữ số tại vị trí i là 1. Ta có
N = 34 S3 =
4
31
4 3 3
S1 = 3
1
4 2 4
S2 = 3 S4 = 30
2 4
Giải. Gọi Ai là tập hợp các cách bỏ 5 lá thư vào 5 phong bì thư sao
cho lá thư thứ i đúng địa chỉ. Bây giờ ta đi tìm N (A1 A2 . . . A5 ). Ta có
N = 5! 5 5!
S3 = 2! =
5 5! 3 3!
S1 = 4! =
1 1! 5 5!
S4 = 1! =
4 4!
5 5!
S2 = 3! =
5 5!
2 2! S5 = 0! =
5 5!
Tổng quát.
n
X (−1)k
N (A1 A2 . . . An ) = n!
k!
k=0
Xác suất
n
N (A1 A2 . . . An ) X (−1)k
= ≈ e−1 (khi n lớn)
N k!
k=0
lvluyen @ hcmus.edu.vn Chương 3. Nguyên lý bù trừ Tháng 9 - 2018 18/35
3.3. Đa thức quân xe
Giới thiệu. Xe là một quân cờ quan trọng trong cờ tướng cũng như cờ
vua, nó có quyền ăn bất cứ quân cờ nào khác màu (của đối phương) ở
trên cùng dòng hay cùng cột (không bị cản trở bởi một quân cờ
khác). Một số bài toán đếm có thể đưa về dạng tính số cách đặt k quân
xe trên một bàn cờ sao cho hai quân xe bất kỳ không thể ăn nhau, tức
là không có 2 quân xe nào trên cùng một dòng hay một cột.
Định nghĩa. Tập hợp tất các hoán vị của {1, 2, . . . , n} được ký hiệu là
Sn . Mỗi hoán vị của σ ∈ Sn được xem như là một song ánh từ
{1, 2, . . . , n} vào {1, 2, . . . , n}. Ví dụ, hoán vị σ = 3 2 1 được xem như
là song ánh σ : {1, 2, 3} → {1, 2, 3} với σ(1) = 3, σ(2) = 2, σ(3) = 1.
Nhận xét. Một hoán vị σ ∈ Sn tương đương với một cách đặt n quân
xe trên bàn cờ n × n ở các tọa độ (i, σ(i)) (với 1 ≤ i ≤ n), hiển nhiên
không có 2 quân xe nào ăn nhau.
lvluyen @ hcmus.edu.vn Chương 3. Nguyên lý bù trừ Tháng 9 - 2018 19/35
Ví dụ. Hoán vị σ = 4 2 3 1 tương đương với cách đặt quân xe
P (X1 , X2 , . . . , Xn ) = {σ ∈ Sn | σ(i) ∈
/ Xi }.
Tập Xi được gọi là tập các vị trí cấm của i. Các hoán vị thuộc
P (X1 , . . . , Xn ) được gọi là hoán vị với vị trí cấm.
Ta dễ thấy một cách phân công mỗi người với một công việc thích hợp
chính là một cách đặt 4 quân xe vào bàn cờ.
Để đơn giản ta có thể xóa các ô cấm ra khỏi bàn cờ. Như vậy bàn cờ
trên sẽ thành
Nhận xét. Việc hoán vị các dòng hay các cột trên bàn cờ không ảnh
hưởng đến kết quả của đa thức quân xe.
lvluyen @ hcmus.edu.vn Chương 3. Nguyên lý bù trừ Tháng 9 - 2018 23/35
Ví dụ. Cho C là bàn cờ 2 × 2
Khi đó, ta có 4 cách đặt một quân xe, 2 cách đặt hai quân xe và không
có cách đặt ba quân xe trở lên. Do đó đa thức quân xe của C là
R(C, x) = 1 + 4x + 2x2 .
4
r3 (C) = × 4 × 3 × 2 = 96.
3
4
r4 (C) = × 4 × 3 × 2 × 1 = 24.
4
Vậy
R(C, x) = 1 + 16x + 72x2 + 96x3 + 24x4 .
Định lý. Nếu bàn cờ C chỉ gồm hai phần rời nhau A và B thì
Từ hệ thức này ta có
!
= x(1 + 2x) + R ,x ×R ,x
Định lý. Cho P (X1 , . . . , Xn ) là tập các hoán vị σ ∈ Sn với vị trí cấm
X1 , . . . , Xn . Gọi B là bàn cờ được tạo từ các vị trí cấm này. Khi đó số
hoán vị này là Xn
(−1)k (n − k)! rk (B).
k=0
××
×
× ××
× ×
Hoán vị dòng 1 với dòng 4 và cột 1 với cột 5, ta được
××
×
×××
××
lvluyen @ hcmus.edu.vn Chương 3. Nguyên lý bù trừ Tháng 9 - 2018 31/35
Gọi B là bàn cờ được tạo bởi các ô cấm, ta có
= (1 + 3x + x2 )(1 + 5x + 4x2 )
= 1 + 8x + 20x2 + 17x3 + 4x4 .
Theo định lý trên ta có số hoán vị với vị trí cấm là
5
X
(−1)k (5 − k)! rk (B)
k=0
= 5! × 1 − 4! × 8 + 3! × 20 − 2! × 17 + 1! × 4 − 5! × 0 = 18
lvluyen @ hcmus.edu.vn Chương 3. Nguyên lý bù trừ Tháng 9 - 2018 32/35
Ví dụ.(tự làm) Ta cần bố trí 4 người A, B, C, D vào 4 trong 5 công
việc 1, 2, 3, 4, 5. Biết rằng A không thích hợp với công việc 2 và 5; B
không thích hợp với 5; C không thích hợp với 3; D không thích hợp với
1, 3 và 4. Hỏi có bao nhiêu cách phân công mỗi người với một công việc
thích hợp?
Hướng dẫn. Ta thêm vào người E và người này thích hợp với mọi công
việc. Khi đó bài toán đưa về việc tìm số cách phân công 5 người cho 5
công việc. Đây cũng chính là bài toán tìm số hoán vị với vị trí cấm.
Bàn cờ 5 × 5 với ô cấm
Hướng dẫn. Đặt A0 = A ∪ {5, 6}. Xét bài toán tìm tất cả các đơn ánh
từ A0 → B không thỏa các điều kiện trên. Vì mỗi các xây dựng đơn
ánh từ A → B ta được 2! các xây dựng đơn ánh từ A0 → B (vì có 2!
các chọn ảnh của 5 và 6).
Bài toán tìm số đơn ánh từ A0 → B chính là bài toán tìm số hoán vị
với vị trí cấm.
lvluyen @ hcmus.edu.vn Chương 3. Nguyên lý bù trừ Tháng 9 - 2018 34/35
Đáp án. Đa thức quân xe: R(C, x) = 1 + 8x + 21x2 + 20x3 + 4x4
Khi đó, số đơn ánh từ A0 → B thỏa điều kiện là
6
X
(−1)k (6 − k)! rk (C) = 152.
k=0
152
Như vậy số đơn ánh từ A → B thỏa điều kiện bài toán là = 76.
2!
Ví dụ.(tự làm) Một xáo trộn (derangement) là một hoán vị các phần
tử của tập hợp sao cho không có phần tử nào xuất hiện đúng vị trí ban
đầu. Ví dụ A = {1, 2, 3, 4, 5}, khi đó 21453 là một xáo trộn, nhưng
21543 không là một xáo trộn vì 4 trùng với vị trí ban đầu. Hãy
a) tìm số xáo trội của các phần tử của tập hợp A = {1, 2, 3, 4, 5, 6, 7};
b) tìm số xáo trội của các phần tử của tập hợp A = {1, 2, . . . , n} với
n là nguyên dương.