1. Tìm hệ thức truy hồi cho số các xâu có độ dài n được tạo từ các phần tử của tập {a,b,c}, chưa hoặc các xâu con aa hoặc các xâu con bb?
2. Tìm hệ thức truy hồi cho xâu có độ dài n (n >4 ) được tạo từ các phần tử của tập {x,y,z,t} và không chứa các xâu con xx, yy, zz, tt?
1/ Gọi $A_{n},B_{n},C_{n} $ lần lượt là tập các xâu kích thước $n$ thỏa đề bài và tận cùng là $a, b, c$. Như vậy số các xâu thỏa yêu cầu là $S_{n}=\left | A_{n} \right |+\left | B_{n} \right |+\left | C_{n} \right |$.
Ta có:
$\left | C_{n} \right |=\left | A_{n-1}\right | +\left | B_{n-1}\right | +\left | C_{n-1}\right | $
$\left | A_{n} \right | =\left | B_{n-1}\right | +\left | C_{n-1}\right |$
$\left | B_{n} \right |=\left | A_{n-1}\right |+\left | C_{n-1}\right |$
Công vế với vế:
$S_{n} =2S_{n-1} +\left | C_{n-1}\right |=2S_{n-1}+(\left | A_{n-2}\right | +\left | B_{n-2}\right | +\left | C_{n-2}\right | )$ hay ta có hệ thức truy hồi:
$S_{n} =2S_{n-1}+S_{n-2},n \geq 3 $
2/ Lâp luận tương tự bài 1/, ta có:
$\left | X_{n} \right | =\left |Y_{n-1} \right | +\left |Z_{n-1} \right | +\left |T_{n-1} \right | $
$\left | Y_{n} \right | =\left |X_{n-1} \right | +\left |Z_{n-1} \right | +\left |T_{n-1} \right | $
$\left | Z_{n} \right | =\left |X_{n-1} \right | +\left |Y_{n-1} \right | +\left |T_{n-1} \right | $
$\left | T_{n} \right |=\left |X_{n-1} \right | +\left |Y_{n-1} \right | +\left |Z_{n-1} \right | $
Cộng vế với vế:
$S_{n} =3(\left |X_{n-1} \right | +\left |Y_{n-1} \right | +\left |Z_{n-1} \right | +\left |T_{n-1} \right | ) $ hay ta có HTTH :
$S_{n} =3S_{n-1},n \geq 2 $
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 17-04-2021 - 15:10