GF for counting
Dependencies
\[ \log(1+z)=\sum_{k\ge1}\frac1k(-1)^{k-1}z^k \]
\[ \exp(z)=\sum_{k\ge0}\frac{z^k}{k!} \]
Lagrange Inversion
given polynomial \(h\) where \(h_0=0\) and \(h_1\not=0\), find \(y\) which \(z=h(y(z))\) holds.
Let \(\phi(y)=y/h(y)\).
Formally, When
\[ y(z)=z\,\phi(y) \]
We have
\[ y_n=\frac1n[u^{n-1}]\phi(u)^{n} \]
\[ [z^n]y(z)^k=\frac k n[u^{n-k}]\phi(u)^n \]
\[ [z^n]H(y(z))=\frac1n[u^n](H^{'}(u)\ \phi(u)^n) \]
Tip: When The Tree equations are too intense to solve try Lagrange Inversion!
OGF
Basic Constructions
\(B=SEQ(A)\)
\[ B(z)=\frac{1}{1-A(z)} \]
\(B=PSET(A)\)
\[ B(z)=\exp(\sum_{k\ge1}\frac{(-1)^{k-1}}{k}A(z^k)) \]
\(B=MSET(A)\)
\[ B(z)=\exp(\sum_{k\ge1}\frac{1}{k}A(z^k)) \]
\(B=CYC(A)\)
\[ B(z)=\sum_{k\ge1}\frac{\varphi(k)}{k}\log(\frac{1}{1-A(z^k)}) \]
Note:
Those equations handle the empty object implicitly, thus:
For general constructions, \(A_0=0\) holds.
For size-restricted constructions \(A_0=1\) holds.
Polya Theorem
Cycle Index
\[ Z(G;x_1,x_2, \dots, x_m)=\frac1{|G|}\sum_{g\in G}x_1^{j_1(g)}x_2^{j_2(g)}\cdots x_m^{j_m(g)} \]
OGF over Groups
\(B=A^M/G\)
\[ B(z)=Z(G;A(z),A(z^2),\dots,A(z^m)) \]
Memorize
Cycle \(Z=\frac1 m\sum_{d|m}\varphi(d)x_d^{n/d}\)
Mirror \(Z=\frac1 2x_1^{2v}+\frac12x_2^v\) or \(Z=\frac12x_1^{2v+1}+\frac12x_1x_2^v\)
All Permutations \(Z=\sum(z^{j_1}z^{j_2}\cdots z^{j_m})/(j_1!j_2!\cdots j_m!1^{j_1}2^{j_2}\cdots m^{j_m})\)
\(PSET_k,MSET_k\)的计算
需要枚举拆分数，套用cycle index
注意，PSET构造时对\(F(z)\)符号取负即可
Additional Useless formula
\[ MSET_k(F) = [u^k]\exp(\sum_{k\ge1}\frac{u^k}kF(z^k)) \]
\[ PSET_k(F) = [u^k]\exp(\sum_{k\ge1}\frac{u^k}k(-1)^{k-1}F(z^k)) \]
\[ CYC_k(F)=[u^k]\sum_{k\ge1}\frac{\varphi(k)}k\log(\frac1{1-u^kF(z^k)}) \]
EGF
\(B=SEQ(A)\)
\[ B(z)=\frac1{1-A(z)} \]
\(B=SET(A)\)
\[ B(z)=\exp(A(z)) \]
*objects are distinguishable through labels anyway.
\(B=CYC(A)\)
\[ B(z)=\log(\frac1{1-A(z)}) \]
*same here.
\(B=SET_k(A)\)
\[ B(z)=\frac1{k!}A(z)^k \]
Additional constructions
\(graph\,F\rightarrow connected\ graph\,G\) (applying inverse operation of exp/polya exp)
\(MSET(G)=F\)
\[ G(z)=\log(F(z)) \]