Giáo trình Toán rời rạc - Bài 16: Công thức truy hồi - Trần Vĩnh Đức
Công thức truy hồi
Trần Vĩnh Đức
HUST
Ngày 24 tháng 7 năm 2018
1 / 45
Nội dung
Ví dụ
Công thức truy hồi
Công thức truy hồi và hàm sinh
Số Catalan
Công thức truy hồi tuyến tính
Ví dụ
Một quần thể vi trùng có số lượng cá thể tăng gấp đôi sau mỗi giờ.
Nếu thoạt đầu có 5 cá thể hỏi sau 5 giờ số lượng của chúng là bao
nhiêu?
{
an = 2an−1
a0 = 5
3 / 45
Bài tập
Hãy tìm công thức tường minh cho dãy
{
an = 2an
a0 = 5
4 / 45
Ví dụ
Xét một cầu thang với n bậc thang. Có bao nhiêu cách để đi lên
cầu thang nếu chúng ta có thể leo lên 1 bậc hoặc 2 bậc trong mỗi
bước?
S1 = 1
S2 = 2
Sn+2 = Sn+1 + Sn
với
n ≥ 1
5 / 45
Ví dụ
Có bao nhiêu xâu nhị phân độ dài n không chứa hai bit 0 liên tiếp?
an+1 = an + an−1
a1 = 2
a2 = 3
6 / 45
Bài tập
Hãy dùng kỹ thuật hàm sinh để tìm công thức tường minh cho dãy
an+1 = an + an−1
a1 = 2
a2 = 3
7 / 45
Ví dụ
Có bao nhiêu xâu tam phân độ dài n không chứa dãy con ”012”?
an+3 = 3an+2 − an
a1 = 3
a2 = 9
8 / 45
Nội dung
Ví dụ
Công thức truy hồi
Công thức truy hồi và hàm sinh
Số Catalan
Công thức truy hồi tuyến tính
Công thức truy hồi
Định nghĩa
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.
10 / 45
Ví dụ
Xét dãy số ⟨an⟩ thỏa mãn công thức
{
an = an−1 − an−2
a0 = 3a1 = 5
Từ công thức truy hồi ta có
a2 = a1 − a0 = 5 − 3 = 2
a3 = a2 − a1 = 2 − 5 = −3
11 / 45
Định nghĩa
Một dãy số được gọi là nghiệm của công thức truy hồi nếu các số
hạng của nó thỏa mãn công thức truy hồi này.
12 / 45
Ví dụ
▶
Xét công thức truy hồi
an = 2an−1 − an−2
với n ≥ 2.
▶
Dãy số ⟨an⟩ với an = 3n có phải là nghiệm của hệ thức truy
hồi trên hay không?
Còn dãy an = 2n?
Còn dãy an = 5?
▶
▶
13 / 45
Ví dụ
Giả sử một người gửi 10, 000 đô la vào tài khoản của mình tại một
ngân hàng với lãi 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 ngân hàng.
{
Pn = Pn−1 + 0.11Pn−1 = 1.11Pn−1
P0 = 10, 000 đô la.
14 / 45
Ví dụ
▶
Một hệ máy tính coi một xâu các chữ số hệ thập phân là một
từ mã hợp lệ nếu nó chứa một số chẵn chữ số 0.
▶
Chẳng hạn, 1230407869 là hợp lệ, còn 120987045608 là
không hợp lệ.
▶
▶
Giả sử an là số các từ mã độ dài n.
Hãy tìm công thức truy hồi cho an.
an = 9an−1 + (10n−1 − an−1
)
= 8an−1 + 10n−1
.
15 / 45
Ví dụ
▶
Chúng ta vẽ n đường thẳng trên giấy sao cho mọi cặp đường
thẳng đều cắt nhau và không có ba đường thẳng nào đồng
quy.
▶
Các đường thẳng này chia mặt phẳng thành bao nhiêu miền?
2
2
2
3
3
4
1
1
1
(a)
(c)
(b)
16 / 45
Ví dụ (Chọn không lặp)
Đặt an,k là số cách chọn tập con k phần tử từ tập n phần tử. Hãy
tìm công thức truy hồi cho ak,n
.
an,k = an−1,k + an−1,k−1
(Đẳng thức Pascal)
17 / 45
Ví dụ (Bỏ bóng)
Hãy tìm công thức truy hồi cho số cách bỏ n quả bóng giống nhau
và k chiếc hộp phân biệt sao cho mỗi hộp chỉ có 2 hoặc 3 hoặc 4
quả bóng.
an,k = an−2,k−1 + an−3,k−1 + an−4,k−1
.
18 / 45
Ví dụ (Hệ thức truy hồi)
Tìm công thức truy hồi cho: Số xâu tam phân độ dài n với một số
chẵn 0 và một số lẻ 1.
an = bn−1 + cn−1 + an−1
bn = 3n−1 − cn−1
cn = 3n−1 − bn−1
19 / 45
Nội dung
Ví dụ
Công thức truy hồi
Công thức truy hồi và hàm sinh
Số Catalan
Công thức truy hồi tuyến tính
Tải về để xem bản đầy đủ
45 trang
18320
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 16: Công thức truy hồi - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_toan_roi_rac_bai_16_cong_thuc_truy_hoi_tran_vinh.pdf
