\begin{align}
K(a, x) =& \prod_{i = 0}^\infty (1 + ax^{2i+1}) \\
=& \sum_{i=1}^\infty a^ix^{i^2}\prod_{j=1}^i \frac{1}{1-x^{2j}}
\end{align}

\(K(a, x) = \sum_{i=0}^\infty c_i a^i\)と置いて\(K(a, x) = (1 + ax)K(ax^2, x)\)で係数比較すると、上記の式が得られる。基数を真ん中で折りたたんで、正方形を作ってもよい。

$$\prod_{i=1}^\infty \frac{1}{1-ax^i} = \sum_{i=0}^\infty a^ix^i \prod_{j=1}^i \frac{1}{1-x^j}$$

同様にすると、上記の式が得られる。Young図形の見る方向を変えても得られる。

正方形を作ると下の式が得られる（Durfee’s square）

$$\frac{1}{\prod_{i \geq 1}(1-x^i)} = \sum x^{i^2}\frac{1}{\prod_{1 \leq j \leq i}(1-x^j)^2}$$

集合スターリング数
\begin{align}
&\left[\frac{x^n}{n!}\right]\exp(t(\exp(x-1)) \\
=& \left[\frac{x^n}{n!}\right]\exp(-t)\exp(t\exp(x)) \bmod t^{n+1} \\
=&\exp(-t) \sum_{i=0}^n i^nt^i
\end{align}

• \(i!i^n\) は n 元集合を分割して、長さ i の順列を作る場合の数。順列の要素として空集合を許す。
• \(i!\biggl\{{\!n\! \atop \!i\!}\biggr\}\) は n 元集合を分割して、長さ i の順列を作る場合の数。順列の要素として空集合を許さない。\(\exp t\) を掛けると、空集合を許す場合になる。

これらより、\([x^{\underline{m}}]\sum_i a_i x^i = [t^n/n!]\sum_{i}\sum_i a_n i^n\exp(-t)\) となり、多点評価 \(O(n \log(n)^2)\) で求まる。
\(Ef(n) = f(n + 1), \Delta = E – 1\) とする。
\begin{align}
f(n) &= E^nf(0) \\
&=(\Delta+1)^nf(0) \\
&= \sum_{i=0}^n {n \choose i} \Delta^i f(0)
\end{align}

\(f(x)=x^n\) とすると、\(\left[\frac{x^n}{n!}\right]\frac{(\exp(x)-1)^i}{i!}=\biggl\{{\!n\! \atop \!i\!}\biggr\}\) より \(\frac{\Delta^i f(0)}{i!}=\biggl\{{\!n\! \atop \!i\!}\biggr\}\) だから
\begin{align}
x^n =& \sum_{i=0}^n {x \choose i} \Delta^i f(0) \\
=&\sum_{i=0}^n x^{\underline{i}}\biggl\{{\!n\! \atop \!i\!}\biggr\}
\end{align}
となる。

解釈１

• 左辺：\(\#[x]^{[n]}\)
• 右辺：像のサイズ \(i\) 毎に数える。

解釈２

• 左辺：\(\{(i, j) : 1 \leq i \leq n, 1 \leq j \leq x + i – 1 \}\) に \(n\) 個の non-ataccking rook を配置する方法
• 右辺：下段の長方形 \(n \times x\) に含まれる rook の数毎に数える。

評価点のシフト

シフトオペレターを \(S\) とすると \(d\) 次多項式に対して

\begin{align}
&S^m \pmod {(S-1)^{d+1}} \\
=&\sum_{j=0}^d{m \choose j}(S-1)^j \\
\end{align}
が成り立つ。\(\# \{ f ∈[S]^{[m]}: \text{$f(x)=1$ となる $x$ が $m-d$ 個以上}\}\) と読み替えて包除すると、
\begin{align}
&\sum_{j=m-d}^m {j-1 \choose m-d-1}(-1)^{j}{m \choose j}S^{m-j} \\
=&\frac{m!}{(m-d-1)!}\sum_{j=0}^{d} \frac{1}{(d-j)!j!(m-j)}(-1)^{m-j}S^{j}
\end{align}
となり、畳み込みになる。

微分 \(df(x)/dx\) は、最小要素を \(x\) のべき指数に加えないことを表している。従って、\(\int f’g dt\) は最小の要素が \(f\) に含まれるような \(fg\) の要素を表す。つまり、\(f_{i} \leftarrow f_{i-1}\) という変換。従って、テイラー展開 \(f(x+y)=\sum_{i \geq 0} \frac{d^if(x)}{dx^i} \frac{y^i}{i!}\) は \(d^if(x)/dx^i\) によって \(y\) のための \(i\) 個の空きを作っている。また、連鎖律 \((fg)’=f’g+fg’\) は最小要素をどちらから取るか2通り試している。

• \(f=\log\frac{1}{1-x}\) ならば \(f’=\frac{1}{1-x}\)
• \(f=\exp(g)\) ならば \(f’=g’f\)
• \(f=\frac{1}{1-g}\) ならば \(f’=fg’f\)
• \(f=\log \frac{1}{1-g}\) ならば \(f’=g’\frac{1}{1-g}\)

ニュートン法

\(y_n = y \mod x^M\) とする。

逆関数の木

\(y=A^{\langle -1\rangle}(x)\) を満たす \(y\) は
$$ y_{n+1} = y_n+(x-A(y_n))/A'(y_n) \pmod{x^{2M}}$$
によって求まる。\(A(x)=x-a_2x^2-a_3x^3-\cdots\)とすると、\(x-A(y_n)\) は部分木のサイズが M 未満かつ全体のサイズが M 以上の木の母関数。\(1/A'(y_n)=1/(1-\sum na_nx^{n-1})\) と見ると、そのような木の親を次々繋げている。

• \(y=\exp(f(x))\) のとき \(y_{n+1}=y_n+(f(x)-\log(y_n))y_n\)

木

部分木のサイズが \(M\) 以上のもののうち、深さ最大のものに着目する。そのような木の母関数は \(x\exp(y_n)-y_n\) なので \(y=x(\exp(y))\) のとき \(y_{n+1}=y_n+(x\exp(y_n)-y_n)/(1-y_n)\)

ラベルなし木

\(f=x\exp(\sum_{i \geq 1} \frac{1}{i}f(x^i))\) のとき　\(y_{n+1}=y_n+\frac{x\exp(\sum_{i \geq 1} \frac{1}{i}y_n(x^i))-y_n}{1-x\exp(\sum_{i \geq 1} \frac{1}{i}y_n(x^i))}\)　（ABC230H）

合成

Breng-Kungの合成のアルゴリズム。
\(f(g_1+x^{m}g_2)=\sum f^{(n)}(g_1)g_2^ix^{mi}\) と \(f'(g(x)) = \frac{df(g(x))/dx}{g’}\) を用いる。\(f(g_1)\) は \(f(g_1)=f_0(g_1)+g_1^{N/2}f_1(g_1)\) のようにして、部分問題に分解する。\(e\) 回再帰すると \(T(N)\leq 2^eT(N/2^e)+\sum_{i=0}^{2^{e-1}} N\log(N)\) となり、\(2^e=\sqrt{N/\log(N)}\) で \(T(N) = O((N\log(N))^{3/2})\) を得る。

\(1/f(x) \mod x^n\)は\(O(n \log(n)\)から\(O(n \log(\deg(f))\) にできる。

\(F(x)=\prod_{f(\alpha)=0}(x-\alpha)\)に対して、
\begin{align}
\log(F) &= \sum_{f(\alpha)=0} \log(x-\alpha) \\
xF’/F&= \sum_{f(\alpha)=0} \frac{x}{x-\alpha} \\
\frac{1}{t}F’\left(\frac{1}{t}\right)/F\left(\frac{1}{t}\right)&= \sum_{f(\alpha)=0} \frac{1}{1-\alpha t} \\
\end{align}

従って、\(f \otimes g = \prod_{f(\alpha)=0, g(\beta)=0}(x-\alpha\beta)\) が \(O(n \log(n))\) で求まる。Bostan, Alin, et al. “Fast computation of special resultants.” Journal of Symbolic Computation 41.1 (2006): 1-29.

\(L\left( \frac{x^n}{n!}\right) = \frac{1}{t^{n+1}}\) とする。
\(L(\exp(ax)) = \frac{1/t}{1-a/t}\) なので、\(\exp(x)\) の代入は \(O(n \log(n))\) でできる。

\begin{align}
&L^{-1}( t^{-1}\sum_{f(\alpha)=0} \alpha^i t^{-i})) \\
=& L^{-1}( \sum_{f(\alpha)=0}\frac{1/t}{1-\alpha/t}) \\
=& \sum_{f(\alpha)=0}\exp(\alpha x) \\
\end{align}

よって、\(f \oplus g = \sum_{f(\alpha)=0, g(\beta)=0}(x-\alpha-\beta)\)が\(O(n\log(n))\) で求まる。Polynomial Taylor Shiftはその特殊系である。\(L( \frac{x^n}{n!}\exp(-ax)) = \frac{1}{(t+\alpha)^{n+1}}\)を用いてもよい。\(L^{-1}(\exp(-ax)F(x)=f(t-a))\) は残念ながら成り立たないが、その近似形を使ってもよい。exp(ax) x^n/n! と x^n/(1-ax)^{n+1} は同じ数え上げを egf/ogf で表している。