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à A₁, A₂, A₃, ta có thể viết công thức

(2) như sau:

X

N(A₁∩ A₂∩ A₃) = N −

N(A_i)+)

N(A_i∩ A_j) − N(A₁∩ A₂∩ A₃)

i

i=j

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 A₁, A₂và A₃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(A₁∩ A₂∩ A₃). Ta có

N = 70, N(A₁) = 70/2 = 35,

N(A₂) = 70/5 = 14, N(A₃) = 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(A₁∩ A₂) = 70/10 = 7. Tương tự ta có,

70

N(A₂∩ A₃) =

= 2, N(A₁∩ A₃) =

= 5.

5 × 7

2 × 7

Bài giảng Toán tổ hợp

8/34

3.1. Sử dụng sơ đồ Ven

70

N(A₁∩ A₂∩ A₃) =

= 1.

2 × 5 × 7

Áp dụng công thức (2) ta có

N(A₁∩ A₂∩ A₃) = 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ừ

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 A₁, A₂, . . . , A_n. Để đơn giản về mặt ký hiệu chúng ta

viết “ ∩ ” như là phép nhân. Ví dụ A₁∩ A₂∩ A₃sẽ được viết thành

A₁A₂A₃. 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 A₁, A₂, . . . , A_nsẽ được viết là N(A₁A₂. . . A_n).

Định lý. Cho tập vũ trụ U có N phần tử và A₁, A₂, . . . , A_nlà n tập

hợp con của U. Ta đặt S_klà 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 {A_i}_i=1,...,n, cụ thể

X

S₁=

N(A_i), S₂=

N(A_iA_j), . . . , S_n= N(A₁A₂. . . A_n).

i

i=j

Khi đó

X

N(A₁A₂. . . A_n) = N +

(−1)^kS_k

k

= N − S₁+ S₂− . . . + (−1)^kS_k+ . . . + (−1)ⁿS_n

Bài giảng Toán tổ hợp

10/34

3.2. Nguyên lý bù trừ

Hệ quả. Cho A₁, A₂, . . . , A_nlà n tập hợp con của tập vũ trụ U. Khi đó

X

N(A₁∪ . . . ∪ A_n) =

(−1)^k−1S_k

k≥1

= S₁− S₂+ . . . + (−1)^k−1S_k+ . . . + (−1)ⁿ⁻¹S_n

Chứng minh. Từ Định lý trên ta có

N(A₁. . . A_n) = N − S₁+ S₂− . . . + (−1)^kS_k+ . . . + (−1)ⁿS_n

ꢀ

ꢁ

= N − S₁− S₂+ . . . + (−1)^k−1S_k+ . . . + (−1)ⁿ⁻¹S_n

.

Mặt khác

N(A₁∪ . . . ∪ A_n) = N − N(A₁. . . A_n).

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

x₁+ x₂+ x₃+ x₄= 18

thỏa điều kiện x_i≤ 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

ꢂ

ꢃ

4 + 18 − 1

(∗). Ta cóN = N(U) = K₄¹⁸

=

= 1330.

18

Gọi A_ilà 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 x_i≥ 8. Khi đó kết quả của bài toán là N(A₁A₂A₃A₄).

Bằng việc giải những bài toán tìm số nghiêm nguyên ta được

ꢂ

ꢃ

ꢂ

ꢃ

13

10

5

2

N(A_i) = K₄¹⁰

=

N(A_iA_j) = K₄²=

N(A_iA_jA_k) = 0

N(A₁A₂A₃A₄) = 0

Vì vai trò của các A_i(1 ≤ i ≤ 4) như nhau nên ta có:

ꢂ

ꢃ

P

13

10

ꢂ

S₁= _iN(A_i) = 4

= 1144

ꢃ ꢂ

ꢃ

P

4

5

2

S₂= _i=jN(A_iA_j) =

= 60

2

S₃= 0, S₄= 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(A₁A₂A₃A₄) = N − S₁+ S₂− S₃+ S₄

= 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à A₁, A₂, A₃, A₄

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ó

ꢂ

ꢃ

ꢂ

ꢃ

52

6

26

6

N = N(U) =

N(A₁A₂) =

ꢂ

N(A₁A₂A₃A₄) = 0

ꢃ

ꢂ

ꢃ

13

39

N(A₁A₂A₃) =

N(A₁) =

6

Bài giảng Toán tổ hợp

13/34

3.2. Nguyên lý bù trừ

Vì vai trò A₁, A₂, A₃, A₄giống nhau nên ta có

ꢂ

ꢃ

ꢂ

ꢃ ꢂ

ꢃ

39

6

4

3

13

6

S₁= 4

S₂=

S₃=

ꢂ

ꢃ ꢂ

ꢃ

4

2

26

6

S₄= 0

a) N(A₁A₂A₃A₄) = N − S₁+ S₂− S₃+ S₄= 8682544

b) N(A₁∪ A₂∪ A₃∪ A₄) = S₁− S₂+ S₃− S₄= 11675976

Ví dụ. Tìm số nghiệm nguyên không âm của phương trình

x₁+ x₂+ x₃+ x₄= 25

(∗)

thỏa điều kiện x₁≤ 5, x₂≤ 6, x₃≤ 7.

Ví dụ. Tìm số nghiệm nguyên không âm của phương trình

x₁+ x₂+ x₃+ x₄+ x₅+ x₆= 20 thỏa điều kiện x_i≤ 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à A₁, A₂, . . . A_nlà 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 N_m,

là

ꢂ

m + 1

m

ꢃ

n−m

X

m + i

m

N_m

=

(−1)ⁱ

ꢂ

S_m+i

i=0

ꢃ

ꢂ

ꢃ

n

m

= S_m

−

S_m+1+ . . . + (−1)^n−m

S_n

Nếu ta gọi N_m^∗là số phần tử thuộc ít nhất m tập hợp thì

ꢂ

m

m − 1

ꢃ

n−m

X

m + i

m − 1

ꢃ

N_m^∗

=

(−1)ⁱ

ꢂ

N_m+i

i=0

ꢂ

ꢃ

n − 1

m − 1

= S_m

−

S_m+1+ . . . + (−1)^n−m

S_n.

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

A_ilà 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 = 3⁴

4

3

ꢂ

ꢃ

S₃=

3¹

4

1

S₁=

ꢂ

3³

3²

ꢂ

ꢃ

4

2

4

S₂=

S₄=

3⁰

Áp dụng định lý trên ta có:

ꢂ

ꢃ

ꢂ

ꢃ

3

2

4

2

a) N₂= S₂−

b) N₂^∗= S₂−

S₃+

S₄= 24.

S₄= 33.

ꢂ

ꢃ

ꢂ

2

1

3

1

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 A_ilà 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(A₁A₂. . . A₅).Ta có

ꢂ

ꢃ

5!

3!

5!

4!

5!

5

3

N = 5!

S₃=

S₄=

S₅=

2! =

1! =

0! =

ꢂ

ꢃ

5!

1!

5

1

S₁=

4! =

3! =

5

4

ꢂ

5!

2!

5

2

S₂=

5

Bài giảng Toán tổ hợp

17/34

3.2. Nguyên lý bù trừ

Ta có

N(A₁A₂. . . A₅) = N − S₁+ S₂− S₃+ S₄− S₅

5! 5! 5! 5! 5!

= 5! −

+

−

+

−

1! 2! 3! 4! 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à S_n. Mỗi hoán vị của σ ∈ S_nđượ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ị σ ∈ S_ntươ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 X₁, X₂, . . . , X_n⊂ {1, 2, . . . , n}. Đặt

P(X₁, X₂, . . . , X_n) = {σ ∈ S_n|σ(i) ∈/ X_i}.

Tập X_iđược gọi là vị trí cấm của i, các hoán vị thuộc

P(X₁, X₂, . . . , X_n) được gọi là hoán vị với vị trí cấm.

Bài giảng Toán tổ hợp

20/34