Từ các chữ số {1,3,5,9} có thể lập được bao nhiêu số tự nhiên có 2019 chữ số và chia hết cho 3 (có thể giải bằng phương pháp truy hồi giúp mình không ạ )
Truy hồi trong tổ hợp đếm mình chưa làm bao giờ, mà nghe hay hay nên mình sẽ thử
Gọi $A_n$ là số các số có $n$ chữ số chia $3$ dư $0$
$B_n$ là số các số có $n$ chữ số chia $3$ dư $1$
$C_n$ là số các số có $n$ chữ số chia $3$ dư $2$
Xét các số có 1 chữ số: $A_1 = 2$ (3 và 9), $B_1 = 1$ (số 1), $C_1 = 1$ (số 5)
Xét các số có 2 chữ số: Ta tạo các số có 2 chữ số bằng cách ghép thêm các số có 1 chữ số vào sau các số có 1 chữ số
Khi đó $A_2 = A_1 \cdot 2 + B_1 \cdot 1 + C_1 \cdot 1 = 2A_1 + B_1 + C_1$
$B_2 = A_1 \cdot 1 + B_1 \cdot 2 + C_1 \cdot 1 = A_1 + 2B_1 + C_1$
$C_2 = A_1 \cdot 1 + B_1 \cdot 1 + C_1 \cdot 1 = A_1 + B_1 + 2C_1$
Xét các số có 3 chữ số: Ta tạo các số có 3 chữ số bằng cách ghép thêm các số có 1 chữ số vào sau các số có 2 chữ số
Khi đó $A_3 = A_2 \cdot 2 + B_2 \cdot 1 + C_2 \cdot 1 = 2A_2 + B_2 + C_2$
$B_2 = A_2 + 2B_2 + C_2$
$C_2 = A_2 + B_2 + 2C_2$
...
Xét các số có n chữ số: Ta tạo các số có n chữ số bằng cách ghép thêm các số có 1 chữ số vào sau các số có n-1 chữ số
Khi đó $A_n = 2A_{n-1} + B_{n-1} + C_{n-1}$
$B_n = A_{n-1} + 2B_{n-1} + C_{n-1}$
$C_n = A_{n-1} + B_{n-1} + 2C_{n-1}$
Như vậy hệ thức truy hồi ta có là $\begin{cases} A_1 = 2 \\ B_1 = 1 \\ C_1 = 1 \\ A_n = 2A_{n-1} + B_{n-1} + C_{n-1} \\ B_n = A_{n-1} + 2B_{n-1} + C_{n-1} \\ C_n = A_{n-1} + B_{n-1} + 2C_{n-1} \end{cases}$
Hệ này giải cũng dễ: Cộng vế theo vế 3 cái cuối có $S_n = A_n + B_n + C_n = 4(A_{n-1} + B_{n-1} + C_{n-1}) = 4S_{n-1}$
Suy ra $S_n = 4^{n-1} S_1 = 4^{n-1} \cdot (A_1 + B_1 + C_1) = 4^n$
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
