Xây dựng hàm sinh thỏa các điều kiện sau :
a) Hàm sinh dùng để mô tả số cách chọn 5 số nguyên từ dãy 1,2,3...,n sao cho không có 2 số nào liên tiếp nhau.
Tìm k sao cho hệ số của xk của hàm sinh là kết quả khi n = 20.
b) Hàm sinh có các hệ số ar với ar là số nghiệm nguyên của phương trình e1 + e2 + e3 + e4 = r thỏa 0 <= e1 $\leq$ e2 $\leq$ e3 $\leq$ e4
Xin mọi người giúp đỡ, em cảm ơn ạ.
a/ Ta xếp các số của dãy theo thứ tự thành 1 hàng ngang. Giả sử ta chọn 1 bộ 5 số $(a, b, c, d, e) $ mà $1\leq a< b< c< d< e\leq n$ thỏa yêu cầu. Gọi $x_{1}$ là số các số trước $a$; $x_{2}, x_{3}, x_{4}, x_{5}$ lần lượt là số các số giữa $a$ và $b$, giữa $b$ và $c$, giữa $c$ và $d$, giữa $d$ và $e$, và $x_{6}$ là số các số sau $e$ và được minh họa như sau:
$$\underset{x_{1}}{\underbrace{....}}a\underset{x_{2}}{\underbrace{....}}b\underset{x_{3}}{\underbrace{....}}c\underset{x_{4}}{\underbrace{....}}d\underset{x_{5}}{\underbrace{....}}e\underset{x_{6}}{\underbrace{....}}$$
Vậy ta có pt:
$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=n-5 $ với $x_{1}, x_{6}\geq 0$ và $ x_{i}\geq 1$ $(*)$
Ta thấy có một song ánh từ tập các bộ 5 số mà ta cần đếm đến tập các bộ nghiệm của pt $(*)$, do đó số cách chọn 5 số thỏa yêu cầu cũng là số nghiệm của $(*)$.
Ta có hàm sinh:
$G(x)=(1+x+x^{2}+x^{3}+...)(x+x^{2}+x^{3}+...)^{4}(1+x+x^{2}+x^{3}+...)=x^{4}\frac{1}{\left ( 1-x \right )^{6}}$
Hệ số của $x^{n-5}$ của hàm sinh $G(x)$ là kết quả, do đó $k=n-5=20-5=15$
b/ Đặt:
$e_{1}=x_{1}$
$e_{2}=e_{1}+x_{2}=x_{1}+x_{2}$
$e_{3}=e_{2}+x_{3}=x_{1}+x_{2}+x_{3}$
$e_{4}=e_{3}+x_{4}=x_{1}+x_{2}+x_{3}+x_{4}$
thì:
$e_{1}+e_{2}+e_{3}+e_{4}=r$ với $0\leq e_{1}\leq e_{2}\leq e_{3}\leq e_{4} \Leftrightarrow x_{4}+2x_{3}+3x_{2}+4x_{1}=r $ với $x_{i}\geq 0$
Hàm sinh cần tìm là:
$G(z)=\frac{1}{1-z}\frac{1}{1-z^{2}}\frac{1}{1-z^{3}}\frac{1}{1-z^{4}}=\prod_{i=1}^{4}\frac{1}{1-z^{i}}$
Bài viết đã được chỉnh sửa nội dung bởi dottoantap: 05-09-2018 - 13:47