Có một cầu thang gồm 15 bậc, với bậc 5, 10 và 15 bị gãy và không được dừng lại. Có bao nhiêu cách để đi hết cầu thang này, nếu mỗi lần được phép đi bộ 1 hoặc 2 bước?
K
Khách
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Những câu hỏi liên quan
17 tháng 9 2016
Gọi \(S_n\) là cách thỏa ycđp
Muốn lên và xuống thang n bậc \(\left(n>3\right)\) có 3 cách :
- Bước tới bậc n-1 rồi bước 1 bậc để lên n và xuống 1 bậc: 1 cách.
- Bước tới bậc n-2 rồi bước 2 bậc để lên n, sau đó xuống 2 bậc hoặc bước lên tửng bậc, xuống từng bậc hoặc xuống 2 bậc: 3 cách.
- Bước tới bậc n-3 để lên n rồi xuống thang: 9 cách (lấy theo VD cho nhanh).
Ta có hệ thức truy hồi, với \(n>3\)3
\(S_n=S_{n-1}+S_{n-2}+S_{n-3}\)
Khởi tạo : \(S_1=1,S_2=3,S_3=9\)
Suy ra : \(S_{11}=157+289+531=977\) cách .
Do 1 lần chỉ được bước 1 hoặc 2 bước nên để bước lên bậc thứ 6 ta phải bước đến bậc thứ 4. Tương tự với các bậc còn lại.
Ta sẽ tính số cách bước từ bậc 1 đến bậc 4, số cách bước từ bậc 6 đến bậc 9, từ bậc 11 đến bậc 14.
Từ bậc 1 đến bậc 4 có 5 cách đi: 1 - 1 - 1 - 1, 2 - 1 - 1, 1 - 2 - 1, 1 - 1 - 2, 2 - 2.
Từ bậc 6 đến 9 có 3 cách đi: 1 - 1 - 1, 1 - 2, 2 - 1.
Từ 11 đến 14 có 3 cách đi: 1 - 1 - 1, 1 - 2, 2 - 1.
Tổng cộng có: 5.3.3 = 45 cách.