1/ Tính số các xâu nhị phân kích thước n có đúng m xâu con 01.
2/ Tính số các xâu tam phân kích thước n mà không có 2 chữ số 0 đứng kề nhau.
3/ Tính số các xâu tứ phân kích thước n có số các chữ số 0 là số chẵn.
Tính số các xâu nhị phân kích thước n có đúng m xâu con 01.
Started By Nobodyv3, 16-05-2023 - 21:54
#2
Posted 17-05-2023 - 12:33
3/ Từ hàm sinh :
$f(x)=\left ( \frac {e^x+e^{-x}}{2} \right )e^{3x}=\frac {1}{2}\left ( e^{4x}+e^{2x} \right )$
suy ra số các xâu thỏa yêu cầu là $\boldsymbol {\frac {1}{2}\left ( 4^{n}+2^{n} \right )}$
hoặc giải theo cách "truyền thống " bằng cách lập hệ thức truy hồi...
$f(x)=\left ( \frac {e^x+e^{-x}}{2} \right )e^{3x}=\frac {1}{2}\left ( e^{4x}+e^{2x} \right )$
suy ra số các xâu thỏa yêu cầu là $\boldsymbol {\frac {1}{2}\left ( 4^{n}+2^{n} \right )}$
hoặc giải theo cách "truyền thống " bằng cách lập hệ thức truy hồi...
Edited by Nobodyv3, 17-05-2023 - 21:20.
- chanhquocnghiem likes this
===========
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...
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...
#3
Posted 19-05-2023 - 10:41
1/ Với một xâu bất kỳ thỏa đề bài, ta thêm một bit 1 vào đầu xâu và một bit 0 vào cuối xâu thì ta có xâu mới kích thước n+2 và vẫn có đúng m xâu con 01. Gọi vị trí trong xâu mà ở đó, bit 0 chuyển qua bit 1 hoặc ngược lại, là "vị trí chuyển " thì lúc này, xâu có n+1 chỗ trống và 2m+1 "vị trí chuyển ". Do đó số các xâu thỏa yêu cầu là $\boldsymbol {\binom {n+1}{2m+1}}$
Hoặc là :
Gọi vị trí trong xâu mà ở đó, bit 0 chuyển qua bit 1 hoặc ngược lại là "vị trí chuyển " thì lúc này, xâu có n-1 chỗ trống và có các trường hợp sau :
- Xâu bắt đầu và kết thúc bằng bit 1: có 2m "vị trí chuyển " .
- Xâu bắt đầu bằng bit 1 và kết thúc bằng bit 0: có 2m+1 "vị trí chuyển " .
- Xâu bắt đầu và kết thúc bằng bit 0: có 2m "vị trí chuyển " .
- Xâu bắt đầu bằng bit 0 và kết thúc bằng bit 1: có 2m-1 "vị trí chuyển " .
Do đó số các xâu thỏa đề bài là :
$\begin {align*}
a_n&=\binom {n-1}{2m}+\binom {n-1}{2m+1}+\binom {n-1}{2m}+\binom {n-1}{2m-1}\\&=\binom {n}{2m+1}+\binom {n}{2m}\\&=\boldsymbol {\binom {n+1}{2m+1}}
\end{align*}$
Hoặc là :
Gọi vị trí trong xâu mà ở đó, bit 0 chuyển qua bit 1 hoặc ngược lại là "vị trí chuyển " thì lúc này, xâu có n-1 chỗ trống và có các trường hợp sau :
- Xâu bắt đầu và kết thúc bằng bit 1: có 2m "vị trí chuyển " .
- Xâu bắt đầu bằng bit 1 và kết thúc bằng bit 0: có 2m+1 "vị trí chuyển " .
- Xâu bắt đầu và kết thúc bằng bit 0: có 2m "vị trí chuyển " .
- Xâu bắt đầu bằng bit 0 và kết thúc bằng bit 1: có 2m-1 "vị trí chuyển " .
Do đó số các xâu thỏa đề bài là :
$\begin {align*}
a_n&=\binom {n-1}{2m}+\binom {n-1}{2m+1}+\binom {n-1}{2m}+\binom {n-1}{2m-1}\\&=\binom {n}{2m+1}+\binom {n}{2m}\\&=\boldsymbol {\binom {n+1}{2m+1}}
\end{align*}$
Edited by Nobodyv3, 20-05-2023 - 11:46.
- chanhquocnghiem likes this
===========
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...
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...
#4
Posted 20-05-2023 - 11:41
2/ Gọi $a_n$ là số các xâu thỏa yêu cầu và $x_n, y_n, z_n$ lần lượt là số các xâu kết thúc bằng 0,1,2 thỏa yêu cầu đề bài. Rõ ràng:
$\begin {align*}
x_{n+1}&=y_n+z_n\\
y_{n+1}&=x_n+y_n+z_n\\
z_{n+1}&=x_n+y_n+z_n
\end{align*}$
Cho nên :
$y_n=z_n,\;x_{n+1}=2y_n,\;y_{n+1}=x_n+2y_n$.
Từ : $y_{n+1}-2y_n-2y_{n-1}=0 \Rightarrow \alpha, \beta =1\pm \sqrt 3\Rightarrow y_n=A\left ( 1+ \sqrt 3 \right )^n+B\left ( 1- \sqrt 3 \right )^n$
Do $y_2=3,\;y_3=8$ nên:
$A=\frac {1+\sqrt3}{4\sqrt3},\;B=\frac {1-\sqrt3}{4\sqrt3}\Rightarrow y_n=\frac {1}{4\sqrt3}\left (\alpha ^{n+1}-\beta^{n+1} \right )$ do $ a_n = x_n + y_n + z_n = 2y_{n-1} + 2y_n $ ta có
$\begin{align*}
a_n &= \frac{1}{2\sqrt{3}}\left(\alpha^n(1+\alpha) - \beta^n(1+\beta)\right)\\
&= \left(\frac{2+\sqrt{3}}{2\sqrt{3}}\right)(1+\sqrt3)^n -\left(\frac{2-\sqrt{3}}{2\sqrt{3}}\right)(1-\sqrt3)^n\\
&=\boldsymbol {\frac {1}{6}\left ( \left ( 3+2\sqrt3 \right )\left ( 1+\sqrt 3 \right )^n+\left ( 3-2\sqrt3 \right )\left ( 1-\sqrt3 \right )^n \right )}
\end{align*}$
Edited.
$\begin {align*}
x_{n+1}&=y_n+z_n\\
y_{n+1}&=x_n+y_n+z_n\\
z_{n+1}&=x_n+y_n+z_n
\end{align*}$
Cho nên :
$y_n=z_n,\;x_{n+1}=2y_n,\;y_{n+1}=x_n+2y_n$.
Từ : $y_{n+1}-2y_n-2y_{n-1}=0 \Rightarrow \alpha, \beta =1\pm \sqrt 3\Rightarrow y_n=A\left ( 1+ \sqrt 3 \right )^n+B\left ( 1- \sqrt 3 \right )^n$
Do $y_2=3,\;y_3=8$ nên:
$A=\frac {1+\sqrt3}{4\sqrt3},\;B=\frac {1-\sqrt3}{4\sqrt3}\Rightarrow y_n=\frac {1}{4\sqrt3}\left (\alpha ^{n+1}-\beta^{n+1} \right )$ do $ a_n = x_n + y_n + z_n = 2y_{n-1} + 2y_n $ ta có
$\begin{align*}
a_n &= \frac{1}{2\sqrt{3}}\left(\alpha^n(1+\alpha) - \beta^n(1+\beta)\right)\\
&= \left(\frac{2+\sqrt{3}}{2\sqrt{3}}\right)(1+\sqrt3)^n -\left(\frac{2-\sqrt{3}}{2\sqrt{3}}\right)(1-\sqrt3)^n\\
&=\boldsymbol {\frac {1}{6}\left ( \left ( 3+2\sqrt3 \right )\left ( 1+\sqrt 3 \right )^n+\left ( 3-2\sqrt3 \right )\left ( 1-\sqrt3 \right )^n \right )}
\end{align*}$
Edited.
Edited by Nobodyv3, 20-05-2023 - 16:31.
- chanhquocnghiem likes this
===========
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...
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...
#5
Posted 20-05-2023 - 16:18
$a_n=\frac{1}{6}\left [ \left ( 3+2\sqrt{3} \right )\left ( 1+\sqrt{3} \right )^n+\left ( 3-2\sqrt{3} \right )\left ( 1-\sqrt{3} \right )^n \right ]$
- Nobodyv3 likes this
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users