Bài giảng Toán rời rạc - Chương 4: Đếm các phần tử - Nguyễn Quỳnh Diệp

ĐẾM CÁC PHẦN TỬ Nguyễn Quỳnh Diệp diepnq@tlu.edu.vn 1 CHƯƠNG 4 Nguyễn Quỳnh Diệp File Bài giảng: goo.gl/Y3cpLF hoặc goo.gl/TYxXQD NỘI DUNG • Cơ sở của phép đếm • Nguyên lý chuồng chim bồ câu • Chỉnh hợp và tổ hợp • Các hệ số nhị thức • Chỉnh hợp và tổ hợp suy rộng • Sinh các hoán vị và tổ hợp Toán rời rạc 2Nguyễn Quỳnh Diệp Toán rời rạc 3 4.1. CƠ SỞ CỦA PHÉP ĐẾM Nguyễn Quỳnh Diệp CƠ SỞ CỦA PHÉP ĐẾM Toán rời rạc 4 • Giả định rằng ta có một tập các đối tượng cùng với thuộc tính của nó • Phép đếm là xác định số lượng các đối tượng đó Các nguyên lí đếm cơ bản • Quy tắc nhân • Quy tắc cộng Nguyễn Quỳnh Diệp CƠ SỞ CỦA PHÉP ĐẾM Toán rời rạc 5 QUY TẮC NHÂN Ví dụ 1: Có bao nhiêu xâu nhị phân có độ dài 7? Giả sử một thủ tục nào đó được tách ra thành một dãy hai nhiệm vụ. Nếu có n1 để làm nhiệm vụ thứ nhất và n2 cách để làm nhiệm vụ thứ hai sau khi nhiệm vụ thứ nhất đã được hoàn thành, thì sẽ có n1.n2 cách thực hiện thủ tục này Ví dụ 2: Có nhiều nhất bao nhiêu biển đăng kí ô tô nếu mỗi biển chứa một dãy ba chữ cái và tiếp sau là ba chữ số? Nguyễn Quỳnh Diệp CƠ SỞ CỦA PHÉP ĐẾM Toán rời rạc 6 QUY TẮC CỘNG Ví dụ 1: Để đi từ thành phố A đến thành phố B có thể đi bằng tàu, xe ô tô hoặc đi máy bay. Có 12 chuyến máy bay từ A tới B, có 5 chuyến tàu và 10 chuyến ô tô. Hỏi có bao nhiêu lựa chọn để đi từ A đến B? Giả sử có hai nhiệm vụ. Nhiệm vụ thứ nhất có thể được thực hiện bằng n1 cách, nhiệm vụ thứ hai có thể thực hiện bằng n2 cách và nếu hai việc này không thể làm đồng thời, thì sẽ có n1+n2 cách làm một trong hai nhiệm vụ đó. Nguyễn Quỳnh Diệp NHỮNG BÀI TOÁN PHỨC TẠP HƠN Toán rời rạc 7 Ví dụ 1: Mật khẩu để đăng nhập máy tính: • Dài từ 6 đến 8 kí tự • Mỗi kí tự là 1 chữ cái • Hỏi có thể có bao nhiêu mật khẩu? • Những bài toán phức tạp có thể giải được nếu sử dụng kết hợp cả hai quy tắc nhân và quy tắc cộng Nguyễn Quỳnh Diệp NGUYÊN LÝ BÙ TRỪ Toán rời rạc 8 Cho A1, A2 là các tập hợp, khi đó: 𝐴1 ∪ 𝐴2 = 𝐴1 + 𝐴2 − |𝐴1 ∩ 𝐴2| Nguyên lý bù trừ: Khi hai nhiệm vụ làm đồng thời • Cộng số cách làm từng nhiệm vụ • Trừ đi số cách làm đồng thời cả hai nhiệm vụ Theo ngôn ngữ tập hợp: Ví dụ: Có bao nhiêu xâu nhị phân độ dài 8 bít: hoặc được bắt đầu bằng bit 1, hoặc kết thúc bằng hai bít 00 Nguyễn Quỳnh Diệp BÀI TẬP 9 Toán rời rạc  Bài 1: Có bao nhiêu xâu nhị phân có độ dài bằng 10 và có bit đầu tiên và bit cuối cùng bằng 1.  Bài 2: Có bao nhiêu xâu gồm 8 chữ cái tiếng anh a) nếu các chữ cái có thể lặp lại b) nếu không chữ cái nào lặp lại c) bắt đầu với chữ cái X và nếu các chữ cái có thể được lặp lại Nguyễn Quỳnh Diệp Toán rời rạc 10 4.2. NGUYÊN LÍ CHUỒNG CHIM BỒ CÂU Nguyễn Quỳnh Diệp NGUYÊN LÍ CHUỒNG CHIM BỒ CÂU Toán rời rạc 11 • Giả sử có một đàn chim bồ câu và một số chuồng • Nguyên lí chuồng chim bồ câu: nếu số chim nhiều hơn số ngăn chuồng thì ít nhất trong một ngăn có 2 con hoặc nhiều hơn. Định lí 1 Nếu có (k+1) đồ vật hoặc nhiều hơn được đặt vào k hộp, thì có ít nhất một hộp chứa hai hoặc nhiều hơn hai đồ vật. Nguyễn Quỳnh Diệp NGUYÊN LÍ CHUỒNG CHIM BỒ CÂU Toán rời rạc 12 Ví dụ: Có 7 quả bóng và có 5 hộp để đựng, ít nhất có 1 hộp có ít nhất 2 bóng Nguyễn Quỳnh Diệp NGUYÊN LÍ DIRICHLET TỔNG QUÁT Toán rời rạc 13 Định lí 2 Nếu có N đồ vật được đặt vào k hộp, thì sẽ tồn tại một hộp chứa ít nhất N/k vật. Ví dụ 1: Trong 100 người có ít nhất 100/12 = 9 người có cùng tháng sinh. Nguyễn Quỳnh Diệp NGUYÊN LÍ DIRICHLET TỔNG QUÁT Toán rời rạc 14 Ví dụ 2: a. Cần phải chọn ít nhất bao nhiêu quân bài trong một bộ bài chuẩn gồm 52 quân để đảm bảo có 3 quân bài cùng một chất. b. Cần phải chọn bao nhiêu quân bài để đảm bảo ít nhất có ba quân bài cơ được chọn Ví dụ 3: Có 51 ngôi nhà trong một phố. Mỗi ngôi nhà có địa chỉ nằm từ 1000 đến 1099. Chứng tỏ rằng có ít nhất hai nhà có địa chỉ là hai số nguyên liên tiếp. Nguyễn Quỳnh Diệp BÀI TẬP 15 Toán rời rạc  Bài 3: Hỏi phải có bao nhiêu sinh viên tham gia học đến từ 50 bang để đến khi tốt nghiệp ít nhất có 100 sinh viên thuộc cùng 1 bang. Nguyễn Quỳnh Diệp Toán rời rạc 16 4.3. CHỈNH HỢP VÀ TỔ HỢP Nguyễn Quỳnh Diệp HOÁN VỊ Toán rời rạc 17 • Hoán vị của một tập các đối tượng là một cách sắp xếp có thứ tự các đối tượng này. • Hoán vị của n phần tử =n! Ví dụ: • Cho tập S gồm các phần tử {a, b, c} • Các hoán vị của tập S: { a, b, c} {b, a, c} {b, c, a} {c, b, a} {c, a, b} {a, c, b} Nguyễn Quỳnh Diệp CHỈNH HỢP Toán rời rạc 18 • Số hoán vị của tập n phần tử là: P(n,n) = n! • Chỉnh hợp chập r của n phần tử là cách sắp xếp có thứ tự r phần tử của một tập n phần tử. Định lí 1 Số chỉnh hợp chập r của tập S gồm n phần tử là: 𝑷 𝒏, 𝒓 = 𝒏 𝒏 − 𝟏 𝒏 − 𝟐 𝒏 − 𝒓 + 𝟏 = 𝒏! 𝒏 − 𝒓 ! Nguyễn Quỳnh Diệp HOÁN VỊ VÀ CHỈNH HỢP Toán rời rạc 19 Ví dụ 1: Có bao nhiêu hoán vị của các chữ cái A, B, C, D, E, F, G, H có chứa xâu ABC Ví dụ 2: Có bao nhiêu cách để chọn người đoạt giải nhất, giải nhì và giải ba trong một cuộc thi có 100 người khác nhau tham gia? Giả sử rằng một thương nhân định đi bán hàng tại tám thành phố. Chị ta bắt đầu cuộc hành trình của mình từ một thành phố nào đó, nhưng có thể đến bảy thành phố khác theo bất kì thứ tự nào. Hỏi chị ta có thể đi qua tất cả các thành phố này theo bao nhiêu lộ trình khác nhau? Ví dụ 3: Nguyễn Quỳnh Diệp TỔ HỢP Toán rời rạc 20 • Tổ hợp chập r của một tập hợp n phần tử là cách chọn không có thứ tự r phần tử của tập đã cho. Kí hiệu C(n, r) hoặc 𝒏 𝒓 Ví dụ: • Tổ hợp chập 2 của tập hợp {a, b, c} là: { a, b} {b, c} {c, a} Định lí 2 Số tổ hợp chập r từ tập có n phần tử, n là số nguyên dương và r là số nguyên, 0  r  n , được cho bởi công thức: 𝑪 𝒏, 𝒓 = 𝒏! 𝒓! 𝒏−𝒓 ! Nguyễn Quỳnh Diệp TỔ HỢP Toán rời rạc 21 Ví dụ 1: Có bao nhiêu cách tuyển năm trong số mười cầu thủ của một đội quần vợt để đi thi đấu tại một trường khác. Ví dụ 2: Xác định số xâu bit có độ dài n và chứa đúng r bit 1 Ví dụ 3: Xác định số cách lựa chọn một hội đồng để triển khai môn toán rời rạc tại một trường đại học, nếu hội đồng gồm 3 thành viên của khoa toán, bốn thành viên của khoa tin. Khoa toán có 9 thành viên, khoa tin có 11 thành viên. Hệ quả 1 Cho n và r là các số nguyên không âm sao cho r  n. Khi đó: C(n,r) = C(n, n-r) Nguyễn Quỳnh Diệp BÀI TẬP Toán rời rạc  Bài 4: Có sáu ứng cử viên tranh cử chức thống đốc bang. Tính số cách in tên của các ứng cử viên lên phiếu bầu cử.  Bài 5: Có bao nhiêu xâu bit độ dài 10 chứa: a) Đúng 4 bít 1 b) Nhiều nhất 4 bít 1 c) Ít nhất 4 bit 1 d) Số bít 0 bằng số bit 1 22Nguyễn Quỳnh Diệp 22 Toán rời rạc 23 4.4. CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG Nguyễn Quỳnh Diệp CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG Toán rời rạc 24 Ví dụ: • Có bao nhiêu xâu gồm hai kí tự sinh ra từ tập {a, b, c} Định lí 1 Số các chỉnh hợp lặp chập r từ n phần tử bằng nr. aa, ab, ac, bb, ba, bc, cc, ca, cb 3.3 = 32 = 9 • Chỉnh hợp lặp chập r của n phần tử là cách sắp xếp có thứ tự r phần tử của một tập n phần tử cho phép các phần tử lặp lại. Nguyễn Quỳnh Diệp CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG Toán rời rạc 25 Ví dụ: • Có bao nhiêu tổ hợp lặp chập 2 sinh ra từ tập {a, b, c} aa, bb, cc, ab, bc, ac, C(3+2-1,2) = C(4,2) = 4! 2!(4−2)! = 6 • Tổ hợp lặp chập r của một tập hợp n phần tử là cách chọn không có thứ tự r phần tử của tập đó, cho phép các phần tử được lặp lại. Nguyễn Quỳnh Diệp Có C(n+r-1,r) số tổ hợp lặp chập r từ tập n phần tử. Định lí 2 CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG Toán rời rạc 26 Ví dụ 1: Trong đĩa hoa quả có táo, cam, lê, mỗi loại có ít nhất 4 quả. tính số cách lấy 4 quả từ đĩa này nếu thứ tự các quả được chọn không quan trọng. Ví dụ 2: Nguyễn Quỳnh Diệp Có bao nhiêu cách đặt 10 viên bi giống hệt nhau vào tám ngăn phân biệt? Có bao nhiêu cách chọn năm tờ giấy bạc từ một két đựng tiền gồm những tờ có mệnh giá 1$, 2$, 5$, 10$, 20$, 50$ và 100$. Giả sử thứ tự mà các tờ tiền được chọn ra là không quan trọng, các tờ tiền cùng loại là không phân biệt và mỗi loại có ít nhất 5 tờ. Ví dụ 3: CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG Toán rời rạc 27 Tổ hợp và chỉnh hợp: Nguyễn Quỳnh Diệp Loại Lặp không? Công thức Chỉnh hợp chập r Không 𝑃(𝑛, 𝑟) = 𝑛! 𝑛 − 𝑟 ! Tổ hợp chập r Không 𝐶(𝑛, 𝑟) = 𝑛! 𝑟! 𝑛 − 𝑟 ! Chỉnh hợp chập r Lặp 𝑛𝑟 Tổ hợp chập r Lặp 𝐶(𝑛 + 𝑟 − 1, 𝑟) = (𝑛 + 𝑟 − 1)! 𝑟! 𝑛 − 1 ! HOÁN VỊ VỚI CÁC PHẦN TỬ KHÔNG PHÂN BIỆT Toán rời rạc 28 Ví dụ: Có thể nhận được bao nhiêu xâu khác nhau bằng cách sắp xếp lại các chữ cái của từ SUCCESS? • Trong bài toán đếm, một số phần tử có thể giống hệt nhau, không phân biệt  Tránh đếm chúng hơn 1 lần Nguyễn Quỳnh Diệp HOÁN VỊ VỚI CÁC PHẦN TỬ KHÔNG PHÂN BIỆT Toán rời rạc 29 Định lí 3: Số các hoán vị khác nhau của n phần tử, trong đó có n1 phần tử thuộc loại 1, n2 phần tử thuộc loại 2,... nk phần tử thuộc loại k, bằng: 𝒏! 𝒏𝟏! 𝒏𝟐! 𝒏𝒌! Nguyễn Quỳnh Diệp SỰ PHÂN PHỐI CÁC VẬT VÀO TRONG CÁC HỘP Toán rời rạc 30 Ví dụ: • Có bao nhiêu cách chia một cỗ bài chuẩn 52 quân thành những tay bài gồm 5 quân cho 4 người chơi. Định lí 4: Số cách phân phối n vật khác nhau vào k hộp khác nhau sao cho có ni vật được đặt vào hộp thứ i, với i= 1, 2, ..., k, bằng: 𝒏! 𝒏𝟏! 𝒏𝟐! 𝒏𝒌! Nguyễn Quỳnh Diệp BÀI TẬP Toán rời rạc  Bài 6: Có bao nhiêu cách chọn 12 chiếc bánh từ một cửa hàng có 21 loại bánh khác nhau  Bài 7: Có bao nhiêu cách phân phối 12 viên bi giống hệt nhau vào sáu ngăn phân biệt. 31  Bài 8: Có bao nhiêu cách phân phối 12 vật khác nhau vào 6 ngăn phân biệt, mỗi ngăn 2 vật. Nguyễn Quỳnh Diệp 31 Toán rời rạc 32 4.5. HỆ THỨC TRUY HỒI Nguyễn Quỳnh Diệp CÁC HỆ THỨC TRUY HỒI Toán rời rạc 33 • Một số bài toán đếm không thể giải được bằng kĩ thuật đếm thông thường • Có thể giải bằng cách tìm mối quan hệ, gọi là các hệ thức truy hồi Nguyễn Quỳnh Diệp CÁC HỆ THỨC TRUY HỒI Toán rời rạc 34 Hệ thức truy hồi đối với dãy số {an} là phương trình biểu diễn an qua một hay nhiều số hạng đứng trước nó, cụ thể là a0, a1, ..., an-1 với mọi số nguyên n  n0 ,trong đó n0 là một số nguyên không âm. Dãy số được gọi là lời giải hay là 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. Định nghĩa 1: Ví dụ: Một hệ thức truy hồi an = 2an-1 - an-2 với a0 = 1, a1 = 3 thì nghiệm của hệ thức truy hồi là: an = 2n+1 Nguyễn Quỳnh Diệp CÁC HỆ THỨC TRUY HỒI Toán rời rạc 35 Ví dụ 1: Cho {an} là dãy số 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 = 3, a1 = 5. Tìm a2, a3. Ví dụ 2: Hãy xác định xem dãy {an} trong đó an =3n với mọi n nguyên không âm có phải là lời giải của hệ thức truy hồi an = 2an-1 – an-2 với n = 2, 3, 4... hay không? Cũng câu hỏi như vậy đối với an = 2 n và an = 5 Nguyễn Quỳnh Diệp MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Toán rời rạc 36 Ví dụ 1: Lãi kép. Giả sử một người gửi 10.000$ vào tài khoản của mình tại một ngân hàng với lãi suất kép 11% mỗi năm. Hỏi sau 30 năm anh ta có bao nhiêu tiền trong tài khoản của mình? Giải: - Gọi Pn là tổng số tiền có trong tài khoản sau n năm Pn = Pn-1 + 0.11Pn-1 = 1,11Pn-1 - Như vậy: - P1 = 1,11P0 - P2 = 1,11P1 = (1,11) 2 P0 - ... - Pn = 1,11Pn-1 = (1,11) n P0 - Thay n = 30 vào công thức P30 = (1,11) 30 . 10000 = 228 923$ Nguyễn Quỳnh Diệp MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Toán rời rạc 37 Ví dụ 2: Họ nhà thỏ và các số Fibonacci. Một cặp thỏ mới sinh được thả trên một hòn đảo. Giả sử rằng một cặp thỏ chưa sinh sản được trước khi đầy 2 tháng tuổi. Kể từ khi chúng đầy 2 tháng tuổi, mỗi tháng chúng đẻ được một đôi thỏ con. Tìm công thức truy hồi tính số cặp thỏ trên đảo sau n tháng với giả sử các con thỏ là trường thọ. Nguyễn Quỳnh Diệp MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Toán rời rạc 38 Số cặp thỏ trên đảo số cặp đẻ thêm số cũ thêm Nguyễn Quỳnh Diệp MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Toán rời rạc 39 Số cặp thỏ trên đảo số cặp đẻ thêm số cũ thêm Nguyễn Quỳnh Diệp MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Toán rời rạc 40 Số cặp thỏ trên đảo số cặp đẻ thêm số cặp cũ Nguyễn Quỳnh Diệp MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Toán rời rạc 41 Số cặp thỏ trên đảo số cặp đẻ thêm số cặp cũ Nguyễn Quỳnh Diệp MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Toán rời rạc 42 Giải: - Giả sử fn là số cặp thỏ sau n tháng, với n = 1, 2, 3,... - Tháng 1 số cặp thỏ trên đảo là f1 = 1 - Tháng 2 số cặp thỏ trên đảo là f2 = 1 - Tháng 3 số cặp thỏ f3 = 1 + 1 = f1 + f2 - Tháng 4 số cặp thỏ f4 = 1 + 2 = f2 + f3 - Tháng n số cặp thỏ trên đảo là fn = fn-1 + fn-2 , fn-1 số cặp thỏ tháng trước, fn-2 số cặp thỏ mới đẻ Nguyễn Quỳnh Diệp MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Toán rời rạc 43 Ví dụ 3: Tháp Hà Nội. Do Édouard Lucas đưa ra cuối thế kỉ XIX. Cọc 1 Cọc 2 Cọc 3 Nguyễn Quỳnh Diệp MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI Toán rời rạc 44 Giải: - Gọi Hn là số bước dịch chuyển để giải câu đố tháp Hà Nội với n đĩa - Dịch chuyển n-1 đĩa từ cọc 1 sang cọc 3, phải dùng Hn-1 lần - Dịch chuyển đĩa n từ cọc 1 sang cọc 2 - Cuối cùng, mất Hn-1 lần để dịch chuyển n-1 đĩa từ cọc 3 sang cọc 2 - Ta có hệ thức truy hồi: Hn = 2.Hn-1 + 1, với H1 = 1 - Hn = 2.Hn-1 + 1 = 2.(2Hn-2 + 1) + 1 = 2 2 Hn-2 + 2 + 1 = 22(2.Hn-3 + 1) + 2 + 1 = 2 3Hn-3 + 2 2 + 2 + 1 ... = 2n-1 H1 + 2 n-2 +... + 2 + 1 = 2n-1 + 2n-2 +... + 2 + 1 = 2n -1 Nguyễn Quỳnh Diệp BÀI TẬP 45 Toán rời rạc  Bài 1: Giả sử an = 2 n + 5.3n , với n = 0, 1, 2,... a) Tìm a1, a2 ,a3 và a4 b) CM: a2 = 5a1 – 6a0 , a3 = 5a2 – 6a1 và a4 = 5a3 – 6a2 c) CMR: an = 5an-1 – 6an-2 với mọi số nguyên n  2  Bài 2: Chứng tỏ rằng dãy {an} là nghiệm của hệ thức truy hồi an=an-1 + 2an-2 + 2n – 9 nếu: a) an = -n + 2 b) an = 5(-1) n – n + 2 45Nguyễn Quỳnh Diệp BÀI TẬP 46 Toán rời rạc  Bài 3: Một nhân viên bắt đầu làm việc tại một công ti từ năm 1999 với lương khởi điểm là 50 000 đô la một năm. Hằng năm anh ta được nhận thêm 1000 đô la và 5% lương của năm trước. a) Hãy thiết lập hệ thức truy hồi tính lương của nhân viên đó sau năm 1999 n năm. b)Lương năm 2007 của anh ta là bao nhiêu? c)Hãy tìm công thức tường minh tính lương của nhân viên này sau năm 1999 n năm 46Nguyễn Quỳnh Diệp Toán rời rạc 47 4.6. GIẢI CÁC HỆ THỨC TRUY HỒI HỆ THỨC TRUY HỒI TUYẾN TÍNH Toán rời rạc 48 Một hệ thức truy hồi tuyến tính thuần nhất bậc k với hệ số hằng số là 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 Định nghĩa 1: • Tuyến tính vì vế phải là tổng các tích của các số hạng trước của dãy • Thuần nhất vì mọi số hạng đều có dạng aj nhân với hệ số • Bậc k là vì an được biểu diễn qua k số hạng đứng trước Nguyễn Quỳnh Diệp HỆ THỨC TRUY HỒI TUYẾN TÍNH Toán rời rạc 49 Ví dụ: - Hệ thức truy hồi Pn = (1.11)Pn-1 là hệ thức truy hồi tuyến tính thuần nhất bậc nhất - Hệ thức truy hồi an = an-1 + (an-1) 2 không là tuyến tính - Hệ thức truy hồi Hn = 2Hn-1 + 1 không là thuần nhất - Hệ thức truy hồi Bn =nBn-1 không có hệ số hằng Nguyễn Quỳnh Diệp GIẢI HỆ THỨC TRUY HỒI TUYẾN TÍNH Toán rời rạc 50 Phương pháp cơ bản: • Tìm nghiệm dạng an = r n , trong đó r là hằng số • an = r n là nghiệm của HTTH: an=c1an-1+ c2an-2 +... +ckan-k nếu và chỉ nếu rn = c1r n-1 + c2r n-2 +... +ckr n-k (*) • Chia cả 2 vế cho rn-k . Khi đó (*) tương đương phương trình: rk - c1r k-1 - c2r k-2 - ... +ck-1r – ck = 0 (1) • Do đó, an = r n là nghiệm nếu và chỉ nếu r là nghiệm phương trình (1) • Phương trình (1) gọi là phương trình đặc trưng • Nghiệm của phương trình (1) gọi là nghiệm đặc trưng của hệ thức truy hồi Nguyễn Quỳnh Diệp GIẢI HTTH TUYẾN TÍNH BẬC 2 Toán rời rạc 51 Cho hệ thức truy hồi an = c1an-1 + c2an-2 với c1 , c2 là hai số thực. Giả sử phương trình đặc trưng r2 – c1r – c2 = 0 có hai nghiệm phân biệt là r1, r2. Khi đó {an} là nghiệm của HTTH nếu và chỉ nếu an = 1r1 n + 2r2 n với n = 0, 1, 2,... trong đó 1, 2 là các hằng số. Định lí 1: Tìm nghiệm của hệ thức truy hồi an = an-1 + 2an-2 với a0 = 2, a1 = 7 Ví dụ 1: Nguyễn Quỳnh Diệp GIẢI HTTH TUYẾN TÍNH BẬC 2 Toán rời rạc 52 Cho hệ thức truy hồi an = c1an-1 + c2an-2 với c1 , c2 là hai số thực, c2  0. Giả sử phương trình đặc trưng r2 – c1r – c2 = 0 có nghiệm kép r0 Khi đó {an} là nghiệm của hệ thức truy hồi nếu và chỉ nếu an = 1r0 n + 2nr0 n với n = 0, 1, 2 ,... trong đó 1, 2 là các hằng số. Định lí 2: Tìm nghiệm của hệ thức truy hồi an = 6an-1 - 9an-2 với a0 = 1, a1 = 6 Ví dụ 2: Nguyễn Quỳnh Diệp GIẢI HTTH TUYẾN TÍNH TỔNG QUÁT Toán rời rạc 53 Cho hệ thức truy hồi an = c1an-1 + c2an-2 + ckan-k với c1 , c2 ,..., ck là các số thực. Giả sử phương trình đặc trưng rk – c1r k-1 – ... – ck =0 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 nếu và chỉ nếu an = 1r1 n + 2r2 n + ... + krk n, với n = 0, 1, 2 ,... trong đó 1, 2 ,..., k là các hằng số. Định lí 3: Tìm nghiệm của hệ thức truy hồi an = 6an-1 - 11an-2 + 6an-3 với a0 = 2, a1 = 5, a2 = 15 Ví dụ 3: Nguyễn Quỳnh Diệp BÀI TẬP Toán rời rạc  Bài 4: Trong các hệ thức truy hồi sau đây, hệ thức nào là tuyến tính thuần nhất với hệ số hằng số. Bậc của các hệ thức đó là bao nhiêu? a) an =3an-1 +4an-2 + 5an-3 b) an = 2nan-1 + an-2 c)an = an-1 + an-4 d) an = an-1 + 2 e) an = an-1 2 + an-2  Bài 5: Giải các hệ thức truy hồi cùng các điều kiện đầu sau: a) an = 2an-1 , với n  1, a0 = 3 b) an = 5an-1 - 6an-2 , với n  2, a0 = 1, a1 = 0 c) an = 4an-1 - 4an-2 , với n  2, a0 = 6, a1 = 8 54Nguyễn Quỳnh Diệp Toán rời rạc 55 4.7. NGUYÊN LÍ BÙ TRỪ Nguyễn Quỳnh Diệp NGUYÊN LÍ BÙ TRỪ Toán rời rạc 56 • Có bao nhiêu phần tử trong hợp của hai tập hợp hữu hạn phần tử? | A  B | = | A | + | B | - | A  B | Lớp toán rời rạc có 25 sinh viên chuyên ngành tin học, 13 sinh viên chuyên ngành toán và tám sinh viên theo học cả ngành toán lẫn tin học. Hỏi trong lớp này có bao nhiêu sinh viên, nếu mỗi sinh viên theo ngành toán hoặc ngành tin hoặc theo học cả toán và tin? Ví dụ 1: Giả sử trong trường có 1807 sinh viên năm thứ nhất. Trong số này có 453 người chọn môn tin học, 547 người chọn môn toán và 299 người học cả hai môn toán và tin. Hỏi có bao nhiêu sinh viên không theo học toán cũng không học tin? Ví dụ 2: Nguyễn Quỳnh Diệp NGUYÊN LÍ BÙ TRỪ Toán rời rạc 57 • Trường hợp 3 tập hợp: | A  B  C | = | A | + | B | + | C | - | A  B | - | A  C | - | C  B | + | A  B  C | Nguyễn Quỳnh Diệp NGUYÊN LÍ BÙ TRỪ Toán rời rạc 58 Biết rằng có 1232 sinh viên học tiếng Tây Ban Nha, 879 sinh viên học tiếng Pháp và 114 sinh viên học tiếng Nga. Ngoài ra còn biết rằng 103 sinh viên học cả tiếng Tây Ban Nha và tiếng Pháp, 23 sinh viên học cả tiếng Tây Ban Nha và tiếng Nga, 14 sinh viên học cả tiếng Pháp và tiếng Nga. Nếu tất cả 2092 sinh viên đều theo học ít nhất một ngoại ngữ, thì có bao nhiêu sinh viên học cả ba thứ tiếng? Ví dụ 1: Nguyễn Quỳnh Diệp NGUYÊN LÍ BÙ TRỪ Toán rời rạc 59 NGUYÊN LÍ BÙ TRỪ. Cho A1 , A2,A3 là các tập hữu hạn. Khi đó: Định lí 1: 𝑨𝟏 ∪ 𝑨𝟐 ∪⋯∪ 𝑨𝒏 = 𝟏≤𝒊≤𝒏 𝑨𝒊 − 𝟏≤𝒊<𝒋≤𝒏 |𝑨𝒊 ∩ 𝑨𝒋| + 𝟏≤𝒊<𝒋<𝒌≤𝒏 |𝑨𝒊 ∩ 𝑨𝒋∩ 𝑨𝒌 | − + −𝟏 𝒏+𝟏| 𝑨𝟏 ∩ 𝑨𝟐 ∩⋯∩ 𝑨𝒏| Nguyễn Quỳnh Diệp NGUYÊN LÍ BÙ TRỪ Toán rời rạc 60 Có bao nhiêu phần tử trong hợp của bốn tập hợp, nếu mỗi tập có 100 phần tử, mỗi cặp tập hợp có chung 50 phần tử, mỗi bộ ba tập hợp có 25 phần tử chung và có năm phần tử thuộc cả 4 tập hợp. Ví dụ: Nguyễn Quỳnh Diệp BÀI TẬP 61 Toán rời rạc Bài 5: Giả sử trong một sọt táo chứa 100 quả có 20 quả bị sâu và 15 quả bị giập nát. Chỉ những quả táo không có sâu hoặc không giập nát mới có thể bán được. Hỏi nếu có 10 quả táo vừa bị sâu vừa bị giập nát thì có bao nhiêu quả táo trong sọt có thể bán? 61Nguyễn Quỳnh Diệp DẠNG KHÁC CỦA NGUYÊN LÍ BÙ TRỪ Toán rời rạc 62 • Giả sử Ai là tập con chứa các phần tử có tính chất P1 , P2, ,Pn kí hiệu N(P1P2...Pn) | A1 A2  ... An | = N(P1P2...Pk) • Nếu số các phần tử không có tính chất nào trong số n tính chất P1P2...Pn được kí hiệu N(P1 ’ P2 ’ ...Pn ’ ) N(P1 ’ P2 ’ ...P