Cho dãy $a_{1},a_{2},a_{3},...,a_{n}$ sao cho $a_{i} \in \left \{ 0,1,2 \right \}$ và $\left | a_{i}-a_{i+1} \right |\leq 1, \forall i$. Tìm số các dãy $a_{1},a_{2},a_{3},...,a_{n}$ thỏa điều kiện đã cho.
Tìm số các dãy $a_{1},a_{2},a_{3},...,a_{n}$ thỏa điều kiện đã cho $a_{i} \in \left \{ 0,1,2 \right \}$ và $\left | a_{i}-a_{i+1} \right |\leq 1$
#2
Đã gửi 20-10-2022 - 22:48
Thử dùng truy hồi xem sao
Gọi $S(n,k)$ là số dãy số có độ dài $n$ thỏa đề và tận cùng là $k$, tức $a_n = k \in \{ 0, 1, 2\}$. Ta cần tìm số dãy số thỏa đề $T(n) = S(n,0)+S(n,1)+S(n,2)$.
Mà từ điều kiện $|a_i - a_{i+1}| \le 1$ thì có thể thấy :
- Nếu $a_{n}=0$ thì $a_{n-1}\in{0,1}$, nên $S(n,0) = S(n-1,0) + S(n-1,1)$.
- Nếu $a_{n}=2$ thì $a_{n-1} \in {1,2}$, nên $S(n,2) = S(n-1,1) + S(n-1,2)$.
- Nếu $a_{n}=1$ thì $a_{n-1} \in {0, 1,2}$, nên $S(n,1) = S(n-1,0) + S(n-1,1) + S(n-1,2)=T(n-1)$.
Vậy $$\begin{align*} T(n) & = S(n,0)+S(n,1)+S(n,2) \\ & = S(n-1,0)+2S(n-1,1)+S(n-1,2)+T(n-1) \\ & =2T(n-1)+T(n-2) \end{align*}$$
Lại có $T(1)=3$ và $T(2)=7$, ta tìm ra CTTQ \[T\left( n \right) = \frac{{{{\left( {1 + \sqrt 2 } \right)}^{n + 1}} + {{\left( {1 - \sqrt 2 } \right)}^{n + 1}}}}{2}\]
Hoặc đơn giản hơn tí thì:
\[T\left( n \right) = \left\lfloor {\frac{{{{\left( {1 + \sqrt 2 } \right)}^{n + 1}} + 1}}{2}} \right\rfloor \]
- hxthanh, Hoang72, Nobodyv3 và 2 người khác yêu thích
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#3
Đã gửi 28-03-2023 - 10:23
Bài này có đáp án bằng hàm sinh là:Cho dãy $a_{1},a_{2},a_{3},...,a_{n}$ sao cho $a_{i} \in \left \{ 0,1,2 \right \}$ và $\left | a_{i}-a_{i+1} \right |\leq 1, \forall i$. Tìm số các dãy $a_{1},a_{2},a_{3},...,a_{n}$ thỏa điều kiện đã cho.
$$[x^{n}]:\quad \dfrac{1+x}{1-2x-x^2}$$
Nhưng quả thực mình đọc không hiểu họ xây dựng sao ra như vậy!?
@Nobodyv3 hay ai đó có thể giải thích giúp mình được không?
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 28-03-2023 - 21:45
- perfectstrong và Nobodyv3 thích
#4
Đã gửi 28-03-2023 - 17:36
Em xin phép viết lại hệ thức truy hồi của anh @perfectstrong là :
$\begin {cases}
T_n=2T_{n-1}+T_{n-2}\\
T_0=1,\quad T_1=3
\end {cases}$
Đặt $G(x)=\sum_{n=0}^{\infty }T_nx^n$. Nhân $x^n$ cả 2 vế:
$T_nx^n=2T_{(n-1)}x^n+T_{(n-2)}x^n$
Cho $n$ chạy từ $2$ đến $\infty $ rồi cộng vế với vế:
$\sum_{n=2}^{\infty }T_nx^n=\sum_{n=2}^{\infty }2T_{(n-1)}x^n+\sum_{n=2}^{\infty }T_{(n-2)}x^n$
Suy ra :
$\begin {align*}
&\Rightarrow \sum_{n=0}^{\infty }T_nx^n-T_0-T_1x=\sum_{n=2}^{\infty }T_{(n-1)}2x.x^{n-1}+\sum_{n=2}^{\infty }T_{(n-2)}x^2.x^{n-2}\\
&\Rightarrow
G(x)-1-3x=2x(G(x)-T_0)+x^2G(x)\\
&\Rightarrow G(x)(1-2x-x^2)=1+x\\
&\Rightarrow \boldsymbol {G(x)=\frac {1+x}{1-2x-x^2}}
\end{align*}$
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 28-03-2023 - 17:41
- perfectstrong và hxthanh thích
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...
#6
Đã gửi 28-03-2023 - 23:01
Ta đã biết :
$\frac{1}{1-\alpha x}=1+\alpha x+\alpha^2x^2+...$ $(1)$
$\frac{1}{1-\beta x}=1+\beta x+\beta^2x^2+...$ $(2)$
Nhân $(1)\times A, (2)\times B$ rồi cộng vế với vế, ta có :
Vế trái :
$$\frac {A}{1-\alpha x}+\frac {B}{1-\beta x}=\frac {A+B+(-A\beta-B\alpha)x}{1-(\alpha+\beta) x+\alpha \beta x^2}$$
Vế phải :
$$(A+B)+(A\alpha+B\beta)x+(A\alpha^2+B \beta^2)x^2+...$$
$\Rightarrow \begin{cases}
1+x=A+B+(-A\beta-B\alpha)x\\
1-2x-x^2=1-(\alpha +\beta )x+\alpha \beta x^2
\end{cases}$ $(3)$
Ta được :
\begin {align*}
G(x)=\frac {1+x}{1-2x-x^2}&=\frac {A+B+(-A\beta-B\alpha)x}{1-(\alpha +\beta )x+\alpha \beta x^2}\\&=\frac {A}{1-\alpha x}+\frac {B}{1-\beta x}\\&=(A+B)+(A\alpha+B\beta)x+(A\alpha^2+B\beta^2)x^2+...
\end {align*}
Suy ra : $T_n=A\alpha^n+B\beta^n$
Giải $(3)$:Từ:
$\begin{cases}
A+B=1\\
-A\beta-B\alpha=1\\
\alpha +\beta =2\\
\alpha \beta =-1
\end{cases}
\Rightarrow
\begin{cases}
\alpha=1+\sqrt 2\\
\beta=1-\sqrt 2 \\
A =\frac {1+\sqrt 2}{2}\\
B =\frac {1-\sqrt 2}{2}
\end{cases}$ hoặc :
$\begin{cases}
\alpha=1-\sqrt 2\\
\beta=1+\sqrt 2 \\
A =\frac {1-\sqrt 2}{2}\\
B =\frac {1+\sqrt 2}{2}
\end{cases}$
Ta thấy $\alpha, \beta $ đối xứng, $A, B$ cũng vậy, nên đặt $\alpha=1+\sqrt 2, \beta=1-\sqrt 2, A =\frac {1+\sqrt 2}{2}, B =\frac {1-\sqrt 2}{2}$.
Lúc này khai triển của $G(x)$ có dạng :
$\begin {align*}
G(x)=\frac {1+x}{1-2x-x^2}&=(A+B)+(A\alpha+B\beta)x+(A\alpha^2+B\beta^2)x^2+...\\
&=1+\left( \frac {(1+\sqrt 2)^2}{2}+ \frac {(1-\sqrt 2)^2}{2} \right) x+\left( \frac {(1+\sqrt 2)}{2}(1+\sqrt 2)^2+ \frac {(1-\sqrt 2)}{2}(1-\sqrt 2)^2 \right) x^2+...
\end{align*}$
Do đó :
$$\boldsymbol {T_n=\frac {(1+\sqrt 2)^{n+1}+(1-\sqrt 2)^{n+1}}{2}}$$
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 29-03-2023 - 00:05
Lỗi $\LaTeX$ thôi mà align lồng trong cases!
- perfectstrong và hxthanh thích
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh