Đến nội dung

Hình ảnh

Phương pháp đếm bằng hàm sinh

* * * * * 1 Bình chọn

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
Lee LOng

Lee LOng

    Trung sĩ

  • Thành viên
  • 174 Bài viết

Xét tập hợp $\left \{ 1;2;...;15 \right \}$ có bao nhiêu tập con có 4 phần tử mà không chứa 2 số liên tiếp nhau.Vị trí các phần tử trong một tập con không quan trọng. Nhờ mọi người hướng dẫn cách dùng hàm sinh!


Bài viết đã được chỉnh sửa nội dung bởi Lee LOng: 14-10-2018 - 11:14


#2
dottoantap

dottoantap

    Trung sĩ

  • Thành viên
  • 162 Bài viết

Xét tập hợp $\left \{ 1;2;...;15 \right \}$ có bao nhiêu tập con có 4 phần tử mà không chứa 2 số liên tiếp nhau.Vị trí các phần tử trong một tập con không quan trọng. Nhờ mọi người hướng dẫn cách dùng hàm sinh!

Ta xếp các số theo thứ tự thành 1 hàng ngang. Giả sử ta xếp được 1 bộ 4 số $(a, b, c, d) $ mà $1\leq a< b< c< d\leq 15$ thỏa yêu cầu. Gọi $x_{1}$ là số các số trước $a$; $x_{2}, x_{3}, x_{4}$ lần lượt là số các số giữa $a$ và $b$, giữa $b$ và $c$, giữa $c$ và $d$ và $x_{5}$ là số các số sau $d$, đượ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{....}}$$

Vậy ta có pt:

$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=15-4=11 $ với $x_{1}, x_{5}\geq 0$ và $ x_{i}\geq 1$     $(*)$

Ta thấy có một song ánh từ tập các bộ 4 số thỏa yc đến tập các bộ nghiệm của pt $(*)$, do đó số cách chọn tập con 4 phần tử thỏa yêu cầu cũng là số nghiệm của $(*)$.

Ta có hàm sinh cho  $x_{1}, x_{5}$ là: $1+x+x^{2}+x^{3}+...$; hàm sinh cho $ x_{i}$ là: $x+x^{2}+x^{3}+...$. Theo qui tắc xoắn ta được:

$G(x)=(1+x+x^{2}+x^{3}+...)^2(x+x^{2}+x^{3}+...)^{3}=\frac{x^{3}}{\left ( 1-x \right )^{5}}$

Khai triển chuỗi ta có:

$x^{3}+5x^{4}+15x^{5}+35x^{6}+70x^{7}+120x^{8}+210x^{9}+330x^{10}+495x^{11}+715x^{12}+....$

Hệ số của $x^{11}$ trong khai triển là số nghiệm của pt $(*)$ và cũng là số tập con thỏa yc đề bài và bằng $495$ tập.


++++++++++++++++++++++++++++

Everything is impossible until you do it.

“Ai không làm gì thì mới không bao giờ sai”. Cứ làm đi, đừng sợ sai, trừ khi cái sai đó là cái sai gây tai hoạ cho người khác.





2 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh


    Google (1)