Có bao nhiêu cách lát ?
#1
Posted 01-03-2013 - 23:13
- Oral1020, LNH and Tungvansoan like this
#2
Posted 31-07-2013 - 16:00
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
Edited by lenhathoang1998, 31-07-2013 - 16:04.
- Sagittarius912, nhatquangsin, AnnieSally and 1 other like this
#3
Posted 17-08-2013 - 21:12
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é
#4
Posted 17-08-2013 - 21:14
#5
Posted 17-08-2013 - 21:59
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 )
- nhatquangsin and AnnieSally like this
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users