1
\[\sec ^2 x+1=\tan^2x \]设 \(E(x)=\tan x+\sec x\),则有:
\[2\tan xE(x)=E(x)^2+1 \]这是因为 \(\tan x\) 是奇数长度的大小关系交替变换的排列的 EGF,\(E(x)\) 则去掉了奇数条件。此时一个 \(n\) 阶交替排列在两边都会被统计 \(n-(n\bmod 2)\) 次。
然后变换一下就可以了。
2
统计 \(n\) 阶平面二叉树 \(a_d=\sum [dep_i=d]\) 的 \(a\) 序列。
首先这等价于计算序列 \(a_1=1,a_i\in [1,2a_{i-1}],\sum a_i=n\)。
这是所谓“Carlitz composition”的一种。
因为有很多状态,搞个多元 GF 出来。设 \(H^{[k]}(q,u)\) 是 \(k\) 长度 \(a\) 序列的 OGF,\(H^{[k]}_{n,j}\) 是长度为 \(k\),最后一项是 \(j\),和为 \(n\) 的 GF。
即:
\[H^{[k]}(q,u)=\sum_{n,j}H_{n,j}^{[k]}q^nu^j\\ H(q,u)=\sum_kH^{[k]}(q,u) \]考虑添加最后一项的操作。这就是把 \(H^{[k]}(q,u)\) 的 \(u^k\) 换为
\[\sum_{i=1}^{2k}(uq)^i=\frac{uq}{1-uq}(1-(uq)^{2k}) \]这就是说:
\[H^{[k+1]}(q,u)=\sum_{n,j}H_{n,j}^{[k]}q^n\frac{uq}{1-uq}(1-(uq)^{2k})\\ =\frac{uq}{1-uq}\left (\sum_{n,j}H^{[k]}_{n,j} q^n-\sum_{n,j}H_{n,j}^{[k]}q^{n+2j}u^{2j}\right )\\ =\frac{uq}{1-uq}\left(H^{[k]}(q,1)-H^{[k]}(q,u^2q^2)\right) \]现对左右两式同时对 \(k\) 求和,就得到:
\[H(q,u)=uq+\frac{uq}{1-uq}\left(H(q,1)-H(q,u^2q^2)\right) \]那么设
\[G(u)=uq+\frac{uq}{1-uq}H(q,1) \]则
\[H(q,u)=G(u)-\frac{uq}{1-uq}\left(G(u^2q^2)-\frac{u^2q^3}{1-u^2q^3}\left( G(u^4q^6)-\dots\right. \right. \]现在令 \(u=1,H(q)=H(q,1)\)。
\[H(q)=G(1)-\frac{q}{1-q}\left(G(q^2)-\frac{q^3}{1-q^3}\left( G(q^6)-\dots\right. \right. \]具体来说:
\[H(q)=\sum_{i\ge 1}G(q^{2^i-2})\prod_{1\le j<i}\frac{-q^{2^j-1}}{1-q^{2^j-1}}\\ =\sum_{i\ge 1}(q^{2^i-1}+\frac{q^{2^i-1}}{1-q^{2^i-1}}H(q))\frac{(-1)^{i-1}q^{2^i-i-1}}{\prod_{1\le j<i}(1-q^{2^j-1})}\\ =\sum_{i\ge 1}\frac{(-1)^{i-1}q^{2^{i+1}-i-2}}{\prod_{1\le j<i}(1-q^{2^j-1})}+H(q)\sum_{i\ge 1}\frac{(-1)^{i-1}q^{2^{i+1}-i-2}}{\prod_{1\le j\le i}(1-q^{2^j-1})} \]那么:
\[H(q)=\left(\sum_{i\ge 1}\frac{(-1)^{i-1}q^{2^{i+1}-i-2}}{\prod_{1\le j<i}(1-q^{2^j-1})}\right){\huge/}\left(1-\sum_{i\ge 1}\frac{(-1)^{i-1}q^{2^{i+1}-i-2}}{\prod_{1\le j\le i}(1-q^{2^j-1})}\right) \]显然可以 polylog 计算。
标签:right,frac,2q,闲话,sum,uq,729,left From: https://www.cnblogs.com/british-union/p/18331096/zhicheng123_is_shabby