Chủ đề này có 4 trả lời

[Sagittarius912]

Có bao nhiêu cách lát đường đi kích thước $3\times 2n$ bằng các viên gạch có kích thước $1 \times 2$?

[LNH]

Có bao nhiêu cách lát đường đi kích thước $3\times 2n$ bằng các viên gạch có kích thước $1 \times 2$?

Gọi  $c_n$ là số cách lát đường đi kích thước $3\times 2n$. Dễ thấy $c_1=3$. Để tính $c_n$, ta chia các cách lát đường đi kích thước $3\times 2n$ thành $n$ lọai, trong đó lọai thứ $k$ là các cách lát mà phần đường đi $3\times 2h$ đầu tiên được phủ kín hòan tòan, nhưng không tồn tại $i< k$ sao cho phần đường đi $3\times 2i$  đầu tiên được phủ kín hòan tòan. Gọi $A_k$ là tập hợp các cách lát lọai $k$ thì rõ ràng $c_{n}=\sum_{i=1}^{n}\left | A_i \right |$. Dễ dàng nhận thấy $\left | A_{1} \right |=3c_{n-1}$ (phần đường đi $3\times 2$ được lát kín bằng $3$ cách, phần còn lại được lát bằng $c_{n-1}$ cách). Dễ dàng thấy rằng có hai cách phủ phần đường đi $3\times 2k$ cho các cách phủ thuộc $A_k$ với $k =2, 3, …, n$ là cách phủ và cách phủ thu được bằng cách lấy đối xứng.

Từ đó suy ra $A_{k}=2c_{n-k}$. Như vậy, ta có  $c_{n}=3c_{n-1}+2c_{n-2}+...+2$. Ta thay $n$ thành $n+1$:

            $c_{n+1}=3c_n + 2c_{n-1} + 2c_{n-2} + … + 2$

Từ đó, trừ hai đẳng thức cuối cùng vế theo vế, ta được

$c_{n+1} – c_n = 3c_n – c_{n-1}$

$\Leftrightarrow c_{n+1}=4c_{n}-c_{n-1}$

Sau đó theo công thức sai phân ta tìm ra công thức tổng quát

Xong

Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 31-07-2013 - 16:04

[LNH]

Không biết bài này có thể đếm bằng phương pháp thiết lập song ánh không nhỉ, đọc trong cái tài liệu song ánh thấy có bài này

Mọi người giúp mình nhé

[AnnieSally]

[LNH]

Nhưng tớ đang cần làm bằng pp song ánh mà  , cái tài liệu trên cũng làm bằng truy hồi giống tớ thôi(lật tẩy rồi  )