Ham sinh va cong thuc e quy – Phần 1 lý thuyết về hàm sinh và công thức đệ quy 1 hàm sinh là bài – StuDocu
Phần 1
lý thuyết về hàm sinh và công thức đệ quy
1
hàm sinh là bài toán đếm
Giả sử {I n=1,2,3,4,…,} là một dãy số .ta viết dãy này như là dãy vô hạn phần tử ,tuy nh
iên ta coi rằng
nó bao gồm cả trường hợp dãy hữu hạn . Nếu ,,,…, là dãy hữu hạn , thì ta sẽ biến nó thành dãy vô hạn
bằng cáh đặt =0,i>m.
Định nghĩa
. hàm sinh ra dãy số đã chi như là dãy hệ số của nó. Nếu dãy là hữu hạn thì sẽ tìm được m
sao cho ,i>m.trong trươg fhowpj này là một đa thức bậc m
ví dụ
một trong những nguồn gốc dẫn đến định nghĩa hàm sinh chính là định lý về khai triể
n nhị thức :
hàm
=
Sinh ra dãy các hệ số tổ hợp
{ =C(m,k),k=0,1,2,3,….,m}
Bởi vì
=
2 hàm sinh và công thức đệ quy
ở mụcnày sẽ tình bày phương pháp sinh để tìm công thức dưới dạng hiện cho số hạng
tổng quát cảu dãy số xác định bởi công thức đệ quy . nội dung phương pháp có thể
trình bày như sau . giả sử ta có {
} là dãy số được xác định theo công thức đệ quy xây dựng hàm
sinh cảu dãy số này theo công thức
=+x+ +….=
Sử dụng các tính chất của dãy số ( suy từ công thức để quy xác định nó ) ta có thể tìm được c
ông thức
gỉa tích cho hàm sinh . từ công thức tìm được ta sẽ khai triển hà
m dưới dạng chuôix lũy thừa , và từ
đó tìm được công thức cho hàm .
T
rước hết ta đưa ra một số phép toán đối với hàm sinh .g
iả sử
= ,=
Là hai hàm sinh còn là số thực , khi đó
+=
=
Tích côsi của hai hàm và
=
T
rong đó
= +++…+=
Từ giả thích ta biết rằng nếu chuỗi hội tụ ở điểm lân cận điểm 0 thì tổng của
nó luôn là hàm giả thích
trong lân cận này và
=(0)/k!,k=0,1,2,3,….
Khi đó chuỗi chính là khai triển macloẻncủa hàm , nếu như có một tương ứng 1-1 giữa motọ hà
m giải
thích và một chuỗi hội tụ trong lân cận 0
T
rong việc áp dụng hàm sinh ta thương sử dụng các c
ông thức sau :
1/=
Mà trường hợp riêng cảu nó là
1/(1-rx)=1+rx++….
Phần 2 một số bài toán minh họa
Ví dụ 1
Tìm hàm sinh cho là một số cách chọn ra n quả từ 4 loại quả : táo, chuối , ca
m và đào ( mỗi loại đều
có số lượng là n) mà trong đó có sẵn một số chẵn quả táo , số lượng chuối chia hế
t cho 5, không quá 4
quả cam và không quá một của đào?
Giải
hàm sinh có dạng
= ( 1+ ++….)(1+++…)(1+x+++)(1+x)
=[1/(1-)][1/(1-)][(1-)/(1-x)](1+x)
=[1/((1-x)(1+x))][1/(1-x)](1+x)
=1/
Từ đó ta có thể tìm công thức hiện cho lời giải bởi vì
1/===
Vậy =n+1
Ví dụ 2
Dãy fibonaci là dãy được xác định bởi công thức đệ quy