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

[Trần Đức Anh @@]

Bài toán: Một bộ bách khoa từ điển gồm $10$ quyển, chứng được sắp trên giá hoặc là vào đúng thứ tự của nó được ghi trên giá sách hoặc là chỗ bên cạnh. Hỏi có bao nhiêu cách sắp đạt như vậy có thể được?

Bài viết đã được chỉnh sửa nội dung bởi Trần Đức Anh @@: 15-08-2013 - 22:44

[LNH]

Bài toán: Một bộ bách khoa từ điển gồm $10$ quyển, chứng được sắp trên giá hoặc là vào đúng thứ tự của nó được ghi trên giá sách hoặc là chỗ bên cạnh. Hỏi có bao nhiêu cách sắp đạt như vậy có thể được?

Ý tưởng bài này là ta thực hiện đếm bằng truy hồi

Gọi số cách sắp đặt $n$ quyển thoả mãn đề bài là $S_n$

Dễ thấy $S_1=1$, $S_2=2$

Xét $S_{n+1}$:

Có 2 TH:

TH1: Ở vị trí $n+1$ ta xếp quyển thứ $n+1$

Dễ thấy số cách xếp thoả mãn đề bài là $S_n$

TH2: Ở vị trí thứ $n+1$ ta xếp quyển thứ $n$

Khi đó ở vị trí thứ $n$ phải là quyển thứ $n+1$

Dễ thấy số cách xếp ở TH2 là $S_{n-1}$

Vậy ta có công thức truy hồi sau:

$S_{n+1}=S_n+S_{n-1}$

Từ đây bấm máy suy ra kết quả