Toán 11 Giải bài toán đếm bằng phương pháp truy hồi

[boywwalkman]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Mình đang bị bí bài này. Xin nhờ mọi người giúp đỡ.
Đề bài: Từ tập E={1;2;3;4;5;6;7;8;9} có thể lập được bao nhiêu số tự nhiên có n chữ số mà trong đó chữ số 1 xuất hiện lẻ lần, chứ số 2 xuất hiện chắn lần (n là số lần nguyên dương cho trước).
Xin cảm ơn.
Mình đoán là gọi đáp số là [tex]x_{n}[/tex] sau đó tìm tương quan với n+1 và n+2 nhưng làm không ra.

 

[7 1 2 5]

Lần lượt gọi [TEX]A_n,B_n,C_n,D_n[/TEX] là tập hợp các số có n chữ số và: có lẻ chữ số 1 và chẵn chữ số 2, lẻ chữ số 1 và lẻ chữ số 2, chẵn chữ số 1 và chẵn chữ số 2, chẵn chữ số 1 và lẻ chữ số 2. [tex]\Rightarrow |A_n|+|B_n|+|C_n|+|D_n|=9^n;A_n,B_n,C_n,D_n[/tex] đôi một không giao nhau.
Khi đó nhận thấy có 1 song ánh đi từ [TEX]A_n \rightarrow D_n[/TEX],[TEX]B_n \rightarrow C_n[/TEX] là phép biến đổi các chữ số 1 thành 2 và chữ số 2 thành 1; nên [TEX]|A_n|=|D_n|,|B_n|=|C_n|[/TEX]
Lại có:
+ Từ 1 số ở [TEX]A_n[/TEX] ta có thể tạo ra 1 số thuộc [TEX]A_{n+1}[/TEX] bằng cách thêm 1 chữ số thuộc [tex]\left \{ 3;4;5;6;7;8;9 \right \}[/tex] ở phía sau số đó. Ta thấy từ 1 số thuộc [TEX]A_n[/TEX] thì tạo ra được 7 số thuộc [TEX]A_{n+1}[/TEX]
+ Từ 1 số ở [TEX]B_n[/TEX] ta có thể tạo ra 1 số thuộc [TEX]A_{n+1}[/TEX] bằng cách thêm chữ số 2 ở phía sau số đó. Ta thấy từ 1 số thuộc [TEX]B_n[/TEX] tạo ra được 1 số thuộc [TEX]A_{n+1}[/TEX]
+ Từ 1 số ở [TEX]C_n[/TEX] ta có thể tạo ra 1 số thuộc [TEX]A_{n+1}[/TEX] bằng cách thêm chữ số 1 ở phía sau số đó. Ta thấy từ 1 số thuộc [TEX]C_n[/TEX] tạo ra được 1 số thuộc [TEX]A_{n+1}[/TEX]
+ + Từ 1 số ở [TEX]D_n[/TEX] ta không thể tạo ra 1 số thuộc [TEX]A_{n+1}[/TEX].
Từ đó ta có: [tex]|A_{n+1}|=7|A_n|+|B_n|+|C_n|=5|A_n|+(|A_n|+|B_n|+|C_n|+|D_n|)=5|A_n|+9^n[/tex]
[TEX]\Rightarrow x_{n+1}=5x_n+9^n,x_1=1[/TEX]
Ta tính được [TEX]x_n=\frac{9^n-5^n}{4}[/TEX]