Đến nội dung

Hình ảnh

Tính số các xâu nhị phân kích thước n có đúng m xâu con 01.

- - - - -

  • Please log in to reply
Chủ đề này có 4 trả lời

#1
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
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.
===========
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
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
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...

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

===========
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
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
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*}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 20-05-2023 - 11:46

===========
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
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
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.

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 20-05-2023 - 16:31

===========
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
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2494 Bài viết

$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 ]$


...

Ðê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 ...

 

http://www.wolframal...-15)(x^2-8x+12)





2 người đang xem chủ đề

0 thành viên, 2 khách, 0 thành viên ẩn danh