Chương 2 - các phương pháp đếm và nguyên lý Dirichlet

CHƯƠNG 2
CÁC PHƯƠNG PHÁP ĐẾM VÀ NGUYÊN LÝ DIRICHLET
Các phần học trong chương 2
Các nguyên lý đếm cơ bản.
Khái niệm về hoán vị, chỉnh hợp, tổ hợp.
Nhị thức Newton.
Nguyên lý Dirichlet.
Hệ thức truy hồi.
Quan hệ chia để trị
Nguyên lý bù trừ.
Các nguyên lý đếm cơ bản
1.1 Nguyên lý cộng
Cho A là một tập hữu hạn các phần tử, ta ký hiệu N(A) là số lượng các phần tử của A.
Nguyên lý cộng: Cho A1, A2, ..., An là các tập hữu hạn, không giao nhau từng đôi một. Khi đó:
Các nguyên lý đếm cơ bản
1.1 Nguyên lý cộng
Ví dụ: Một sinh viên có thể chọn bài thực hành máy tính trong ba danh sách tương ứng có 23, 15 và 19 bài. Có bao nhiêu cách chọn bài thực hành?
Giải:
Có 23 cách chọn bài thực hành từ ds thứ nhất.
Có 15 cách chọn bài thực hành từ ds thứ hai.
Có 23 cách chọn bài thực hành từ ds thứ ba.
Vậy có 23 + 15 + 19 cách chọn bài thực hành.
Các nguyên lý đếm cơ bản
1.2 Nguyên lý nhân
Nguyên lý nhân: Cho A1, A2, ..., An là các tập hữu hạn bất kỳ, khi đó:
Các nguyên lý đếm cơ bản
1.2. Nguyên lý nhân
Ví dụ: Trong một trung tâm máy tính có 32 chiếc máy vi tính. Mỗi máy có 24 cổng. Hỏi có bao nhiêu cổng khác nhau trong trung tâm này?
Giải:
Thủ tục chọn cổng gồm 2 việc: chọn máy, và chọn cổng.
Vì có 32 cách chọn máy tính và 24 cách chọn cổng bất kể máy nào đã được chọn. Quy tắc nhân cho ta thấy có 3224 = 768 cổng.
2. K/n về hoán vị, chỉnh hợp, tổ hợp
2.1 Chỉnh hợp lặp
Chỉnh hợp lặp chập k của n phần tử là một cách sắp xếp có thứ tự k phần tử lấy từ tập gồm n phần tử đã cho, mỗi phần tử có thể lấy lặp lại.
Công thức tính:
Ví dụ: Tập A = {1,2,3,4,5} các bộ (1,1,2); (1,2,1); (2,3,5) và (2,3,2) là chỉnh hợp lặp chập 3 của 5 phần tử.
2. K/n về hoán vị, chỉnh hợp, tổ hợp
2.2 Chỉnh hợp không lặp
Chỉnh hợp không lặp chập k từ n phần tử là một cách sắp xếp có thứ tự k phần tử của n phần tử, mỗi phần tử không được lấy lặp lại.
Công thức tính:
Ví dụ: Tập A = {1,2,3,4,5} các bộ (1,3,2); (3,2,1); (2,3,5) và (2,3,4) là chỉnh hợp không lặp chập 3 của 5 phần tử.
2. K/n về hoán vị, chỉnh hợp, tổ hợp
2.3 Hoán vị
Hoán vị của n phần tử khác nhau là một cách sắp xếp có thứ tự n phần tử đó.
Công thức tính: Pn = n!
Ví dụ: Một bàn có 4 học sinh, hỏi có bao nhiêu cách sắp chỗ ngồi cho 4 hs đó.
Giải: Mỗi phương án lựa chọn để xếp chỗ ngồi là một hoán vị từ 4 học sinh. Vậy có 4! = 24 cách.
2. K/n về hoán vị, chỉnh hợp, tổ hợp
2.4. Tổ hợp
Tổ hợp chập k từ n phần tử là cách chọn không phân biệt thứ tự k phần tử lấy từ tập n phần tử đã cho, mỗi phần tử không được lấy lặp lại.
Công thức tính:
Ví dụ: Có bao nhiêu cách tuyển 5 trong số 10 cầu thủ cầu lông để đi thi đấu?
Giải: Đó chính là số tổ hợp chập 5 của 10 phần tử:
2. K/n về hoán vị, chỉnh hợp, tổ hợp
2.5. Tổ hợp lặp
Tổ hợp lặp chập k từ n phần tử là một bộ gồm k phần tử không phân biệt thứ tự, mỗi phần tử có thể được lấy lặp lại từ n phần tử đã cho.
Công thức tính:
3. Nhị thức Newton
Với x, y  R và n là số nguyên dương ta có:
Ví dụ: triển khai biểu thức (x+y)4
4. Nguyên lý Dirichlet
4.1. Mở đầu
Giả sử có một đàn chim bồ câu có 5 con bay vào chuồng.
Nhưng chỉ có 4 chuồng.
Điều gì sẽ sảy ra?
4. Nguyên lý Dirichlet
4.1. Mở đầu
Nguyên lý Dirichlet:
Nếu xếp nhiều hơn n đối tượng vào n cái hộp thì tồn tại ít nhất một họpp chứa không ít hơn 2 đối tượng.
VD: Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất hai người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau.
4. Nguyên lý Dirichlet
4.2. Nguyên lý Dirichlet tổng quát
Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất [N/k] đồ vật.
Ví Dụ: CMR trong 100 người, có ít nhất 9 người sinh cùng một tháng.
Giải:
Xếp những người sinh cùng tháng vào một nhóm. Có 12 tháng tất cả. Vậy theo nguyên lý Dirichlet, tồn tại một nhóm có ít nhất [100/12]= 9 người.
Định nghĩa 1: Hệ thức truy hồi (hay công thức truy hồi) đối với dãy số {an} là công thức biểu diễn an qua một hay nhiều số hạng đi trước của dãy. Dãy số được gọi là lời giải hay nghiệm của hệ thức truy hồi nếu các số hạng của nó thỏa mãn hệ thức truy hồi này.
5. Hệ thức truy hồi
5.1. Khái niệm và các ví dụ
5. Hệ thức truy hồi
5.1. Khái niệm và các ví dụ
Ví dụ: Cho {an} là dãy thỏa mãn hệ thức truy hồi an = an-1 – an-2 với n=2,3,4,... Và giả sử a0 = 5,
a1 = 9. Tìm a2, a3?
Giải: Từ hệ thức truy hồi ta có
a2 = a1 - a0 = 9 - 5 = 4.
a3 = a2 – a1 = 4 – 9 = -5.
5. Hệ thức truy hồi
5.1. Khái niệm và các ví dụ
Ví dụ 2: Giả sử số vi trùng trong một quần thể sẽ tăng gấp 3 sau mỗi giờ.
Hãy lập hệ thức truy hồi tính số vi trùng sau n giờ.
Nếu có 100 vi trùng ban đầu, chúng sẽ là bao nhiêu sau 10 giờ?
Giải:
Giả sử số vi trùng sau n giờ là an.
Ta có quan hệ an = 3an-1.
a0 = 100, a1 = 3a0, a2 = 3.3a0, ...,
a10 = 310a0 = 5.904.900
5. Hệ thức truy hồi
5.2. Giải các hệ thức truy hồi
Định nghĩa: hệ thức truy hồi có dạng: an = c1an-1 + c2an-2 + ... + ckan-k, trong đó c1, c2, ..., ck là các số thực và ck  0, được gọi là hệ thức truy hồi tuyến tính thần nhất bậc k với hệ số hằng.
Ví dụ:
Hệ thức truy hồi an = an-1 – an-2 là hệ thức truy hồi tuyến tính thuần nhất bậc 2.
Hệ thức truy hồi an = 3an-1 là hệ thức truy hồi tuyến tính thuấn nhất bậc 1.
5. Hệ thức truy hồi
5.2. Giải các hệ thức truy hồi
Định lý 1:
Cho c1, c2 là hai số thực. Giả sử phương trình r2 – c1r – c2 = 0 có 2 nghiệm phân biệt r1 và r2. Khi đó dãy {an} là nghiệm của hệ thức truy hồi
an=c1an-1+c2an-2 khi và chỉ khi an=1r1n+2r2n, n=1,2,... trong đó 1 và 2 là các hằng số.
5. Hệ thức truy hồi
5.2. Giải các hệ thức truy hồi
Ví dụ:Tìm nghiệm của hệ thức truy hồi
an = an-1 + 2an-2 với a0=2, a1=7.
Giải:
Phương trình là r2–r–2=0, có nghiệm là r=2, r=1.
Theo đlý, dãy {an} là nghiệm của hệ thức truy hồi khi và chỉ khi an = 12n+2(-1)n, trong đó 1 và 2 là các hằng số.
Ta có a0=2 = 1+2, a1=7 = 1.(2)+2.(-1)
Giải ra ta được 1 = 3, 2 = -1.
Nghiệm của hệ thức truy hồi là dãy {an} với
an=3.2n – (-1)n.
5. Hệ thức truy hồi
5.2. Giải các hệ thức truy hồi
Định lý 2:
Cho c1 và c2 là các số thực và c2  0. Giải sử r2 – c1r – c2 = 0 chỉ có 1 nghiệm r0. Dãy {an} là nghiệm của hệ thức truy hồi an = c1an-1 + c2an-2 khi và chỉ khi an= 1r0n+ 2nr0n với n = 0,1,2,... trong đó 1 và 2 là các hằng số.
5. Hệ thức truy hồi
5.2. Giải các hệ thức truy hồi
Định lý 3:
Cho c1, c2, ..., ck là các số thực. Giả sử phương trình đặc trưng
rk – c1rk-1 - ... – ck có k nghiệm phân biệt r1, r2, ..., rk. Khi đó dãy {an} là nghiệm của hệ thức truy hồi an=c1an-1+c2an-2+...+ckan-k khi và chỉ khi an=1r1n + 2r2n + ... + krkn, với n = 1, 2, ... trong đó 1, 2, ..., k là các hằng số.
5. Hệ thức truy hồi
5.2. Giải các hệ thức truy hồi
Ví dụ: Hãy tìm nghiệm của hệ thức truy hồi an = 6an-1 - 11an-2 + 6an-3, với đkiện ban đầu a0=2, a1=5 và a2=15.
Giải: Đa thức đặc trưng của hệ thức truy hồi này là
r3 - 6r2 + 11r – 6 = 0. Các nghiệm đặc trưng là
r = 1, r = 2, r = 3.
Do vậy nghiệm của hệ thức truy hồi có dạng:
an = 11n + 22n + 33n.
Các điều kiện ban đầu: a0 = 2 = 1 + 2 + 3
a1 = 5 = 1 + 22 + 33
a2 = 15 = 1 + 24 + 39.
Giải hệ được 1= 1, 2 = 1, 3 = 2. Vì thế, nghiệm duy nhất của hệ thức truy hồi này và các điều kiện ban đầu đã cho là dãy {an} với an = 1  2n + 2.3n.
6. Quan hệ chia để trị
Hệ thức truy hồi chia để trị:
Giả sử một thuật toán phân chia một bài toán cỡ n thành a bài toán nhỏ, mỗi bài toán nhỏ cỡ [n/b].
Giả sử tổng các phép toán thêm vào khi thực hiện phân chia bài toán cỡ n thành các bài toán có cỡ nhỏ hơn là g(n).
Khi đó, nếu f(n) là số các phép toán cần thiết để giải bài toán đã cho thì f thỏa mãn hệ thức truy hồi sau:
6. Quan hệ chia để trị
Ví dụ: Thuật toán tìm kiếm nhị phân:
Thuật toán đưa bài toán tìm kiếm cỡ n về bài toán tìm kiếm cỡ n/2, khi n chẵn.
Khi thực hiện rút gọn cần 2 phép so sánh
Xác định nửa ds nào được sd tiếp tục.
Xác định ds có còn phần tử không.
f(n) là số phép so sánh.
Ta có f(n) = f(n/2) + 2, nếu n chẵn.
6. Quan hệ chia để trị
Định lý 1: Giả sử f là một hàm tăng thoả mãn hệ thức truy hồi


với mọi n chia hết cho b, a  1, b là số nguyên lớn hơn 1, còn c là số thực dương. Khi đó:
6. Quan hệ chia để trị
Định lý 2: Giả sử f là hàm tăng thoả mãn hệ thức truy hồi

với mọi n = bk, trong đó k là số nguyên dương, a  1, b là số nguyên lớn hơn 1, còn c và d là các số thực dương. Khi đó
7. Nguyên lý bù trừ
Cho hai tập A và B. N(AB) = ?
Ta có: N(AB) = N(A) + N(B) – N(AB)
7. Nguyên lý bù trừ
Ví dụ: lớp Toán-tin có 25 sinh viên giỏi tin, 13 sinh viên giỏi toán n và 8 sinh viên giỏi cả toán và tin. Hỏi trong lớp có bao nhiêu sinh viên, nếu mỗi sinh viên hoặc giỏi toán hoặc giỏi tin hoặc giỏi cả hai môn.
Giải: gọi A là tập sv giỏi tin, B là tập sv giỏi toán. Khi AB là tập sv giỏi cả hai. Số sv trong lớp là N(AB) = 25+13-8 = 30.
7. Nguyên lý bù trừ
Cho 3 tập hợp A, B, C. N(ABC)=?
Ta có:
N(ABC)=N(A)+N(B)+N(C)-N(AB)-
N(AC)- N(BC)+N(ABC)
7. Nguyên lý bù trừ
Ví dụ: Có 1202 sv học t.Anh, 813sv học t.Pháp, 114 sv học t.Nga, 103 sv học cả t.Anh và t.Pháp, 23 sv học cả t.Anh và t.Nga, 14 sv học cả t.Pháp và t.Nga. Nếu tất cả 2092 sv đều theo học ít nhất 1 ngoại ngữ, thì có bao nhiêu sinh viên học cả 3 thứ tiếng?
Giải: N(ABC) = 3
7. Nguyên lý bù trừ
Định lý: (nguyên lý bù trừ) Cho A1, A2, ..., An là các tập hữu hạn. Khi đó:
7. Nguyên lý bù trừ
Ví dụ: Hãy viết ra công thức tính số phần tử của hợp 4 tập hợp.
Giải: áp dụng nguyên lý bù trừ:
N(ABCD)=N(A)+N(B)+N(C)+N(D)
-N(AB) -N(AC) -N(AD)
-N(BC) -N(BD) -N(CD)
+N(ABC) +N(ABD)
+N(ACD) +N(BCD)
-N(ABCD).
BÀI TẬP
Các bài tập cuối chương 2.