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

[Math04]

Với $n$ là số nguyên dương cho trước, tìm số các từ có độ dài $n$ trên một từ điển có 3 chữ cái ${a,b,c}$ sao cho chữ cái $a$ xuất hiện một số lẻ lần.

[perfectstrong]

Xét hàm sinh: \[F\left( x \right) = \frac{x}{{1 - {x^2}}}{\left( {\frac{1}{{1 - x}}} \right)^2}\]

Đáp án cần tìm là $[x^n]F(x)$. Hy vọng Nobodyv3 tiếp sức

[Nobodyv3]

Xét hàm sinh: \[F\left( x \right) = \frac{x}{{1 - {x^2}}}{\left( {\frac{1}{{1 - x}}} \right)^2}\]
Đáp án cần tìm là $[x^n]F(x)$. Hy vọng Nobodyv3 tiếp sức

Tiến hành tách phân thức :
$\begin {align*}
F(x)&=\frac{x}{1-x^2}\frac{1}{\left ( 1-x \right )^2}\\&=\frac{1}{2}\frac{1}{\left ( 1-x \right )^3}-\frac{1}{8}\frac{1}{1+x}-\frac{1}{8}\frac{1}{1-x}-\frac{1}{4}\frac{1}{\left ( 1-x \right )^2}
\end{align*}$
Do đó,
$\begin{align*}
\Longrightarrow\boldsymbol {[x^n]F(x)}&=\frac{1}{2}\binom{n+2}{2}-\frac{(-1)^n}{8}-\frac{1}{8}-\frac{1}{4}(n+1)\\&=\frac{n^2+n}{4}-\frac{(-1)^n+1}{8}
\end{align*} $
=========
Tuy nhiên,....
Em hiểu ý của anh, nhưng riêng bài này và từ ý tưởng của anh, em nghĩ tốt nhất là dùng hàm sinh mũ để giải :
Xét hàm sinh :
$f(x)=e^{2x}\cdot \frac{e^x-e^{-x}}{2}\\
f(x)=\frac{e^{3x}-e^x}{2}=\frac{1}{2}\sum_{n=0}^{\infty }\left ( 3^n-1 \right )\frac{x^n}{n!}$
Vậy số các từ thỏa đề bài là $\boxed {\frac{3^n-1}{2}}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 21-10-2022 - 12:39

[perfectstrong]

Tiến hành tách phân thức :
$\begin {align*}
F(x)&=\frac{x}{1-x^2}\frac{1}{\left ( 1-x \right )^2}\\&=\frac{1}{2}\frac{1}{\left ( 1-x \right )^3}-\frac{1}{8}\frac{1}{1+x}-\frac{1}{8}\frac{1}{1-x}-\frac{1}{4}\frac{1}{\left ( 1-x \right )^2}
\end{align*}$
Do đó,
$\begin{align*}
\Longrightarrow\boldsymbol {[x^n]F(x)}&=\frac{1}{2}\binom{n+2}{2}-\frac{(-1)^n}{8}-\frac{1}{8}-\frac{1}{4}(n+1)\\&=\frac{n^2+n}{4}-\frac{(-1)^n+1}{8}
\end{align*} $
=========
Tuy nhiên,....
Em hiểu ý của anh, nhưng riêng bài này và từ ý tưởng của anh, em nghĩ tốt nhất là dùng hàm sinh mũ để giải :
Xét hàm sinh :
$f(x)=e^{2x}\cdot \frac{e^x-e^{-x}}{2}\\
f(x)=\frac{e^{3x}-e^x}{2}=\frac{1}{2}\sum_{n=0}^{\infty }\left ( 3^n-1 \right )\frac{x^n}{n!}$
Vậy số các từ thỏa đề bài là $\boxed {\frac{3^n-1}{2}}$

Cảm ơn em đã xử lý nốt Tuy nhiên, kết quả lại không trùng nhau. Nhìn lại thì có vẻ hàm anh đưa ra chỉ mới xét tới số nghiệm nguyên của $2S(a)+S(b)+S(c)=n$ mà chưa tính tới sự hoán vị của các phần tử.

[Nobodyv3]

Cảm ơn em đã xử lý nốt Tuy nhiên, kết quả lại không trùng nhau. Nhìn lại thì có vẻ hàm anh đưa ra chỉ mới xét tới số nghiệm nguyên của $2S(a)+S(b)+S(c)=n$ mà chưa tính tới sự hoán vị của các phần tử.

Đúng vậy đó anh!
Đây cũng là lý do mà em không dùng hàm sinh thường (OGF) mà sử dụng hàm sinh mũ (EGF) để giải bài này.

[hxthanh]

Truy hồi thì ta có $2$ dãy (lẻ, chẵn) độ dài $n$, với:
$\begin{cases}l_n=2l_{n-1}+c_{n-1} \\ c_n=2c_{n-1}+l_{n-1}\end{cases}$
Suy ra:
$l_{n}=4l_{n-1}-3l_{n-2}$
với $l_1=1, l_2=4$