Bài giảng Toán rời rạc: Công thức truy hồi

Công thức truy hồi

HUST

Trần Vĩnh Đức

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

1 / 45

Ngày 24 tháng 7 năm 2018

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

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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?

{

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

3 / 45

an = 2an(cid:0)1 a0 = 5

Bài tập Hãy tìm công thức tường minh cho dãy

{

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

4 / 45

an = 2an a0 = 5

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?

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

5 / 45

với n (cid:21) 1 S1 = 1 S2 = 2 Sn+2 = Sn+1 + Sn

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?

8 ><

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

6 / 45

>: an+1 = an + an(cid:0)1 a1 = 2 a2 = 3

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

8 ><

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

7 / 45

>: an+1 = an + an(cid:0)1 a1 = 2 a2 = 3

Ví dụ Có bao nhiêu xâu tam phân độ dài n không chứa dãy con ”012”?

8 ><

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

8 / 45

>: an+3 = 3an+2 (cid:0) an a1 = 3 a2 = 9

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

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

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.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

10 / 45

Ví dụ Xét dãy số ⟨an⟩ thỏa mãn công thức

{

an = an(cid:0)1 (cid:0) an(cid:0)2 a0 = 3a1 = 5

Từ công thức truy hồi ta có

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

11 / 45

a2 = a1 (cid:0) a0 = 5 (cid:0) 3 = 2 a3 = a2 (cid:0) a1 = 2 (cid:0) 5 = (cid:0)3

Đị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.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

12 / 45

Ví dụ

▶ Xét công thức truy hồi

với n (cid:21) 2: an = 2an(cid:0)1 (cid:0) an(cid:0)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?

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

13 / 45

▶ Còn dãy an = 2n? ▶ Còn dãy an = 5?

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.

{

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

14 / 45

Pn = Pn(cid:0)1 + 0:11Pn(cid:0)1 = 1:11Pn(cid:0)1 P0 = 10; 000 đô la:

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(cid:0)1 + (10n(cid:0)1 (cid:0) an(cid:0)1)

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

15 / 45

= 8an(cid:0)1 + 10n(cid:0)1:

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.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

16 / 45

▶ Các đường thẳng này chia mặt phẳng thành bao nhiêu miền?

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.

(Đẳng thức Pascal)

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

17 / 45

an;k = an(cid:0)1;k + an(cid:0)1;k(cid:0)1

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.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

18 / 45

an;k = an(cid:0)2;k(cid:0)1 + an(cid:0)3;k(cid:0)1 + an(cid:0)4;k(cid:0)1:

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.

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

19 / 45

an = bn(cid:0)1 + cn(cid:0)1 + an(cid:0)1 bn = 3n(cid:0)1 (cid:0) cn(cid:0)1 cn = 3n(cid:0)1 (cid:0) bn(cid:0)1

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

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

Công thức truy hồi tuyến tính

Ví dụ Tìm hàm sinh cho dãy số là nghiệm của công thức truy hồi

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

21 / 45

an = an(cid:0)1 + n a0 = 1

Ví dụ (Chọn không lặp) Đặt gn(x) là họ các hàm sinh

gn(x) = an;0 + an;1x + (cid:1) (cid:1) (cid:1) + an;kxk + : : : an;nxn

thỏa mãn công thức truy hồi

với mọi k > n an;k = an(cid:0)1;k + an(cid:0)1;k(cid:0)1 an;0 = an;n = 1 an;k = 0

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

22 / 45

Hãy tìm dạng đóng cho hàm sinh gn(x) và dùng nó để tìm công thức tường minh cho an;k.

Giải

n∑

k=1

k=1 n∑

n(cid:0)1∑

gn(x) (cid:0) 1 = an;kxk = (an(cid:0)1;kxk + an(cid:0)1;k(cid:0)1xk)

k=1

h=0

= an(cid:0)1;kxk + x an(cid:0)1;hxk)

= gn(cid:0)1(x) (cid:0) 1 + xgn(cid:0)1(x)

Vậy ta được

gn(x) = gn(cid:0)1(x) + xgn(cid:0)1(x) = (1 + x)gn(cid:0)1(x)

Giải công thức truy hồi trên, ta được

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

23 / 45

gn(x) = (1 + x)ng0(x) = (1 + x)n:

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

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

Công thức truy hồi tuyến tính

Số Catalan Có bao nhiêu cách đặt dấu ngoặc cho tổng n số để chỉ định trình tự thực hiện phép cộng?

Ví dụ Với n = 4 ta có 5 khả năng:

(((a + b) + c) + d)

((a + (b + c)) + d)

((a + b) + (c + d))

(a + ((b + c) + d))

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

25 / 45

(a + (b + (c + d)))

Công thức truy hồi cho các số Catalan

n(cid:0)1∑

Cn = C1Cn(cid:0)1 + C2Cn(cid:0)2 + (cid:1) (cid:1) (cid:1) + Cn(cid:0)1C1

i=1

= CiCn(cid:0)i:

Công thức này suy ra từ các cách đặt dấu ngoặc:

(1 : : : n) = (1)(2 : : : n);

(1 2)(3 : : : n); (cid:1) (cid:1) (cid:1) (1 : : : n (cid:0) 1)(n):

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

26 / 45

Ta đặt C0 = 0 và ta biết C1 = 1.

Công thức truy hồi cho các số Catalan

n∑

Cn = C0Cn + C1Cn(cid:0)1 + C2Cn(cid:0)2 + (cid:1) (cid:1) (cid:1) + Cn(cid:0)1C1 + CnC0

i=0

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

27 / 45

= CiCn(cid:0)i:

Hàm sinh của số Catalan

Xét hàm sinh của Cn:

n∑

i=0

n(cid:21)1

C(x) = 0 + x + x2 + 2x3 + 5x4 + (cid:1) (cid:1) (cid:1) ∑ ∑ = 0 + Cnxn = (CiCn(cid:0)i) xn

Theo luật tích

2 + (C0C1 + C1C0)x + (C0C2 + C1C1 + C2C0)x2 + (cid:1) (cid:1) (cid:1)

n∑

i=0

n(cid:21)2

C(x)2 = C0 ) ( ∑ = 0 + 0 + xn CiCn(cid:0)i

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

28 / 45

= C(x) (cid:0) x

Hàm sinh cho các số Catalan

Giải phương trình

C(x)2 (cid:0) C(x) + x = 0:

Ta được p 1 (cid:6) C(x) =

: = 1 (cid:0) 4x 2 1 (cid:6) (1 (cid:0) 4x)1/2 2

Vì C0 = 0, ta lấy nghiệm

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

29 / 45

C(x) = : 1 (cid:0) (1 (cid:0) 4x)1/2 2

Định lý nhị thức tổng quát

Với số thực q bất kỳ, khai triển của chuỗi ) ( ) ) ( ( ( )

q n (

(1 + y)q = + y + y2 + (cid:1) (cid:1) (cid:1) + yn + (cid:1) (cid:1) (cid:1) q 0 q 1 q 2 q n ( ) có hệ số của yn được định nghĩa bởi )

q n

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

30 / 45

: := q n q(q (cid:0) 1)(q (cid:0) 2) (cid:2) (cid:1) (cid:1) (cid:1) (cid:2) [q (cid:0) (n (cid:0) 1)] n! ( ) xuất hiện từ chuỗi Taylor cho (Công thức cho hệ số tổng quát (1 + y)q.)

Bổ đề Với mỗi n (cid:21) 1,

( ( )

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

31 / 45

(cid:2) = 1/2 n ((cid:0)1)n(cid:0)1 n ) 2n(cid:0)2 n(cid:0)1 22n(cid:0)1

Định lý Hàm sinh của dãy số Catalan là

1∑

C(x) = )

n=1

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

32 / 45

= xn: 1 (cid:0) (1 (cid:0) 4x)1/2 2 ( 2n (cid:0) 2 n (cid:0) 1 1 n

Số Catalan

( )

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

33 / 45

: Cn = 1 n 2n (cid:0) 2 n (cid:0) 1

Bài tập Xét bàn cờ n (cid:2) n:

Xét đường đi ngắn nhất từ góc A tới góc B đi qua các cạnh (mỗi đường qua 2n cạnh).

1. Có bao nhiêu đường như vậy?

CuuDuongThanCong.com

https://fb.com/tailieudientucntt

34 / 45

2. Chứng minh rằng số đường không xuống dưới đường chéo chính là số Catalan Cn. ( mà 3. Hãy tìm cách chứng minh số Catalan Cn = 1 n ) 2n(cid:0)2 n(cid:0)1 không dùng hàm sinh.