Nobodyv3

Ta cần tìm số nghiệm nguyên không âm của hệ phương trình :
$\left\{\begin{matrix}
5z_1+10z_2+25z_3+z_4&=\;200 \\
z_1+z_2+z_3+z_4&=\;50 &
\end{matrix}\right.$

Giả sử anh A có một số tờ tiền với các mệnh giá 1,5,10 và 25 đồng. Hỏi anh A có bao nhiêu cách trả tiền món hàng giá 200 đồng với đúng 50 tờ tiền.

Số cặp học sinh có chung một câu trả lời : $C_{8}^{2}=28$
Số cách trả lời các câu hỏi của 8 học sinh:
$\underbrace{ 28\cdot27\cdots\cdot(28-4n+1) }_{4n \text{ thừa số }}=A_{28}^{4n}$
Từ đó ta có :
$4n\leq 28\Rightarrow n\leq 7$

Xét đa thức $G(x)=(1+x)^{2007}$. Gọi $\omega=e ^{2\pi i/3}$ là 1 nghiệm của phương trình $x^3=1$ thì theo định lý RUF ta có :
$$\begin {align*}
S &=\frac {2^{2007}+(1+\omega )^{2007} +(1+\omega ^2)^{2007} }{3}\\
&=\frac {2^{2007}-2}{3}
\end {align*}$$Ta thấy $1000=2^3\times 5^3$ mà $2^{2007} \equiv 0\!\! \pmod{2^3}$ và $2^{2007} \equiv 2^7\equiv 3\!\! \pmod{5^3}$. Suy ra :
$2^{2007}\equiv 128\!\!\pmod {1000}$ nên :
$2^{2007}-2\equiv 126\!\!\pmod {1000}$
Nhận thấy $gcd(3,1000)=1$ nên $3^{-1}\equiv 667\!\!\pmod {1000}$
Do đó :
$$\begin {align*}
S=\frac {2^{2007}-2}{3}&\equiv 667\times (2^{2007}-2)\\
&\equiv 667\times126\\
&\equiv 042\!\!\pmod {1000}
\end {align*}$$Vậy số dư là $ \boldsymbol {042}$

Cho
$$S={2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}$$
Hãy tính $S\!\!\!\! \!\pmod{\!\!1000}$
========
OP tại :
https://artofproblem...c20073c20072007

Tính số nghiệm nguyên không âm của phương trình
$$2x_1+3x_2+3x_3=n$$trong đó $n\equiv 1\!\! \pmod{6}$

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*}$$

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*}$$

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

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

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 Hic, xem ra em cần rất nhiều thời gian mới tiêu hóa hết...!

Đầ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 )}$ .

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

Em thử tăng lên một biến $(z_6)$ xem. Kết quả sau khi xét theo modulo 6 có thể rút gọn về một đẳng thức rất đẹp đó!

Thưa Thầy, vâng ạ.
Lúc này phương trình sẽ là:
$$z_2+z_3+z_4+z_5+z_6=n$$
Tương tự, ta có hàm sinh:$$F(x)=\frac { x^5}{(1-x)^5(1+x+x^2+x^3+x^4+x^5)}$$
Tiến hành tách phân thức và rút gọn ta có:$$\begin {align*}
F(x)&=\frac{1}{6\left ( 1-x \right )^5}-\frac{5}{12\left ( 1-x \right )^4}-\frac{5}{72\left ( 1-x \right )^3}+\frac{5}{16\left ( 1-x \right )^2}\\
&\quad -\frac{1}{96\left ( 1+x \right )}+\frac{151}{864\left ( 1-x \right )}+\frac{1}{27\left ( 1+x+x^2 \right )}\\
&\quad -\frac{1}{3\left ( 1-x +x^2\right )}+\frac{x}{54\left ( 1+x+x^2 \right )}+\frac{x}{6\left ( 1-x+x^2 \right )}
\end{align*}$$Do đó số nghiệm là :$$\left [ x^n \right ]F(x)= \left \{ \begin{matrix} &
\frac {1}{6}\binom{n+4}{4}-\frac {5}{12}\binom{n+3}{3}+\frac {5}{72}\binom{n+2}{2}+ \frac {5}{16}(n+1)+\frac {151}{864}-\frac {(-1)^n}{96}+\frac {1}{27}-\frac{(-1)^n}{3} &&\text{nếu $n \equiv 0\!\! \pmod{3}$ }\\
& \frac {1}{6}\binom{n+4}{4}-\frac {5}{12}\binom{n+3}{3}+\frac {5}{72}\binom{n+2}{2}+ \frac {5}{16}(n+1)+\frac {151}{864}-\frac {(-1)^n}{96}-\frac{1}{27}-\frac{(-1)^{(n-1)/3}}{3}+\frac{1}{54}+\frac {(-1)^{(n-1)/3}}{6}  &&\text{nếu $n \equiv 1\!\! \pmod{3}$ } \\
&\frac {1}{6}\binom{n+4}{4}-\frac {5}{12}\binom{n+3}{3}+\frac {5}{72}\binom{n+2}{2}+ \frac {5}{16}(n+1)+\frac {151}{864}-\frac {(-1)^n}{96}-\frac{1}{54}+\frac {(-1)^{(n-2)/3}}{6} &&\text{nếu $n \equiv 2\!\! \pmod{3}$ }
\end{matrix}\right.$$
Hic, em không rút gọn hơn được nữa!

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.