目录

• 定义
  • * 普通生成函数OGF
    • 指数生成函数 EGF
    • Dirichlet生成函数
    • Notation
• OGF
  • * OGF property
    • some OGF instances
• EGF
  • * EGF property
    • some EGF instances
• Dirichlet生成函数
  • * Dirichlet GF property
    • some Dirichlet GF instances

upd 2021-02-25 刚学会怎么把html传到github然后弄出来一个url让你访问

https://yhm138.github.io/personal_yhm138/memos/gf.html

定义

普通生成函数OGF

\[f(x)=\sum_{n=0}^{\infty}a_nx^n
\]

指数生成函数 EGF

\[f(x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n
\]

Dirichlet生成函数

\[f(s)=\sum_{n=1}^{\infty}\frac{a_n}{n^s}
\]

Notation

\(P()\) denotes Polynomial

\(S_1(n,k)\) denotes the Stirling's number of the first kind，and \(S_2(n,k)\) so on

\(\mu(n)\) denotes mobius function

\(p\) prime

OGF

OGF property

\[f(x)g(x)\stackrel{}{\longleftrightarrow}\{\sum_{n=0}^{\infty}a_kb_{n-k}
\}_{n=0}^{\infty}
\]

\[f^k(x)\stackrel{}{\longleftrightarrow}
\{
\sum_{n_1+n_2+…+n_k=n}a_{n_1}a_{n_2}a_{n_3}…a_{n_k}
\}_{n=0}^{\infty}
\]

\[\frac{f(x)}{1-x}\stackrel{}{\longleftrightarrow}
\{
\sum_{j=0}^n a_j
\}_{n=0}^{\infty}
\]

\[P(xD)f\stackrel{}{\longleftrightarrow}
\{
P(n)a_n
\}_{n=0}^{\infty}
\]

some OGF instances

\[\frac{1}{1-x}{\longleftrightarrow}
\{
\ 1\
\}_{n=0}^{\infty}
\]

\[\frac{x}{(1-x)^2}{\longleftrightarrow}
\{
\ n\
\}_{n=0}^{\infty}
\]

\[\frac{1}{(1-x)^k}{\longleftrightarrow}
\{
\ \tbinom{n+k-1}{n}\
\}_{n=0}^{\infty}
\]

\[\frac{1}{(1-rx)^k}{\longleftrightarrow}
\{
\ \ \tbinom{n+k-1}{n}r^n\ \
\}_{n=0}^{\infty}
\]

\[\frac{1}{1-cx}{\longleftrightarrow}
\{
c^n
\}_{n=0}^{\infty}
\]

EGF

EGF property

\[D^k f{\longleftrightarrow}
\{
a_{n+k}
\}_{n=0}^{\infty}
\]

\[xDf{\longleftrightarrow}
\{
na_n
\}_{n=0}^{\infty}
\]

\[P(xD)f {\longleftrightarrow}
\{
P(n)a_n
\}_{n=0}^{\infty}
\]

\[f(x)g(x){\longleftrightarrow}
\{
\sum_{k=0}^n \tbinom{n}{k} a_kb_{n-k}
\}_{n=0}^{\infty}
\]

\[f(x)g(x)h(x)={\longleftrightarrow}
\{
\sum_{i+j+k=n\\i,j,k\geq0}\tbinom{n}{i,j,k}a_ib_jc_k
\}_{n=0}^{\infty}
\]

\[f^k(x){\longleftrightarrow}
\{
\sum_{n_1+n_2+…+n_k=n\\n_i\geq0,i=1,2,…,k}\tbinom{n}{n_1,n_2,…n_k}a_{n_1}a_{n_2}…a_{n_k}
\}_{n=0}^{\infty}
\]

some EGF instances

\[e^x{\longleftrightarrow}
\{
1
\}_{n=0}^{\infty}
\]

\[e^{cx}{\longleftrightarrow}
\{
c^n
\}_{n=0}^{\infty}
\]

\[\frac{(e^x-1)^k}{k!}{\longleftrightarrow}
\{
\ S_2(n,k)\
\}_{n=0}^{\infty}
\]

\[\frac{[ln(1+x)]^k}{k!}{\longleftrightarrow}
\{
\ S_1(n,k)\
\}_{n=0}^{\infty}
\]

Dirichlet生成函数

Dirichlet GF property

\[f(s)g(s){\longleftrightarrow}
\{
\sum_{d|n}a_db_{\frac{n}{d}}
\}_{n=1}^{\infty}
\]

\[f^k(s){\longleftrightarrow}
\{
\sum_{n_1n_2…n_k=n}a_{n_1}a_{n_2}…a_{n_k}
\}_{n=1}^{\infty}
\]

some Dirichlet GF instances

\[\zeta(s){\longleftrightarrow}
\{
1
\}_{n=1}^{\infty}
\]

\[[\zeta(s)]^2{\longleftrightarrow}
\{
\sum_{d|n}1
\}_{n=1}^{\infty}
\]

\[\frac{1}{\zeta(s)}{\longleftrightarrow}
\{
\ \mu(n)\
\}_{n=1}^{\infty}
\]

\[[\zeta(s)]^k{\longleftrightarrow}
\{
n可分解为k个有序正因子积的方法数
\}_{n=1}^{\infty}
\]

\[[\zeta(s)-1]^k{\longleftrightarrow}
\{
n可分解为k个非平凡有序正因子积的方法数
\}_{n=1}^{\infty}
\]

\[\prod_{p}(\sum_{k=0}^{\infty}f(p^k)p^{-ks}){\longleftrightarrow}
\{
积性数论函数f(n)
\}_{n=1}^{\infty}
\]

先写到这，不定期更新

编辑公式不易，转载请注明出处

2020-08-20