Skip to Content

2. Generating Functions

2019-09-04·Combinatorics
  • ordinary generating function(OGF) define by ana_n: G(x)=∑n≥0anxnG(x)=\sum_{n\geq0}a_nx^n
  • coefficient: [xk]G(x)[x^k]G(x)
  • C[[x]]\mathbb{C}[[x]]: ring of formal power series with complex coefficient
  • Combination: 3 red, 4 blue, and 5 green
    • (1+x+x2+x3)(1+x+x2+x3+x4)(1+x+x2+x3+x4+x5)(1+x+x^2+x^3)(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4+x^5)
    • coefficient xkx^k gives the number of way to select kk balls
  • Fibonacci number
    • Fn=15(ϕn−ϕ^n),ϕ=1+52,ϕ^=1−52F_n=\frac{1}{\sqrt{5}}(\phi^n-\hat\phi^n),\phi=\frac{1+\sqrt{5}}{2},\hat\phi=\frac{1-\sqrt{5}}{2}
    • G(x)=x1−x−x2=x(1−ϕx)(1−ϕ^x)=α1−ϕx+β1−ϕ^xG(x)=\frac{x}{1-x-x^2}=\frac{x}{(1-\phi x)(1-\hat\phi x)}=\frac{\alpha}{1-\phi x}+\frac{\beta}{1-\hat\phi x}
  • General Methodology
    • Give a recursion that computes ana_n
    • Give the generating function and manipulate the right hand side of equation so that it becomes some other expression involving G(x)G(x)
      • shift: xkG(x)=∑n≥kgn−kxnx^kG(x)=\sum_{n\geq k}g_{n-k}x^n
      • addition: F(x)+G(x)=∑n≥0(fn+gn)xnF(x)+G(x)=\sum_{n\geq 0}(f_n+g_n)x^n
      • convolution: F(x)G(X)=∑n≥0∑k=0nfkgn−kxnF(x)G(X)=\sum_{n\geq 0}\sum_{k=0}^nf_kg_{n-k}x^n
      • differentiation: G′(x)=∑n≥0(n+1)gn+1xnG'(x)=\sum_{n\geq0}(n+1)g_{n+1}x^n
    • Solve the resulting equation to derive an explicit formula for G(x)G(x)
    • Expand G(x)G(x) into a power series and read off the coefficient of xnx^n
      • Taylor expansion: G(x)=∑n≥0G(n)(0)n!xnG(x)=\sum_{n\geq 0}\frac{G^{(n)}(0)}{n!}x^n
      • Geometric sequence: 11−x=∑n≥0xn\frac{1}{1-x}=\sum_{n\geq0}x^n
        • G(x)=∑i=1kai1−bixG(x)=\sum_{i=1}^{k}\frac{a_i}{1-b_ix}, [xn]G(x)=∑i=1kaibin[x^n]G(x)=\sum_{i=1}^ka_ib_i^n
      • Newton's formular: (1+x)α=∑n≥0(αn)xn(1+x)^\alpha=\sum_{n\geq0}{\alpha\choose n}x^n
        • (αn)=α(α−1)⋯(α−(n−1))n!{\alpha\choose n}=\frac{\alpha(\alpha-1)\cdots(\alpha-(n-1))}{n!}
        • (−nm)=(−1)m(n+m−1m){-n\choose m}=(-1)^m{n+m-1\choose m}
  • Catalan Number: Cn=∑k=0n−1CkCn−1−k,C0=1C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k},C_0=1
    • Interpretation
      • 出入栈：the number of expressions containing n pairs of parentheses which are correctly matched：以最后一个左括号的对应右括号的位置为 choice，划分成两个部分
      • Dyck words of length 2n2n(A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's)
      • the number of different ways n+1n + 1 factors can be completely parenthesized
      • the number of full binary trees with n+1n + 1 leaves
      • 单调路径：the number of monotonic lattice paths along the edges of a grid with n×nn × n square cells, which do not pass above the diagonal
      • 三角形剖分：triangulations of a convex (n+2)(n+2)-gon
      • 二叉树种类
    • Cn=1n+1(2nn)C_n=\frac{1}{n+1}{2n\choose n}
      • Generating function
        • G(x)2=∑n≥0∑k=0nCkCn−kxnG(x)^2=\sum_{n\geq0}\sum_{k=0}^nC_kC_{n-k}x^n
        • G(x)=1+xG(x)2⇒G(x)=1−(1−4x)122xG(x)=1+xG(x)^2\Rightarrow G(x)=\frac{1-(1-4x)^{\frac{1}{2}}}{2x}
          • 二次方程只有一解：lim⁡x→0G(x)=C0\lim_{x\rightarrow0}G(x)=C_0
        • G(x)=2∑n≥0(12n+1)(−4x)nG(x)=2\sum_{n\geq0}{\frac{1}{2}\choose n+1}(-4x)^n
      • Andre's reflection method: Cn=(2nn)−(2nn+1)C_n={2n\choose n}-{2n\choose n+1}
      • bijective proof: split up the set of all monotonic paths into n+1n + 1 equally sized classes
    • Ω(4nn3/2)\Omega(\frac{4^n}{n^{3/2}})
  • Quicksort
    • Quicksort recursion: Tn=1n∑k=1n(n−1+Tk−1+Tn−k)T_n=\frac{1}{n}\sum_{k=1}^n(n-1+T_{k-1}+T_{n-k})
    • ∑n≥0nTnxn=∑n≥0n(n−1)xn+2∑n≥0(∑k=0n−1Tk)xn\sum_{n\geq0}nT_nx^n=\sum_{n\geq 0}n(n-1)x^n + 2\sum_{n\geq0}(\sum_{k=0}^{n-1}T_k)x^n
    • xG′(x)=2x2(1−x)3+2x1−xG(x)xG'(x)=\frac{2x^2}{(1-x)^3}+\frac{2x}{1-x}G(x)
    • G(x)=2(1−x)2ln⁡11−xG(x)=\frac{2}{(1-x)^2}\ln\frac{1}{1-x}
    • Tn=2(n+1)H(n)−2nT_n=2(n+1)H(n)-2n