[51nod 1947] 栈的代价和

51nod 1947

设$f_{n}$为长度为$n$的出栈序列方案数,有
$$f_{n} = \sum\limits_{i=1}^nf_{i-1}\cdot f_{n-i}$$
设$g_n$为所有方案所有进栈时刻栈内元素数量之和,有
$$g_n = \sum \limits_{i=1}^n(g_{i-1}+if_{i-1})\cdot f_{n-i} + f_{i-1}\cdot g_{n-i}$$
设$h_n$为题目所求答案,有
$$h_n = \sum \limits_{i=1}^n(h_{i-1}+g_{i-1}+if_{i-1})\cdot f_{n-i} + f_{i-1}\cdot(h_{n-i}+ig_{n-i})$$

将上式生成函数可以得到

$$\begin{split}
F(x) &= \sum \limits_{i}f_ix^i\\
A(x) &= (xF(x))’ = \sum \limits_{i}(i+1)f_ix^i\\
G(x) &= \sum \limits_{i}g_ix^i\\
H(x) &= \sum \limits_{i}h_ix^i\\
\end{split}$$

$$\begin{split}
F &= x\cdot F^2+1\\
G &= x((G+A)F+FG)\\
H &= x((H+G+A)F+FH+GA)
\end{split}$$

解方程可得
$$\begin{split}
F(x) &= \frac{1-u^{\frac{1}{2}}}{2x}(u = 1 – 4x)\\
A(x) &= -\frac{u^{-\frac{1}{2}}}{4}\\
G(x) &= \frac{u^{-1}-u^{-\frac{1}{2}}}{2}\\
H(x) &= \frac{u^{-\frac{3}{2}} – u^{-\frac{1}{2}}}{4} + \frac{(u^{-2} – u^{-\frac{3}{2}})x}{2}\\
\end{split}$$

$$\begin{split}[x^n]u^{-\frac{3}{2}}
&= (-4)^n\cdot \frac{(-\frac{3}{2})^{\underline n}}{n!}\\
&= 2^n\cdot \frac{3\cdot 5\cdot \dots \cdot (2n+1)}{n!}\\
&= \frac{(2n+1)!}{n!\cdot n!}\\
&={2n\choose n}\cdot (2n+1)
\end{split}$$

$$\begin{split}[x^n]u^{-\frac{1}{2}}
&= (-4)^n \cdot \frac{(-\frac{1}{2})^{\underline n}}{n!}\\
&= 2^n\cdot \frac{1\cdot 3\cdot \dots \cdot (2n-1)}{n!}\\
&= \frac{(2n)!}{n!\cdot n!}\\
&= {2n\choose n}
\end{split}$$

$$\begin{split}[x^n]u^{-2}
&= (-4)^n\cdot \frac{(-2)^{\underline n}}{n!}\\
&= 4^n\cdot \frac{(n+1)!}{n!}\\
&= 4^n\cdot (n+1)
\end{split}$$

$$\begin{split}[x^n]H(x)
&= \frac{[x^n]u^{-\frac{3}{2}} – [x^n]u^{-\frac{1}{2}}}{4} + \frac{[x^{n-1}]u^{-2} – [x^{n-1}]u^{-\frac{3}{2}}}{2}\\
&= \frac{{2n\choose n}\cdot (2n+1) – {2n\choose n}}{4}+\frac{4^{n-1}\cdot n – {2n-2\choose n-1}\cdot (2n-1)}{2}\\
&= \frac{{2n\choose n}\cdot 2n – 2\cdot{2n-2\choose n-1}\cdot (2n-1)}{4} + \frac{ 4^{n-1}\cdot n}{2}\\
&= \frac{2n{2n-1\choose n} + 2n{2n-1\choose n-1}-2n\cdot{2n-1\choose n}}{4} + \frac{ 4^{n-1}\cdot n}{2}\\
&=\frac{n}{2}\cdot \left({2n-1\choose n-1} + 4^{n-1}\right)
\end{split}$$

发表评论

电子邮件地址不会被公开。 必填项已用*标注