CHƯƠNG 4
ĐẾM CÁC PHẦN TỬ
Nguyễn Quỳnh Diệp diepnq@tlu.edu.vn
File Bài giảng: goo.gl/Y3cpLF hoặc goo.gl/TYxXQD
1
Nguyễn Quỳnh Diệp
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
Nguyễn Quỳnh Diệp
Toán rời rạc
2
4.1. CƠ SỞ CỦA PHÉP ĐẾM
Nguyễn Quỳnh Diệp
Toán rời rạc
3
CƠ SỞ CỦA PHÉP ĐẾM
• 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
Nguyễn Quỳnh Diệp
Toán rời rạc
• Quy tắc cộng
4
CƠ SỞ CỦA PHÉP ĐẾM
QUY TẮC NHÂN 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ụ 1: Có bao nhiêu xâu nhị phân có độ dài 7?
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
Toán rời rạc
5
CƠ SỞ CỦA PHÉP ĐẾM
QUY TẮC CỘNG 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ụ đó.
Ví dụ 1:
Nguyễn Quỳnh Diệp
Toán rời rạc
Để đ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?
6
NHỮNG BÀI TOÁN PHỨC TẠP HƠN
hai quy tắc nhân và quy tắc cộng
• 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ả
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?
Nguyễn Quỳnh Diệp
Toán rời rạc
7
NGUYÊN LÝ BÙ TRỪ
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:
Cho A1, A2 là các tập hợp, khi đó:
𝐴1 ∪ 𝐴2 = 𝐴1 + 𝐴2 − |𝐴1 ∩ 𝐴2|
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
Toán rời rạc
8
BÀI TẬP
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
9
Nguyễn Quỳnh Diệp
Toán rời rạc
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
4.2. NGUYÊN LÍ CHUỒNG CHIM BỒ CÂU
Nguyễn Quỳnh Diệp
Toán rời rạc
10
NGUYÊN LÍ CHUỒNG CHIM BỒ CÂU
• 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
Toán rời rạc
11
NGUYÊN LÍ CHUỒNG CHIM BỒ CÂU
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
Toán rời rạc
12
NGUYÊN LÍ DIRICHLET TỔNG QUÁT
Đị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
Nguyễn Quỳnh Diệp
Toán rời rạc
tháng sinh.
13
NGUYÊN LÍ DIRICHLET TỔNG QUÁT
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
Toán rời rạc
14
BÀI TẬP
bang để đến khi tốt nghiệp ít nhất có 100 sinh viên thuộc cùng 1
Bài 3: Hỏi phải có bao nhiêu sinh viên tham gia học đến từ 50
15
Nguyễn Quỳnh Diệp
Toán rời rạc
bang.
4.3. CHỈNH HỢP VÀ TỔ HỢP
Nguyễn Quỳnh Diệp
Toán rời rạc
16
HOÁN VỊ
• 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:
Nguyễn Quỳnh Diệp
Toán rời rạc
{ a, b, c} {b, a, c} {b, c, a} {c, b, a} {c, a, b} {a, c, b}
17
CHỈNH HỢP
• 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
Toán rời rạc
• Số hoán vị của tập n phần tử là: P(n,n) = n!
18
HOÁN VỊ VÀ CHỈNH HỢP
Ví dụ 1:
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?
Ví dụ 2:
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ụ 3:
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?
Nguyễn Quỳnh Diệp
Toán rời rạc
19
TỔ HỢP
• 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
Toán rời rạc
20
TỔ HỢP
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)
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.
Nguyễn Quỳnh Diệp
Toán rời rạc
21
BÀI TẬP
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:
Bài 4: Có sáu ứng cử viên tranh cử chức thống đốc bang.
22
Nguyễn Quỳnh Diệp
Toán rời rạc
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
22
4.4. CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG
Nguyễn Quỳnh Diệp
Toán rời rạc
23
CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG
• 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.
Định lí 1
Số các chỉnh hợp lặp chập r từ n phần tử bằng nr.
Ví dụ: • Có bao nhiêu xâu gồm hai kí tự sinh ra từ tập {a, b, c}
3.3 = 32 = 9
aa, ab, ac, bb, ba, bc, cc, ca, cb
Nguyễn Quỳnh Diệp
Toán rời rạc
24
CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG
• 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.
Định lí 2
Có C(n+r-1,r) số tổ hợp lặp chập r từ tập n phần tử.
Ví dụ: • Có bao nhiêu tổ hợp lặp chập 2 sinh ra từ tập {a, b, c}
= 6
C(3+2-1,2) = C(4,2) =
4! 2!(4−2)!
aa, bb, cc, ab, bc, ac,
Nguyễn Quỳnh Diệp
Toán rời rạc
25
CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG
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:
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?
Ví dụ 3:
Nguyễn Quỳnh Diệp
Toán rời rạc
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ờ.
26
CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG
Tổ hợp và chỉnh hợ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, 𝑟) =
Nguyễn Quỳnh Diệp
Toán rời rạc
(𝑛 + 𝑟 − 1)! 𝑟! 𝑛 − 1 !
27
HOÁN VỊ VỚI CÁC PHẦN TỬ KHÔNG PHÂN BIỆT
• 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
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?
Nguyễn Quỳnh Diệp
Toán rời rạc
28
HOÁN VỊ VỚI CÁC PHẦN TỬ KHÔNG PHÂN BIỆT
Đị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
Toán rời rạc
29
SỰ PHÂN PHỐI CÁC VẬT VÀO TRONG CÁC HỘP
Đị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:
𝒏! 𝒏𝟏! 𝒏𝟐! … 𝒏𝒌!
Ví dụ: • Có bao nhiêu cách chia một cỗ bài chuẩn 52 quân thành những
Nguyễn Quỳnh Diệp
Toán rời rạc
tay bài gồm 5 quân cho 4 người chơi.
30
BÀI TẬP
hàng có 21 loại bánh khác nhau
Bài 6: Có bao nhiêu cách chọn 12 chiếc bánh từ một cửa
nhau vào sáu ngăn phân biệt.
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.
31
Nguyễn Quỳnh Diệp
Toán rời rạc
Bài 7: Có bao nhiêu cách phân phối 12 viên bi giống hệt
31
4.5. HỆ THỨC TRUY HỒI
Nguyễn Quỳnh Diệp
Toán rời rạc
32
CÁC HỆ THỨC TRUY HỒI
• 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
Toán rời rạc
33
CÁC HỆ THỨC TRUY HỒI
Định nghĩa 1:
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.
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à:
Nguyễn Quỳnh Diệp
Toán rời rạc
an = 2n+1
34
CÁC HỆ THỨC TRUY HỒI
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 = 2n và an = 5
Nguyễn Quỳnh Diệp
Toán rời rạc
35
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
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:
...
Nguyễn Quỳnh Diệp
Toán rời rạc
- 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$
36
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
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
Toán rời rạc
37
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
Số cặp thỏ trên đảo
số cặp đẻ thêm
số cũ thêm
Nguyễn Quỳnh Diệp
Toán rời rạc
38
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
Số cặp thỏ trên đảo
số cặp đẻ thêm
số cũ thêm
Nguyễn Quỳnh Diệp
Toán rời rạc
39
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
Số cặp thỏ trên đảo
số cặp đẻ thêm
số cặp cũ
Nguyễn Quỳnh Diệp
Toán rời rạc
40
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
Số cặp thỏ trên đảo
số cặp đẻ thêm
số cặp cũ
Nguyễn Quỳnh Diệp
Toán rời rạc
41
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
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ỏ
Nguyễn Quỳnh Diệp
Toán rời rạc
tháng trước, fn-2 số cặp thỏ mới đẻ
42
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
Ví dụ 3: Tháp Hà Nội. Do Édouard Lucas đưa ra cuối thế kỉ XIX.
Cọc 2
Nguyễn Quỳnh Diệp
Toán rời rạc
Cọc 1 Cọc 3
43
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
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 = 22 Hn-2 + 2 + 1 = 22(2.Hn-3 + 1) + 2 + 1 = 23Hn-3 + 22 + 2 + 1
Nguyễn Quỳnh Diệp
Toán rời rạc
... = 2n-1 H1 + 2n-2 +... + 2 + 1 = 2n-1 + 2n-2 +... + 2 + 1 = 2n -1
44
BÀI TẬP
Bài 1: Giả sử an = 2n + 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:
45
Nguyễn Quỳnh Diệp
Toán rời rạc
a) an = -n + 2 b) an = 5(-1)n – n + 2
45
BÀI TẬP
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?
46
Nguyễn Quỳnh Diệp
Toán rời rạc
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
46
4.6. GIẢI CÁC HỆ THỨC TRUY HỒI
Toán rời rạc
47
HỆ THỨC TRUY HỒI TUYẾN TÍNH
Định nghĩa 1:
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
• Tuyến tính vì vế phải là tổng các tích của các số hạng trước
• 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
Toán rời rạc
của dãy
48
HỆ THỨC TRUY HỒI TUYẾN TÍNH
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 Bn =nBn-1 không có hệ số hằng
Nguyễn Quỳnh Diệp
Toán rời rạc
- Hệ thức truy hồi Hn = 2Hn-1 + 1 không là thuần nhất
49
GIẢI HỆ THỨC TRUY HỒI TUYẾN TÍNH
Phương pháp cơ bản: • Tìm nghiệm dạng an = rn , trong đó r là hằng số • an = rn là nghiệm của HTTH: an=c1an-1+ c2an-2 +... +ckan-k
nếu và chỉ nếu rn = c1rn-1 + c2rn-2 +... +ckrn-k (*)
• Chia cả 2 vế cho rn-k . Khi đó (*) tương đương phương trình:
• Do đó, an = rn là nghiệm nếu và chỉ nếu r là nghiệm phương trình
rk - c1rk-1 - c2rk-2 - ... +ck-1r – ck = 0 (1)
(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ệ
Nguyễn Quỳnh Diệp
Toán rời rạc
thức truy hồi
50
GIẢI HTTH TUYẾN TÍNH BẬC 2
Định lí 1:
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 n + 2r2
với n = 0, 1, 2,... trong đó 1, 2 là các hằng số.
Ví dụ 1:
Tìm nghiệm của hệ thức truy hồi
Nguyễn Quỳnh Diệp
Toán rời rạc
an = an-1 + 2an-2 với a0 = 2, a1 = 7
51
GIẢI HTTH TUYẾN TÍNH BẬC 2
Định lí 2:
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
n
an = 1r0
n + 2nr0
với n = 0, 1, 2 ,... trong đó 1, 2 là các hằng số.
Tìm nghiệm của hệ thức truy hồi
Ví dụ 2:
Nguyễn Quỳnh Diệp
Toán rời rạc
an = 6an-1 - 9an-2 với a0 = 1, a1 = 6
52
GIẢI HTTH TUYẾN TÍNH TỔNG QUÁT
Định lí 3:
rk – c1rk-1 – ... – ck =0
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 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
n,
an = 1r1
n + 2r2
n + ... + krk với n = 0, 1, 2 ,... trong đó 1, 2 ,..., k là các hằng số.
Tìm nghiệm của hệ thức truy hồi
Ví dụ 3:
Nguyễn Quỳnh Diệp
Toán rời rạc
an = 6an-1 - 11an-2 + 6an-3 với a0 = 2, a1 = 5, a2 = 15
53
BÀI TẬP
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
d) an = an-1 + 2 e) an = an-1
c)an = an-1 + an-4 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
Nguyễn Quỳnh Diệp
Toán rời rạc
c) an = 4an-1 - 4an-2 , với n 2, a0 = 6, a1 = 8
54
4.7. NGUYÊN LÍ BÙ TRỪ
Nguyễn Quỳnh Diệp
Toán rời rạc
55
NGUYÊN LÍ BÙ TRỪ
• 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 |
Ví dụ 1: 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ụ 2: 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?
Nguyễn Quỳnh Diệp
Toán rời rạc
56
NGUYÊN LÍ BÙ TRỪ
• Trường hợp 3 tập hợp: | A B C | = | A | + | B | + | C | - | A B | - | A C | - | C B |
Nguyễn Quỳnh Diệp
Toán rời rạc
+ | A B C |
57
NGUYÊN LÍ BÙ TRỪ
Ví dụ 1: 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?
Nguyễn Quỳnh Diệp
Toán rời rạc
58
NGUYÊN LÍ BÙ TRỪ
Định lí 1:
NGUYÊN LÍ BÙ TRỪ. Cho A1 , A2,A3 là các tập hữu hạn. Khi đó:
𝑨𝒊 − |𝑨𝒊 ∩ 𝑨𝒋|
𝟏≤𝒊<𝒋≤𝒏
+
|𝑨𝒊 ∩ 𝑨𝒋∩ 𝑨𝒌 | − … + −𝟏 𝒏+𝟏| 𝑨𝟏 ∩ 𝑨𝟐 ∩ ⋯ ∩ 𝑨𝒏|
𝟏≤𝒊<𝒋<𝒌≤𝒏
Nguyễn Quỳnh Diệp
Toán rời rạc
𝑨𝟏 ∪ 𝑨𝟐 ∪ ⋯ ∪ 𝑨𝒏 = 𝟏≤𝒊≤𝒏
59
NGUYÊN LÍ BÙ TRỪ
Ví dụ:
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.
Nguyễn Quỳnh Diệp
Toán rời rạc
60
BÀI TẬP
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?
61
Nguyễn Quỳnh Diệp
Toán rời rạc
61
DẠNG KHÁC CỦA NGUYÊN LÍ BÙ TRỪ
• 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
’ ...Pk
’ ) = N - | A1 A2 ... An |
Nguyễn Quỳnh Diệp
Toán rời rạc
62
ỨNG DỤNG NGUYÊN LÍ BÙ TRỪ
Ví dụ 1: Phương trình x1 + x2 + x3 = 11 có bao nhiêu nghiệm, trong đó x1, x2, x3 là các số nguyên không âm với x1 3, x2 4 và x3 6.
Ví dụ 2: Tìm số các số nguyên tố không vượt quá 100?
Nguyễn Quỳnh Diệp
Toán rời rạc
63
4.4. CÁC HỆ SỐ NHỊ THỨC
Nguyễn Quỳnh Diệp
Toán rời rạc
64
CÁC HỆ SỐ NHỊ THỨC
• Nhị thức là tổng của hai số hạng
Định lí nhị thức
𝑪 𝒏, 𝒋 𝒙𝒏−𝒋𝒚𝒋
𝒏 (𝒙 + 𝒚)𝒏= 𝒋=𝟎
= 𝑪 𝒏, 𝟎 𝒙𝒏 + 𝑪 𝒏, 𝟏 𝒙𝒏−𝟏𝒚 + ⋯ + 𝑪 𝒏, 𝒏 − 𝟏 𝒙𝒚𝒏−𝟏 + 𝑪(𝒏, 𝒏)𝒚𝒏
Nguyễn Quỳnh Diệp
Toán rời rạc
Cho x và y là hai biến và n là một số nguyên dương. Khi đó:
65
CÁC HỆ SỐ NHỊ THỨC
Ví dụ 1: Tìm khai triển biểu thức (x+y)4
𝐶 4, 𝑗 𝑥4−𝑗𝑦𝑗
4 (𝑥 + 𝑦)4= 𝑗=0
= 𝐶 4,0 𝑥4 + 𝐶 4,1 𝑥3𝑦 + 𝐶 4,2 𝑥2𝑦2 + 𝐶 4,3 𝑥𝑦3 + 𝐶 4,4 𝑦4
= 𝒙𝟒 + 𝟒𝒙𝟑𝒚 + 𝟔𝒙𝟐𝒚𝟐 + 𝟒𝒙𝒚𝟑 + 𝒚𝟒
Ví dụ 2: Tìm hệ số của x12y13 khai triển biểu thức (2x-3y)25
Nguyễn Quỳnh Diệp
Toán rời rạc
66
CÁC HỆ SỐ NHỊ THỨC
Nếu n là số nguyên không âm, thì: 𝒏
Hệ quả 1
𝑪 𝒏, 𝒌 = 𝟐𝒏
𝒌=𝟎
𝒏
Nếu n là số nguyên dương, khi đó:
Hệ quả 2
(−𝟏)𝒌𝑪 𝒏, 𝒌 = 𝟎
Nếu n là số nguyên không âm, thì: 𝒏
𝒌=𝟎
Hệ quả 3
𝟐𝒌𝑪 𝒏, 𝒌 = 𝟑𝒏
Nguyễn Quỳnh Diệp
Toán rời rạc
𝒌=𝟎
67
HẰNG ĐẲNG THỨC PASCAL VÀ TAM GIÁC PASCAL
Định lí 1
HẰNG ĐẲNG THỨC PASCAL. Cho n và k là các số nguyên dương, với n k. Khi đó:
𝑪 𝒏 + 𝟏, 𝒌 = 𝑪 𝒏, 𝒌 − 𝟏 + 𝑪(𝒏, 𝒌)
= +
Nguyễn Quỳnh Diệp
Toán rời rạc
𝑛 + 1 𝑘 𝑛 𝑘 − 1 𝑛 𝑘
68
HẰNG ĐẲNG THỨC PASCAL VÀ TAM GIÁC PASCAL
=
+
Nguyễn Quỳnh Diệp
Toán rời rạc
𝑛 + 1 𝑘 𝑛 𝑘 − 1 𝑛 𝑘
69
BÀI TẬP
Bài 8: Tìm hệ số của x101y99 trong khai triển của (2x-3y)200
70
Nguyễn Quỳnh Diệp
Toán rời rạc
Bài 7: Tìm khai triển (x + y)7
70
84
Nguyễn Quỳnh Diệp
