Phương pháp hàm sinh

Đây là một bài viết lên trang FB của Sputnik Education và là để hưởng ứng lời yêu cầu của TS Trần Nam Dũng cung cấp các đề tài thú vị để dạy luyện học sinh giỏi tham dự thi tuyển olympic về toán.

Các bạn đọc đã có biết phương pháp hàm sinh chưa nhỉ ?

Ý tưởng của nó đơn giản như sau:

Giả sử ta phải tính một dãy các số S(n) phụ thuộc vào n, với n chạy từ 0 đến vô cùng, được cho bởi một qui tắc truy hồi hay tổ hợp gì đó. Khi đó ta viết

F(x) = \sum_n S(n) x^n

Thay vì tính S(n) cho từng n, ta tính luôn xem hàm F(x) là hàm nào. Nếu tính được F(x), thì chỉ cần lấy các đạo hàm của nó tại điểm 0 là ra được các số S(n).

Hàm F(x) gọi là hàm sinh (generating function) trong phương pháp này.

Thử lấy hai ví dụ.

Ví dụ đầu tiên là ví dụ số thỏ của Fibonacci.

Chúng là các số a(n) thỏa mãn công thức truy hồi

a(n+2) = a(n+1) + a(n)

và điều kiện ban đầu a(0) = a(1) =1.  Hỏi công thức tổng quát của a(n) như thế nào ?

Cách thông dụng để tính a(n) là dùng đại số tuyến tính, để viết được a(n) dưới dạng

a(n) = C. A^n + D. B^n với A,B, C,D là các số nào đó. Cách hàm sinh cũng sẽ cho ra kết quả tương tự:

Đặt F(x) = \sum a(n) x^n. Khi đó

F(x) = 1 + \sum a(n+1) x^{n+1} = 1 + \sum a(n-1) x^{n+1} + \sum a(n) x^{n+1} = 1 + F(x) x + F(x) x^2,

suy ra

F(x) (1 - x - x^2) = 1, hay có nghĩa là F(x) = 1/(1-x-x^2)

Có thể tách 1 - x - x^2 = (1 -Ax)(1 - Bx) , rồi viết

F(x) = C. (1- Ax)^{-1} + D. (1-Bx)^{-1}

Chú ý công thức

(1 - Ax)^{-1} = \sum (Ax)^n = \sum A^n x^n

Từ đó ta có

a(n) = C. A^n + D. B^n

giống hệt như là nếu dùng đại số tuyến tính

Ví dụ thứ hai là bài toán tổ hợp trong sách Yaglom (đã đem đố trên trang Sputnik Education): Cho 2n điểm trên vòng tròn. Hỏi có bao nhiêu cách nối khác nhau các điểm đó đôi một với nhau để được n đoạn thẳng không cắt nhau.

Để giải, gọi C(n) là số cách. Khi đó dễ thấy C(n) thỏa mãn công thức truy hồi:

C(0) = C(1) = 1,

C(n+1) = C(0)C(n) + C(1) C(n-1) + C(2) C(n-2) + \hdots + C(n) C(0)

nếu đặt F(x) = \sum C(n) x^n thì sẽ có được một phương trình cho F(x) (trong đó có xF(x)^2) rồi từ đó tính được F(x), rồi suy ra C(n) với mọi n. Đấy là gợi ý như vậy, các bạn thử tính cụ thể nhé. Công thức, nếu tôi tính không nhầm, là

C(n) = (2n)!/n!(n+1)!

Print Friendly

1 comment to Phương pháp hàm sinh

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

This blog is kept spam free by WP-SpamFree.