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

[Nobodyv3]

Có bao nhiêu xâu kích thước 20 lập từ $\left \{ a,b \right \}$ có chứa xâu con $aaa$ và $bbbb$.

[Nobodyv3]

Gọi :
$a_n$ là số các xâu kích thước n không chứa $aaa$,
$b_n$ là số các xâu kích thước n không chứa $bbbb$ ,
$c_n$ là số các xâu kích thước n không chứa $aaa$ và $bbbb$.
Theo nguyên lý bù trừ, số xâu cần tính là :
$$d_n=2^n-a_n-b_n+c_n,\quad n\geq 0\qquad (1)$$Hàm sinh cho các Smirnov words trên tập $\left \{ a,b \right \}$ là $$\left ( 1-\frac{2x}{1+x} \right )^{-1}=1+2x+2x^2+2x^3+...\qquad (2)$$

( Còn tiếp)

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

[Nobodyv3]

Giải :
Gọi :
$a_n$ là số các xâu kích thước n không chứa $aaa$,
$b_n$ là số các xâu kích thước n không chứa $bbbb$ ,
$c_n$ là số các xâu kích thước n không chứa $aaa$ và $bbbb$.
Theo nguyên lý bù trừ, số xâu cần tính là :
$d_n=2^n-a_n-b_n+c_n, n\geq 0\qquad(1) $
Hàm sinh cho các Smirnov words trên tập $\left \{ a,b \right \}$ là $\left ( 1-\frac{2x}{1+x} \right )^{-1}=1+2x+2x^2+2x^3+...\qquad (2)$
- Xâu con $aaa$:
Thiết lập hàm sinh $A(x)=\sum_{n=0}^\infty a_nx^n$ như sau : ta tìm các xâu không chứa $aaa$, từ Smirnov words ta thay mỗi $a$ bằng $a$ hoặc $aa$ còn mỗi $b$ có thể thay với số lượng không ràng buộc:
$$\begin{align*} &a:\quad x\quad\to\quad x+x^2\\ &b:\quad x\quad\to\quad x+x^2+x^3+\cdots = \frac{x}{1-x} \end{align*}$$Thay vào (2):$$\begin{align*} A(x)&=\left(1-\frac{x+x^2}{1+x+x^2}-\frac{\frac{x}{1-x}}{1+\frac{x}{1-x}}\right)^{-1} \\
&=\frac{1-x^3}{1-2x+x^4} \end{align*}$$- Xâu con $bbbb$:
Thiết lập hàm sinh $B(x)=\sum_{n=0}^\infty b_nx^n$ như sau :ta tìm các xâu không chứa $bbbb$, từ Smirnov words ta thay mỗi $b$ bằng $b$ hoặc $bb$ hoặc $bbb$ còn mỗi $a$ có thể thay với số lượng không ràng buộc :$$\begin{align*} &a:\quad x\quad\to\quad x+x^2+x^3+\cdots = \frac{x}{1-x}\\ &b:\quad x\quad\to\quad x+x^2+x^3 \end{align*}$$Thay vào (2):
$$\begin{align*} B(x)&=\left(1-\frac{\frac{x}{1-x}}{1+\frac{x}{1-x}}-\frac{x+x^2+x^3}{1+x+x^2+x^3}\right)^{-1}\\
& =\frac{1-x^4}{1-2x+x^5}\end{align*}$$- Xâu con $aaa,bbbb$:
Thiết lập hàm sinh $C(x)=\sum_{n=0}^\infty c_nx^n$ như sau : ta tìm các xâu không chứa $aaa$ và $bbbb$, từ Smirnov words ta thay mỗi $a$ bằng $a$ hoặc $aa$ và mỗi $b$ bằng $b$ hoặc $bb$ hoặc $bbb$:
$$\begin{align*} &a:\quad x\quad\to\quad x+x^2\\ &b:\quad x\quad\to\quad x+x^2+x^3 \end{align*}$$Thay vào (2):$$\begin{align*} C(x)&=\left(1-\frac{x+x^2}{1+x+x^2}-\frac{x+x^2+x^3}{1+x+x^2+x^3}\right)^{-1}\\ &=\frac{1+2x+3x^2+3x^3+2x^4+x^5}{1-x^2-2x^3-2x^4-x^5} \end{align*}$$Và hàm sinh cho $2^n$ là $$\begin{align*} \frac{1}{1-2x}=1+2x+4x^2+8x^3+\cdots \end{align*}$$
Cuối cùng, theo (1) ta có hàm sinh $D(x)$:
$$\begin{align*}D(x)&=\frac{1}{1-2x}-A(x)-B(x)+C(x)\\
&=\frac{1}{1-2x}-\frac{1-x^3}{1-2x+x^4}-\frac{1-x^4}{1-2x+x^5}\\
&+\frac{1+2x+3x^2+3x^3+2x^4+x^5}{1-x^2-2x^3-2x^4-x^5}\\ &=\cdots +34261x^{17}+75713x^{18}+165571x^{19}\\
&+\boldsymbol {358847x^{20}}+771762x^{21}+1648716x^{22} +\cdots \end{align*}$$Vậy có $\color {blue }{ 358847}$ xâu thỏa đề bài.
N.B.: Smirnov words là các từ không có chữ cái giống nhau đứng liên tiếp.

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