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

[Nobodyv3]

Có bao nhiêu xâu tứ phân kích thước 15 lập từ $\left \{ 0,1,2,3 \right \}$ không có 2 chữ số 0 liên tiếp.

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 19-08-2023 - 02:29

[Nobodyv3]

Hàm sinh cho các Smirnov words trên tập $\left \{ 0,1,2,3 \right \}$ là $\left ( 1-\frac{4x}{1+x} \right )^{-1}=1+4x+12x^2+36x^3+108x^4+\cdots \qquad  (1)$
Ta tìm các xâu không chứa $00$: từ Smirnov words ta giữ lại các $0$ còn các $1,2,3$ có thể thay với số lượng không ràng buộc thì (1) cho ta:
$$\begin{align*} A(x)&=\left(1-\frac{x}{1+x}-\frac{\frac{3x}{1-x}}{1+\frac{x}{1-x}}\right)^{-1} \\
&=\frac{1+x}{1-3x-3x^2}\\
&= \cdots+ 132543135x^{14}+\boldsymbol {502509177x^{15}}+1905156936x^{16}+  \cdots  \end{align*}$$ Vậy có $\color {blue}{502509177} $ xâu thỏa đề bài.

[chanhquocnghiem]

Có bao nhiêu xâu tứ phân kích thước 15 lập từ $\left \{ 0,1,2,3 \right \}$ không có 2 chữ số 0 liên tiếp.

Gọi $k$ là số chữ số $0$ có trong xâu đó.

Chọn $k$ vị trí (trong $15$ vị trí) sao cho không có 2 vị trí liên tiếp : $C_{16-k}^k$ cách.

(tham khảo ở đây https://diendantoanh...-số-liên-tiếp/)

Điền $1$, hoặc $2$, hoặc $3$ vào các vị trí còn lại : $3^{15-k}$ cách.

$\Rightarrow$ đáp án là $\sum_{k=0}^{8}C_{16-k}^k3^{15-k}=502509177$.