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

[Nobodyv3]

Có bao nhiêu xâu nhị phân có đúng 10 bit 1 sao cho không có 3 bit 0 liên tiếp hoặc 4 bit 1 liên tiếp.

[Nobodyv3]

Ta sẽ xây dựng hàm sinh nhờ vào một ít kiến thức (không cần nhiều) về ngôn ngữ hình thức. Ở bài này,  phần ngôn ngữ lặp lại là $ (
\left \{ 0,00 \right \} \left \{1,11,111 \right \})^*$  tức là sau 1 hoặc 2 bit 0 có thể là 1 hoặc 2 hoặc 3 bit 1 và cứ lặp lại như thế. Tuy nhiên, đó chỉ là các xâu bắt đầu bằng bit 0 và kết thúc bằng bit 1. Do đó, để biểu diễn đầy đủ các xâu thỏa yêu cầu thì đầu xâu ta thêm $\left \{ \epsilon,1,11,111 \right \}$ và cuối xâu thêm $ \left \{\epsilon, 0,00 \right \} $ cụ thể là :
$$\left \{ \epsilon,1,11,111 \right \}(
\left \{ 0,00 \right \} \left \{1,11,111 \right \})^*\left \{\epsilon, 0,00 \right \}$$
Nhờ đó, ta xây dựng được hàm sinh :
$$\begin {align*}
G(x)&=\left ( 1+x+x^2+x^3 \right )\frac{1}{1-\left (1+1 \right )\left (x+x^2+x^3  \right )}\left ( 1+1+1 \right )\\
&=\frac{3\left ( 1+x+x^2+x^3 \right )}{1-2x-2x^2-2x^3}
\end{align*}$$
Và tính được số các xâu thỏa yêu cầu là :
$\left [ x^{10} \right ]G(x)=\boldsymbol {145152}$

[hxthanh]

Đầu xâu và cuối xâu thì dễ hiểu rồi ($\epsilon$ chắc là empty) còn phần hàm sinh cho cấu trúc lặp đấy hơi… trừu tượng (với mình). Thật bất ngờ vì độ “mạnh mẽ” của hàm sinh đối với bài toán này. Nếu được mong tác giả giải thích thêm.

[Nobodyv3]

Đầu xâu và cuối xâu thì dễ hiểu rồi ($\epsilon$ chắc là empty) còn phần hàm sinh cho cấu trúc lặp đấy hơi… trừu tượng (với mình). Thật bất ngờ vì độ “mạnh mẽ” của hàm sinh đối với bài toán này. Nếu được mong tác giả giải thích thêm.

Em xin trình bày những gì em hiểu :
Ta thường sử dụng chuỗi vô hạn $\frac {1}{1-X}$ làm hàm sinh để đếm số cách "cái gì đó" lặp đi lặp lại. Xét thí dụ :
Có bao nhiêu cách dán lên phong bì 50 xu tem bằng các loại tem mệnh giá 1 xu, 2 xu, 5 xu, biết rằng thứ tự dán tem là quan trọng.
Lập hàm sinh : vì các loại tem này được dán lặp đi lặp lại nên ta xem $X$ là $x+x^2+x^5$ suy ra hàm sinh là $\frac {1}{1-(x+x^2+x^5)}$.
Trở lại bài toán, suy luận tương tự, cụm lặp đi lặp lại $(
\left \{ 0,00 \right \} \left \{1,11,111 \right \})$ được mã hóa là $2\left (x+x^2+x^3  \right )$ và thay vào $X$ nên ta có hàm sinh cho riêng cụm lặp đi lặp lại này là $\frac {1}{1- 2\left (x+x^2+x^3  \right )}$ .

[hxthanh]

Em xin trình bày những gì em hiểu :
Ta thường sử dụng chuỗi vô hạn $\frac {1}{1-X}$ làm hàm sinh để đếm số cách "cái gì đó" lặp đi lặp lại. Xét thí dụ :
Có bao nhiêu cách dán lên phong bì 50 xu tem bằng các loại tem mệnh giá 1 xu, 2 xu, 5 xu, biết rằng thứ tự dán tem là quan trọng.
Lập hàm sinh : vì các loại tem này được dán lặp đi lặp lại nên ta xem $X$ là $x+x^2+x^5$ suy ra hàm sinh là $\frac {1}{1-(x+x^2+x^5)}$.
Trở lại bài toán, suy luận tương tự, cụm lặp đi lặp lại $(
\left \{ 0,00 \right \} \left \{1,11,111 \right \})$ được mã hóa là $2\left (x+x^2+x^3  \right )$ và thay vào $X$ nên ta có hàm sinh cho riêng cụm lặp đi lặp lại này là $\frac {1}{1- 2\left (x+x^2+x^3  \right )}$ .

Làm cách nào xử lý hàm sinh này?

[Nobodyv3]

Làm cách nào xử lý hàm sinh này?

Như vậy, từ hàm sinh $h(x)=\frac {1}{1- 2\left (x+x^2+x^3  \right )}$ và với sự trợ giúp của WA, ta tính được số xâu nhị phân (bắt đầu là bit 0 và cuối xâu là bit 1) có đúng 10 bit 1 mà không có 3 bit 0 liên tiếp hoặc 4 bit 1 liên tiếp :
$[x^{10}]h(x)=\boldsymbol {32256}$
WA query :
https://www.wolframa...1-2(x+x^2+x^3))

[hxthanh]

Như vậy, từ hàm sinh $h(x)=\frac {1}{1- 2\left (x+x^2+x^3  \right )}$ và với sự trợ giúp của WA, ta tính được số xâu nhị phân (bắt đầu là bit 0 và cuối xâu là bit 1) có đúng 10 bit 1 mà không có 3 bit 0 liên tiếp hoặc 4 bit 1 liên tiếp :
$[x^{10}]h(x)=\boldsymbol {32256}$
WA query :
https://www.wolframa...1-2(x+x^2+x^3))

No, no! Không xài máy tính nhé!

[Nobodyv3]

No, no! Không xài máy tính nhé!

Vậy thì... Em xin ngồi ngóng... Hic.

[hxthanh]

Vậy thì... Em xin ngồi ngóng... Hic.

Tưởng em xử lý được chứ! Thế này thì bó tay, tuy vậy thì cũng tìm thấy cái để tham khảo ở đây

[hovutenha]

theo em hiểu thì hàm sinh:

$$\frac{1}{1-x}=\sum_{k=0}^{\infty }x^{k}$$

Như vậy thì áp dụng vào hàm sinh: $\frac{1}{1-2(x+x^2+x^3)}$

ta có được:

$$\frac{1}{1-2(x+x^2+x^3)}=\sum_{k=0}^{\infty }(2(x+x^2+x^3))^{k}$$

đây là biểu thức hoàn toàn có thể tìm được hệ số của $x^{10}$. Kết quả cũng ra $\textbf{32256}$

 

Vậy khi áp vào hàm sinh :

$$\frac{3(1+x+x^2+x^3)}{1-2(x+x^2+x^3)}=3(1+x+x^2+x^3)\sum_{k=0}^{\infty }(2(x+x^2+x^3))^{k}$$

Ta tìm được kết quả là $\textbf{145152}$

Bài viết đã được chỉnh sửa nội dung bởi hovutenha: 02-02-2024 - 21:57

[Nobodyv3]

Tưởng em xử lý được chứ! Thế này thì bó tay, tuy vậy thì cũng tìm thấy cái để tham khảo ở đây

Bằng casework, tuy cồng kềnh nhưng vẫn tính tay được :
$$\begin {align*}
[x^{10}]\frac{1}{1-2(x+x^2+x^3)}&=[x^{10}]\sum_{k=4}^{10 }2^k(x+x^2+x^3)^k\\
&=160+ 1632+5760+9856\\
&\quad +9216+4608+1024\\
&=32256
\end {align*}$$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 02-02-2024 - 22:43

[hxthanh]

Bằng casework, tuy cồng kềnh nhưng vẫn tính tay được :
$$\begin {align*}
[x^{10}]\frac{1}{1-2(x+x^2+x^3)}&=[x^{10}]\sum_{k=4}^{10 }(2^k(x+x^2+x^3)^k\\
&=160+ 1632+5760+9856\\
&\quad +9216+4608+1024\\
&=32256
\end {align*}$$

Dẫu sao thì [x^n] vẫn là một ẩn số

[Konstante]

Không biết làm như thế này có được không (thực ra cũng chỉ là biến đổi lòng vòng): gọi $a,b,c$ là $3$ nghiệm của phương trình $1-2(x+x^2+x^3)=0$, thế thì $$(a-x)(b-x)(c-x) = 1-2(x+x^2+x^3)$$Sử dụng định lý tách phân số cho đa thức $$\frac{1}{(a-x)(b-x)(c-x)} = \frac{A}{(a-x)} + \frac{B}{(b-x)} + \frac{C}{(c-x)}$$ trong đó $A = \frac{1}{(b-a)(c-a)}, \, B =  \frac{1}{(a-b)(c-b)}, \, C =  \frac{1}{(a-c)(b-c)}$. Mặt khác hệ số của $x^{10}$ trong tổng hình thức $\frac{1}{1-\alpha x}$ là $\alpha^{10}$ nên $$[x^{10}]\frac{1}{(a-x)(b-x)(c-x)} = \frac{a^9}{(b-a)(c-a)} + \frac{b^9}{(a-b)(c-b)} + \frac{c^9}{(a-c)(b-c)}$$Vế phải là biểu thức đối xứng của các nghiệm nên có thể tính tường minh bằng công thức Viete.

[hxthanh]

Không biết làm như thế này có được không (thực ra cũng chỉ là biến đổi lòng vòng): gọi $a,b,c$ là $3$ nghiệm của phương trình $1-2(x+x^2+x^3)=0$, thế thì $$(a-x)(b-x)(c-x) = 1-2(x+x^2+x^3)$$Sử dụng định lý tách phân số cho đa thức $$\frac{1}{(a-x)(b-x)(c-x)} = \frac{A}{(a-x)} + \frac{B}{(b-x)} + \frac{C}{(c-x)}$$ trong đó $A = \frac{1}{(b-a)(c-a)}, \, B =  \frac{1}{(a-b)(c-b)}, \, C =  \frac{1}{(a-c)(b-c)}$. Mặt khác hệ số của $x^{10}$ trong tổng hình thức $\frac{1}{1-\alpha x}$ là $\alpha^{10}$ nên $$[x^{10}]\frac{1}{(a-x)(b-x)(c-x)} = \frac{a^9}{(b-a)(c-a)} + \frac{b^9}{(a-b)(c-b)} + \frac{c^9}{(a-c)(b-c)}$$Vế phải là biểu thức đối xứng của các nghiệm nên có thể tính tường minh bằng công thức Viete.

Trên thực tế thì đúng là có thể làm như vậy, tuy nhiên để đưa Viète vào được thì công thức rất cồng kềnh và có vẻ như không khả thi với $n$ tổng quát.
Đôi khi ta cũng gặp những bài toán dù biết được cách giải nhưng lại không thể đưa ra một công thức đóng.
Việc bắt buộc phải đưa ra một thuật toán để tính hệ số của $[x^{2024}]$ chẳng hạn, thì có lẽ hệ thức truy hồi có lẽ là khả thi nhất!
Chẳng hạn như:
$\begin{cases}u_0=1;\;\; u_1=2;\;\; u_2=6;\\ u_n=2(u_{n-1}+u_{n-2}+u_{n-3});\;\; (n\ge 3)\end{cases}$

[Nobodyv3]

Dẫu sao thì [x^n] vẫn là một ẩn số

Trong lúc chưa tìm được công thức dạng closed form thì ta xài tạm công thức dạng "ugly form" này vậy (Hic, cơm nguội đỡ lòng!). Ta có :
$$\begin {align*}
h(x)&=\frac {1}{1- 2\left (x+x^2+x^3 \right )}\\
&=\frac{1-x}{1-x-2x(1-x^3)}=\frac{1-x}{1-3x+2x^4}\\
&=(1-x)\sum_{i=0}^{\infty }x^i(3-2x^3)^i=(1-x)\sum_{i=0}^{\infty }x^i\sum_{j=0}^{i}\binom{i}{j}(-1)^j2^jx^{3j}3^{i-j}\\
\Longrightarrow &[x^n]\sum_{i=0}^{\infty }x^i\sum_{j=0}^{i}\binom{i}{j}(-1)^j2^jx^{3j}3^{i-j}\\
&=\sum_{i=0}^{n}[x^{n-i}]\sum_{j=0}^{i}\binom{i}{j}(-1)^j2^jx^{3j}3^{i-j}\\
&=\sum_{i=0}^{n} [x^i]\sum_{j=0}^{n-i}\binom{n-i}{j}(-1)^j2^jx^{3j}3^{n-i-j}\\
&=\sum_{i=0}^{\left \lfloor n/3 \right \rfloor }x^{3i}\sum_{j=0}^{n-3i}\binom{n-3i}{j}(-1)^j2^jx^{3j}3^{n-3i-j}\\
&=\sum_{i=0}^{\left \lfloor n/3 \right \rfloor }\binom{n-3i}{i}(-1)^i2^i3^{n-4i}\\
\Longrightarrow
\boldsymbol { [x^n]h(x)} &
\boldsymbol { =\sum_{i=0}^{\left \lfloor n/3 \right \rfloor}\left [ \binom{n-3i}{i} -\frac{1}{3}\binom{n-3i-1}{i}\right ](-1)^i2^i3^{n-4i}}
\end {align*}$$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 04-02-2024 - 07:00