Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác

Bài giảng Toỏn tổ hợp
Đại học Khoa học Tự nhiờn, Tp HCM
Bài giảng Toỏn tổ hợp 1/34
Nội dung chương 3
Nội dung
Chương 3. MỘT SỐ KỸ THUẬT ĐẾM KHÁC
1. Sử dụng sơ đồ Ven
2. Nguyờn lý bự trừ
3. Đa thức quõn xe
Bài giảng Toỏn tổ hợp 2/34
3.1. Sử dụng sơ đồ Ven
3.1.Sử dụng sơ đồ Ven
Xột sơ đồ Ven
Ta ký hiệu
U là tập vũ trụ
A là phần bự của A trong U
N(A) là số phần tử của A.
N = N(U)
Khi đú N(A ∩B) = N −N(A)−N(B) +N(A ∩B) (1)
Bài giảng Toỏn tổ hợp 3/34
3.1. Sử dụng sơ đồ Ven
Vớ dụ. Một trường học cú 100 sinh viờn, trong đú cú 50 sinh viờn học
tiếng Anh, 40 sinh viờn học tiếng Phỏp và 20 sinh viờn học cả tiếng
Anh và tiếng Phỏp. Hỏi cú bao nhiờu sinh viờn khụng học tiếng Anh
lẫn khụng học tiếng Phỏp?
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 chỳng 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
Bài giảng Toỏn tổ hợp 4/34
3.1. Sử dụng sơ đồ Ven
Vớ dụ. Cú bao nhiờu hoỏn vị cỏc chữ số 0, 1, 2, . . . , 9 sao cho chữ số
đầu lớn hơn 1 và chữ số cuối nhỏ hơn 8?
Giải. Gọi U là tập tất cả cỏc hoỏn vị của 0, 1, 2, ..., 9; A là tập tất cả
cỏc hoỏn vị với chữ số đầu là 0 hoặc 1 và B là tập tất cả cỏc hoỏn vị với
chữ số cuối là 8 hoặc 9. Khi đú yờu cầu của bài toỏn là tớnh N(A ∩B).
Ta cú N = 10!, N(A) = 2ì 9!, N(B) = 2ì 9!, N(A ∩ P ) = 2ì 2ì 8!.
Áp dụng cụng thức (1) ta được
N(A ∩B)= N −N(A)−N(B) +N(A ∩B)
= 10!− (2ì 9!)− (2ì 9!) + (2ì 2ì 8!) = 2338560
Bài giảng Toỏn tổ hợp 5/34
3.1. Sử dụng sơ đồ Ven
Cõu hỏi. Nếu ta mở rộng cụng thức (1) cho trường hợp 3 tập hợp thỡ
như thế nào?
Đỏp ỏn. Khi đú cụng thức là
N(A ∩B ∩ C) =N −N(A)−N(B)−N(C)
+N(A ∩B) +N(A ∩ C) +N(B ∩ C)
−N(A ∩B ∩ C) (2)
Bài giảng Toỏn tổ hợp 6/34
3.1. Sử dụng sơ đồ Ven
Đối với trường hợp 3 tập hợp là A1, A2, A3, ta cú thể viết cụng thức
(2) như sau:
N(A1 ∩A2 ∩A3) = N −
∑
i
N(Ai)+)
∑
i 6=j
N(Ai ∩Aj)−N(A1 ∩A2 ∩A3)
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
cú bao nhiờu sinh viờn khụng học cả 3 tiếng Anh, Phỏp và Đức?
Giải. Ta cú N = 100, N(A) = N(P ) = N(D) = 40, N(A ∩ P ) =
N(P ∩D) = N(A ∩D) = 20, và 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.
Vớ dụ. Cú bao nhiờu số nguyờn dương ≤ 70 mà nguyờn tố cựng nhau
với 70?
Bài giảng Toỏn tổ hợp 7/34
3.1. Sử dụng sơ đồ Ven
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.
Giải. Gọi U là tập hợp cỏc số nguyờn dương ≤ 70. 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 hoặc 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ú
N = 70, N(A1) = 70/2 = 35,
N(A2) = 70/5 = 14, N(A3) = 70/7 = 10
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) = 70/10 = 7. Tương tự ta cú,
N(A2 ∩A3) = 70
5ì 7 = 2, N(A1 ∩A3) =
70
2ì 7 = 5.
Bài giảng Toỏn tổ hợp 8/34
3.1. Sử dụng sơ đồ Ven
N(A1 ∩A2 ∩A3) = 70
2ì 5ì 7 = 1.
Áp dụng cụng thức (2) ta cú
N(A1 ∩A2 ∩A3) = 70− (35 + 14 + 10) + (7 + 2 + 5)− 1 = 24.
Vớ dụ. Cú bao nhiờu số nguyờn dương ≤ 1000 mà nguyờn tố cựng
nhau với
a) 50 b) 210
Bài giảng Toỏn tổ hợp 9/34
3.2. Nguyờn lý bự trừ
3.2. Nguyờn lý bự trừ
Trong phần này chỳng ta sẽ mở rộng cụng thức ở phần 1 cho trường
hợp n tập hợp A1, A2, . . . , An. Để đơn giản về mặt ký hiệu chỳng ta
viết “ ∩ ” như là phộp nhõn. Vớ dụ A1 ∩A2 ∩A3 sẽ được viết thành
A1A2A3. Bằng việc sử dụng ký hiệu này, ta cú số lượng phần tử khụng
thuộc tất cả cỏc tập A1, A2, . . . , An sẽ được viết là N(A1A2 . . . An).
Định lý. Cho tập vũ trụ U cú N phần tử và A1, A2, . . . , An là n tập
hợp con của U. Ta đặt Sk là tổng số phần tử của tất cả tập giao của
đỳng k tập hợp từ cỏc {Ai}i=1,...,n, cụ thể
S1 =
∑
i
N(Ai), S2 =
∑
i 6=j
N(AiAj), . . . , Sn = N(A1A2 . . . An).
Khi đú
N(A1A2 . . . An) = N +
∑
k
(−1)kSk
= N − S1 + S2 − . . .+ (−1)kSk + . . .+ (−1)nSn
Bài giảng Toỏn tổ hợp 10/34
3.2. Nguyờn lý bự trừ
Hệ quả. Cho A1, A2, . . . , An là n tập hợp con của tập vũ trụ U. Khi đú
N(A1 ∪ . . . ∪An) =
∑
k≥1
(−1)k−1Sk
= S1 − S2 + . . .+ (−1)k−1Sk + . . .+ (−1)n−1Sn
Chứng minh. Từ Định lý trờn ta cú
N(A1 . . . An) = N − S1 + S2 − . . .+ (−1)kSk + . . .+ (−1)nSn
= N −
(
S1 − S2 + . . .+ (−1)k−1Sk + . . .+ (−1)n−1Sn
)
.
Mặt khỏc N(A1 ∪ . . . ∪An) = N −N(A1 . . . An).
Do đú ta cú điều phải chứng mỡnh
Vớ dụ. Tỡm số nghiệm nguyờn khụng õm của phương trỡnh
x1 + x2 + x3 + x4 = 18 (∗)
thỏa điều kiện xi ≤ 7, ∀i = 1, . . . , 4.
Bài giảng Toỏn tổ hợp 11/34
3.2. Nguyờn lý bự trừ
Giải. Gọi U là tập hợp cỏc nghiệm nguyờn khụng õm của phương trỡnh
(∗). Ta cúN = N(U) = K184 =
(
4 + 18− 1
18
)
= 1330.
Gọi Ai là tập hợp cỏc nghiệm nguyờn khụng õm của phương trỡnh (∗)
thỏa tớnh chất xi ≥ 8. Khi đú kết quả của bài toỏn là N(A1A2A3A4).
Bằng việc giải những bài toỏn tỡm số nghiờm nguyờn ta được
N(Ai) = K
10
4 =
(
13
10
)
N(AiAjAk) = 0
N(AiAj) = K
2
4 =
(
5
2
)
N(A1A2A3A4) = 0
Vỡ vai trũ của cỏc Ai (1 ≤ i ≤ 4) như nhau nờn ta cú:
S1 =
∑
iN(Ai) = 4
(
13
10
)
= 1144
S2 =
∑
i 6=j N(AiAj) =
(
4
2
)(
5
2
)
= 60
S3 = 0, S4 = 0
Bài giảng Toỏn tổ hợp 12/34
3.2. Nguyờn lý bự trừ
Áp dụng Định lý, ta cú
N(A1A2A3A4) = N − S1 + S2 − S3 + S4
= 1330− 1144 + 60− 0 + 0 = 246
Vớ dụ. Cú bao nhiờu cỏch lấy 6 lỏ bài từ bộ bài 52 lỏ sao cho
a) cú đầy đủ 4 chất (cơ, rụ, chuồn, bớch).
b) ớt nhất một chất khụng cú
Giải. Gọi U là tất cả bộ 6 lỏ bài được lấy từ bộ bài và A1, A2, A3, A4
lần lượt là tất cả bộ 6 lỏ bài mà khụng cú chất cơ, rụ, chuồn và
bớch. Ta cú
N = N(U) =
(
52
6
)
N(A1) =
(
39
6
)
N(A1A2) =
(
26
6
)
N(A1A2A3) =
(
13
6
)
N(A1A2A3A4) = 0
Bài giảng Toỏn tổ hợp 13/34
3.2. Nguyờn lý bự trừ
Vỡ vai trũ A1, A2, A3, A4 giống nhau nờn ta cú
S1 = 4
(
39
6
)
S2 =
(
4
2
)(
26
6
) S3 =
(
4
3
)(
13
6
)
S4 = 0
a) N(A1A2A3A4) = N − S1 + S2 − S3 + S4 = 8682544
b) N(A1 ∪A2 ∪A3 ∪A4) = S1 − S2 + S3 − S4 = 11675976
Vớ dụ. Tỡm số nghiệm nguyờn khụng õm của phương trỡnh
x1 + x2 + x3 + x4 = 25 (∗)
thỏa điều kiện x1 ≤ 5, x2 ≤ 6, x3 ≤ 7.
Vớ dụ. Tỡm số nghiệm nguyờn khụng õm của phương trỡnh
x1 + x2 + x3 + x4 + x5 + x6 = 20 thỏa điều kiện xi ≤ 8 (i = 1, . . . 6)
Bài giảng Toỏn tổ hợp 14/34
3.2. Nguyờn lý bự trừ
Định lý. Cho tập vũ trụ U cú n phần tử và A1, A2, . . . An là n tập hợp
con của U. Khi đú số phần tử thuộc vào đỳng m tập hợp, ký hiệu Nm,
là
Nm =
n−m∑
i=0
(−1)i
(
m+ i
m
)
Sm+i
= Sm −
(
m+ 1
m
)
Sm+1 + . . .+ (−1)n−m
(
n
m
)
Sn
Nếu ta gọi N∗m là số phần tử thuộc ớt nhất m tập hợp thỡ
N∗m =
n−m∑
i=0
(−1)i
(
m+ i
m− 1
)
Nm+i
= Sm −
(
m
m− 1
)
Sm+1 + . . .+ (−1)n−m
(
n− 1
m− 1
)
Sn.
Bài giảng Toỏn tổ hợp 15/34
3.2. Nguyờn lý bự trừ
Vớ dụ. Cú bao nhiờu chuỗi tam phõn (chỉ gồm 0, 1, 2) độ dài 4 thỏa
món: a) chứa đỳng 2 chữ số 1 b) chứa nhiều hơn 2 chữ số 1
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
S1 =
(
4
1
)
33
S2 =
(
4
2
)
32
S3 =
(
4
3
)
31
S4 =
(
4
4
)
30
Áp dụng định lý trờn ta cú:
a) N2 = S2 −
(
3
2
)
S3 +
(
4
2
)
S4 = 24.
b) N∗2 = S2 −
(
2
1
)
S3 +
(
3
1
)
S4 = 33.
Bài giảng Toỏn tổ hợp 16/34
3.2. Nguyờn lý bự trừ
Vớ dụ. Cú 5 lỏ thư và 5 phong bỡ ghi sẵn địa chỉ. Bỏ ngẫu nhiờn cỏc lỏ
thư vào phong bỡ.
a) Hỏi xỏc xuất để khụng lỏ thư nào đỳng địa chỉ là bao nhiờu?
b) Hỏi xỏc xuất để đỳng 3 lỏ thư đỳng địa chỉ là bao nhiờu?
Sau đú tổng quỏt húa bài toỏn cho n và k ≤ n
Giải. Gọi Ai là tập cỏc cỏch bỏ 5 là thư vào 5 phong bỡ sao cho lỏ thứ
i đỳng địa chỉ. Bõy giờ ta đi tỡm N(A1A2 . . . A5).Ta cú
N = 5!
S1 =
(
5
1
)
4! =
5!
1!
S2 =
(
5
2
)
3! =
5!
2!
S3 =
(
5
3
)
2! =
5!
3!
S4 =
(
5
4
)
1! =
5!
4!
S5 =
(
5
5
)
0! =
5!
5!
Bài giảng Toỏn tổ hợp 17/34
3.2. Nguyờn lý bự trừ
Ta cú
N(A1A2 . . . A5) = N − S1 + S2 − S3 + S4 − S5
= 5!− 5!
1!
+
5!
2!
− 5!
3!
+
5!
4!
− 5!
5!
Bài giảng Toỏn tổ hợp 18/34
3.3. Đa thức quõn xe
Đa thức quõn xe
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 của đối phương ở trờn cựng dũng hoặc
cựng cột và khụng bị cản trở bởi 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ú hai quõn xe nào
ở cựng dũng hay cựng cột.
Định nghĩa. Tập hợp tất cả 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}
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), ta thấy khụng
cú hai quõn xe nào ăn nhau.
Bài giảng Toỏn tổ hợp 19/34
3.3. Đa thức quõn xe
Vớ dụ. Hoỏn vị σ = 4231 tương đương với cỏch đặt quõn xe
Định nghĩa. Xột cỏc tập con X1, X2, . . . , Xn ⊂ {1, 2, . . . , n}. Đặt
P (X1, X2, . . . , Xn) = {σ ∈ Sn|σ(i) /∈ Xi}.
Tập Xi được gọi là vị trớ cấm của i, cỏc hoỏn vị thuộc
P (X1, X2, . . . , Xn) được gọi là hoỏn vị với vị trớ cấm.
Bài giảng Toỏn tổ hợp 20/34
3.3. Đa thức quõn xe
Vớ dụ. Cho X = {1, 2, 3, 4, 5} và cỏc tập con X1 = {3, 4}, X2 = {5},
X3 = {1, 3, 4}, X4 = {2, 5} và X5 = ∅. Tỡm số phần tử của tập hoỏn vị
với vị trớ cấm P (X1, X2, . . . , Xn)?
Nhận xột. Bài toỏn tương đương với bài toỏn tỡm số cỏch đặt 5 quõn
xe trờn bàn cờ 5ì 5 như hỡnh sau, trong đú cỏc ụ gạch chộo là ụ cấm
Trong phần này chỳng ta sẽ dựng phương phỏp đa thức quõn xe để giải
những bài toỏn dạng này.
Bài giảng Toỏn tổ hợp 21/34
3.3. Đa thức quõn xe
Vớ dụ. 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 biểu diễn 4 người và 5 cụng việc thành một bàn cờ
4ì 5 như hỡnh sau
Ta dễ thấy một cỏch phõn cụng mỗi người một cụng việc phự hợp
chớnh là một cỏch đặt 4 quõn xe vào bàn cờ.
Bài giảng Toỏn tổ hợp 22/34
3.3. Đa thức quõn xe
Để đơ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 nghĩa. Một bàn cờ là một tập con của mảng mì n ụ vuụng.
Vớ dụ. Cỏc ụ vuụng ở trờn là một bàn cờ.
Bài giảng Toỏn tổ hợp 23/34
3.3. Đa thức quõn xe
Định nghĩa. Cho C là một bàn cờ cú m ụ vuụng và k ≤ m. Gọi rk(C)
là cỏch đặt k quõn xe lờn bàn cờ sao cho 2 xe bất kỳ khụng thể ăn
nhau. Đa thức quõn xe được định nghĩa là
R(C, x) = r0(C) + r1(C)x+ r2(C)x
2 + ã ã ã+ rm(C)xm
Ta dễ thấy r0(C) = 1 và r1(C) = m.
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.
Vớ dụ. Cho C là bàn cờ 2ì 2
Bài giảng Toỏn tổ hợp 24/34
3.3. Đa thức quõn xe
Khi đú ta cú 4 cỏch đặt một quõn xe và 2 cỏch đặt hai quõn xe. Do đú
đa thức quõn xe của C là
R(C, x) = 1 + 4x+ 2x2.
Vớ dụ. Cho C là bàn cờ 4ì 4
Hóy tỡm đa thức quõn xe của C?
Bài giảng Toỏn tổ hợp 25/34
3.3. Đa thức quõn xe
Hướng dẫn. Ta cú r0(C) = 1, r1(C) = 16.
Với 2 quõn xe, ta cú C24 cỏch chọn vị trớ dũng đặt xe. Với mỗi cỏch
chọn dũng, quõn xe thứ 1 cú 4 cỏch chọn, quõn xe thứ 2 cú 3 cỏch
chọn. Như vậy,
r2(C) = C
2
4 .4.3 = 72.
Lý luận tương tự ta cú
r3(C) = C
3
4 .4.3.2 = 96.
r4(C) = C
4
4 .4.3.2.1 = 24.
Vậy
R(C, x) = 1 + 16x+ 72x2 + 96x3 + 24x4
Bài giảng Toỏn tổ hợp 26/34
3.3. Đa thức quõn xe
Định nghĩa. Hai phần A,B của bàn cờ C được gọi là rời nhau nếu
khụng cú ụ vuụng nào trong A cú cựng dũng hay cựng cột với một ụ
vuụng trong B
Vớ dụ. Hai phần A,B của bàn cờ sau là rời nhau
Định lý. Nếu bàn cờ C chỉ gồm hai phần rời nhau A và B thỡ
R(C, x) = R(A, x)ìR(B, x).
Bài giảng Toỏn tổ hợp 27/34
3.3. Đa thức quõn xe
Định lý. Cho a là ụ vuụng tựy ý của bàn cờ C. Gọi D là bàn cờ cú
được từ C bằng cỏch xúa dũng và cột chứa a, và E là bàn cờ cú được từ
C bằng cỏch xúa ụ a. Khi đú
R(C, x) = xR(D,x) +R(E, x).
Vớ dụ. Tỡm đa thức quõn xe của bàn cờ C sau
Bài giảng Toỏn tổ hợp 28/34
3.3. Đa thức quõn xe
Áp dụng định lý trờn ta được
Bài giảng Toỏn tổ hợp 29/34
3.3. Đa thức quõn xe
Vớ dụ. Tỡm đa thức quõn xe của bàn cờ sau
Đỏp ỏn. 1 + 8x+ 20x2 + 17x3 + 4x4
Định lý. Cho P (X1, X2, . . . , Xn) là tập cỏc hoỏn vị σ ∈ Sn với cỏc vị
trớ cấm X1, X2, . . . , Xn. Gọi B là bàn cờ được tạo từ cỏc vị trớ cấm
này. Khi đú số cỏc hoỏn vị này là
n∑
k=0
(−1)k(n− k)!rk(B).
Bài giảng Toỏn tổ hợp 30/34
3.3. Đa thức quõn xe
Vớ dụ. Cho X = {1, 2, 3, 4, 5} và cỏc tập con X1 = {3, 4}, X2 = {5},
X3 = {1, 3, 4}, và X5 = ∅. Tỡm số phần tử của tập hoỏn vị với vị trớ
cấm P (X1, X2, X3, X4, X5)?
Bài toỏn tương đương với bài toỏn tỡm số cỏch đặt 5 quõn xe trờn bàn
cờ 5ì 5 như hỡnh sau, trong đú cỏc ụ được gạch chộo là ụ cấm.
Bài giảng Toỏn tổ hợp 31/34
3.3. Đa thức quõn xe
Bài giảng Toỏn tổ hợp 32/34
3.3. Đa thức quõn xe
Vớ dụ. Ta cần bố trớ bốn người A,B,C,D vào 4 trong 5 cụng việc.
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 phự hợp?
Bài giảng Toỏn tổ hợp 33/34
3.3. Đa thức quõn xe
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.
Gọi B là bàn cờ được tạo bởi cỏc ụ cấm. Khi đú
R(B, x) = 1 + 7x = 15x2 + 10x3 + 2x4. Suy ra cỏch phõn cụng cụng
việc là 24.
Bài giảng Toỏn tổ hợp 34/34