二项式系数

  • 定义：

    (x+y)n=∑k=0n(nk)xkyn−k\begin{align}(x+y)^n=\sum_{k=0}^n\left(\begin{matrix}n\\k\end{matrix}\right)x^ky^{n-k}\end{align}

  • 下指数一定为整数，当其为负数时，二项式系数为零，否则：

    • 当上指数为整数时， (nk)=n!k!(n−k)!\begin{align}\left(\begin{matrix}n\\k\end{matrix}\right)=\frac{n!}{k!(n-k)!}\end{align}，具有组合意义
    • 上指数可推广为实数，此时 (nk)=nk‾k!\begin{align}\left(\begin{matrix}n\\k\end{matrix}\right)=\frac{n^{\underline k}}{k!}\end{align}，可视为nn的kk次多项式((1+r)k(1+r)^k泰勒展开的系数)

  • 当上指数为正整数时：

    • ∑k=0n(nk)=2n\begin{align}\sum_{k=0}^n\left(\begin{matrix}n\\k\end{matrix}\right)=2^n\end{align}、 ∑k=0n(−1)k(nk)=0\begin{align}\sum_{k=0}^n(-1)^k\left(\begin{matrix}n\\k\end{matrix}\right)=0\end{align}，均可通过定义证明
    • 下指数任意， (nk)=(nn−k)\begin{align}\left(\begin{matrix}n\\k\end{matrix}\right)=\left(\begin{matrix}n\\n-k\end{matrix}\right)\end{align}

  • 当上指数为任意实数时：

    • 下指数不为零时， (nk)=nk(n−1k−1)\begin{align}\left(\begin{matrix}n\\k\end{matrix}\right)=\frac nk\left(\begin{matrix}n-1\\k-1\end{matrix}\right)\end{align}
    • (nk)=(n−1k)+(n−1k−1)\begin{align}\left(\begin{matrix}n\\k\end{matrix}\right)=\left(\begin{matrix}n-1\\k\end{matrix}\right)+\left(\begin{matrix}n-1\\k-1\end{matrix}\right)\end{align}

  • 特殊值：

    • (n0)=1\left(\begin{matrix}n\\0\end{matrix}\right)=1
    • (n1)=n\left(\begin{matrix}n\\1\end{matrix}\right)=n
    • (nn)=1\left(\begin{matrix}n\\n\end{matrix}\right)=1

  • 序列构造母函数：<a0,⋯ ,an><a_0,\cdots,a_n>的母函数为A(x)=a0+a1x+a2x2+⋯+anxnA(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n

  • 母函数乘积的系数：若C(x)=A(x)B(x)C(x)=A(x)B(x)，则

    cn=∑k=0nakbn−k\begin{align}c_n=\sum_{k=0}^na_kb_{n-k}\end{align}

    • 证明范德蒙德卷积：由(1+x)a+b=(1+x)a(1+x)b(1+x)^{a+b}=(1+x)^a(1+x)^b，设为C(x)=A(x)B(x)C(x)=A(x)B(x) 由

      C(x)=∑k=0n(a+bk)xkA(x)=∑k=0n(ak)xkB(x)=∑k=0n(bk)xk\begin{align}&C(x)=\sum_{k=0}^n\left(\begin{matrix}a+b\\k\end{matrix}\right)x^k\\&A(x)=\sum_{k=0}^n\left(\begin{matrix}a\\k\end{matrix}\right)x^k\\&B(x)=\sum_{k=0}^n\left(\begin{matrix}b\\k\end{matrix}\right)x^k\end{align}

      得

      cn=(a+bn)=∑k=0n(ak)(bn−k)\begin{align}c_n=\left(\begin{matrix}a+b\\n\end{matrix}\right)=\sum_{k=0}^n\left(\begin{matrix}a\\k\end{matrix}\right)\left(\begin{matrix}b\\n-k\end{matrix}\right)\end{align}

  • 常见母函数：

    • (1+x)n=∑k=0n(nk)xk\begin{align}(1+x)^n=\sum_{k=0}^n\left(\begin{matrix}n\\k\end{matrix}\right)x^k\end{align}
    • 11−x=∑k≥0xk、11+x=∑k≥0(−1)kxk\begin{align}\frac1{1-x}=\sum_{k\ge0}x^k、\frac1{1+x}=\sum_{k\ge0}(-1)^kx^k\end{align}
    • 1(1−x)n+1=∑k≥0(n+kk)xk\begin{align}\frac1{(1-x)^{n+1}}=\sum_{k\ge0}\left(\begin{matrix}n+k\\k\end{matrix}\right)x^k\end{align}
    • xn(1−x)n+1=∑k≥0(kn)xk\begin{align}\frac{x^n}{(1-x)^{n+1}}=\sum_{k\ge0}\left(\begin{matrix}k\\n\end{matrix}\right)x^k\end{align}，通过上式移项换元得到

第二类斯特林数

  • 定义： xn=∑k{nk}xk‾\begin{align}x^{n}=\sum_{k}\left\{\begin{matrix}n\\k\end{matrix}\right\}x^{\underline k}\end{align}，组合意义为将nn个元素分为kk个无区别的非空集合
  • 递推式： {nk}=k{n−1k}+{n−1k−1}\begin{align}\left\{\begin{matrix}n\\k\end{matrix}\right\}=k\left\{\begin{matrix}n-1\\k\end{matrix}\right\}+\left\{\begin{matrix}n-1\\k-1\end{matrix}\right\}\end{align} 组合意义：将第nn个元素分到kk个原有盒子的方案为第一项，将它单独作为一个集合的方案数为第二项
  • 特殊值：
    • {n0}={1,n=00,n≠0\left\{\begin{matrix}n\\0\end{matrix}\right\}=\begin{cases}1,&n=0\\0,&n\ne0\end{cases}
    • {n1}=1\left\{\begin{matrix}n\\1\end{matrix}\right\}=1
    • {n2}=∑k=1n−1(nk)2=2n−1−1\begin{align}\left\{\begin{matrix}n\\2\end{matrix}\right\}=\frac{\sum\limits_{k=1}^{n-1}\left(\begin{matrix}n\\k\end{matrix}\right)}2=2^{n-1}-1\end{align}
    • {nn−1}=(n2)=n(n−1)2\left\{\begin{matrix}n\\n-1\end{matrix}\right\}=\left(\begin{matrix}n\\2\end{matrix}\right)=\frac{n(n-1)}2
    • {nn}=1\left\{\begin{matrix}n\\n\end{matrix}\right\}=1

第一类斯特林数

  • 定义：xn‾=∑k≥0[nk]xkx^{\overline n}=\sum_{k\ge0}\left[\begin{matrix}n\\k\end{matrix}\right]x^k，组合意义为将nn个元素分为kk个轮换

  • 递推式：[nk]=(n−1)[n−1k]+[n−1k−1]\left[\begin{matrix}n\\k\end{matrix}\right]=(n-1)\left[\begin{matrix}n-1\\k\end{matrix}\right]+\left[\begin{matrix}n-1\\k-1\end{matrix}\right]

    组合意义为将第nn个元素插入到已有划分的n−1n-1个位置上(第一项)，或作为单独一个轮换(第二项)

  • 特殊值：

    • [n0]={0,n≠01,n=0\left[\begin{matrix}n\\0\end{matrix}\right]=\begin{cases}0,&n\ne0\\1,&n=0\end{cases}
    • [n1]=(n−1)!\left[\begin{matrix}n\\1\end{matrix}\right]=(n-1)!
    • [nn−1]=(n2)=n(n−1)2\left[\begin{matrix}n\\n-1\end{matrix}\right]=\left(\begin{matrix}n\\2\end{matrix}\right)=\frac{n(n-1)}2
    • [nn]=1\left[\begin{matrix}n\\n\end{matrix}\right]=1
    • 一般来说，第一类斯特林数大于第二类斯特林数，当k=0,n−1,nk=0,n-1,n时两者相等
    • ∑k=0n[nk]=n!\sum_{k=0}^n\left[\begin{matrix}n\\k\end{matrix}\right]=n!

调和数

  • 定义：

    Hn=∑k=1n1k\begin{align}H_n=\sum_{k=1}^n\frac1{k}\end{align}

  • 和第一类斯特林数关系：n!Hn=[n+12]n!H_n=\left[\begin{matrix}n+1\\2\end{matrix}\right]

    证：

    [n+12]=n[n2]+(n−1)!⇒1n![n+12]=1(n−1)![n2]+1n,由递推式⇒1n![n+12]=Hn\begin{align}&\left[\begin{matrix}n+1\\2\end{matrix}\right]=n\left[\begin{matrix}n\\2\end{matrix}\right]+(n-1)!\\&\Rightarrow\frac1{n!}\left[\begin{matrix}n+1\\2\end{matrix}\right]=\frac1{(n-1)!}\left[\begin{matrix}n\\2\end{matrix}\right]+\frac1n,由递推式\\&\Rightarrow\frac1{n!}\left[\begin{matrix}n+1\\2\end{matrix}\right]=H_n\end{align}
当2k≤n<2k+1时,只需证明n=2k时Hn>⌊lg⁡n⌋+12且n=2k−1−1时Hn≤⌊lg⁡n⌋+1即可(1)当n=2k时,右式=k+12Hn=∑i=0k∑j=2i−12i1j>∑i=0k2j−12j>k+12(2)当n=2k+1−1时,右式=k+1Hn=∑i=0k∑j=i2i+1−11j≤∑i=0k\begin{align}&当2^k\le n<2^{k+1}时,只需证明n=2^k时H_n>\frac{\lfloor\lg n\rfloor+1}2\\&且n=2^{k-1}-1时H_n\le\lfloor\lg n\rfloor+1即可\\&(1)当n=2^k时,右式=\frac{k+1}2\\&H_n=\sum_{i=0}^k\sum_{j=2^{i-1}}^{2^i}\frac1j>\sum_{i=0}^k\frac{2^{j-1}}{2^j}>\frac{k+1}2\\&(2)当n=2^{k+1}-1时,右式=k+1\\&H_n=\sum_{i=0}^k\sum_{j=i}^{2^{i+1}-1}\frac1j\le\sum_{i=0}^k\end{align}