💡

数学相关

创建于 2023-10-25

Tags: 笔记

  • 子集反演

g(S)=TSf(T)f(S)=TSg(T)(1)STg(S)=\sum_{T\subseteq S}f(T) \Leftrightarrow f(S)=\sum_{T\subseteq S}g(T)\cdot (-1)^{|S|-|T|}

h(S)=TSf(T)f(S)=TSh(T)(1)TSh(S)=\sum_{T\supseteq S}f(T) \Leftrightarrow f(S)=\sum_{T\supseteq S}h(T)\cdot (-1)^{|T|-|S|}

  • 二项式反演

g(n)=i=0n(ni)f(i)f(n)=i=0n(1)ni(ni)g(i)g(n)=\sum_{i=0}^n\binom{n}{i}f(i)\Leftrightarrow f(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g(i)

h(n)=i=nm(in)f(i)f(n)=i=nm(1)in(in)h(i)h(n)=\sum_{i=n}^m\binom{i}{n}f(i)\Leftrightarrow f(n)=\sum_{i=n}^m(-1)^{i-n}\binom{i}{n}h(i)

  • 莫比乌斯反演

[gcd(x,y)=1]=dx,dyμ(d)[\gcd(x,y)=1]=\sum_{d|x,d|y}\mu(d)

  • 组合恒等式

    • 组合递推式:

(nk)=(n1k1)+(n1k)\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}

    • 不知名恒等式:

(nm)(mk)=(nk)(nkmk)\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}

Proof

(nm)(mk)=n!m!m!(nm)!k!(mk)!=n!(nk)!(nm)!k!(mk)!(nk)!=(nk)(nkmk)\binom{n}{m}\binom{m}{k}=\frac{n!m!}{m!(n-m)!k!(m-k)!}=\frac{n!(n-k)!}{(n-m)!k!(m-k)!(n-k)!}=\binom{n}{k}\binom{n-k}{m-k}

    • 二项式定理:

i=0n(ni)xiyni=(x+y)n\sum_{i=0}^n\binom{n}{i}x^iy^{n-i}=(x+y)^n

    • 不知名恒等式(2):

kn(m+kk)=(m+n+1n)\sum_{k\le n}\binom{m+k}{k}=\binom{m+n+1}{n}

Proof

kn(m+kk)=(m0)+(m+11)+(m+22)++(m+nn)=(m+10)+(m+11)+(m+22)++(m+nn)=(m+21)+(m+22)++(m+nn)==(m+nn1)+(m+nn)=(m+n+1n)\begin{aligned} &\sum_{k\le n}\binom{m+k}{k}\\ =&\binom{m}{0}+\binom{m+1}{1}+\binom{m+2}{2}+\dots+\binom{m+n}{n}\\ =&\binom{m+1}{0}+\binom{m+1}{1}+\binom{m+2}{2}+\dots+\binom{m+n}{n}\\ =&\binom{m+2}{1}+\binom{m+2}{2}+\dots+\binom{m+n}{n}\\ =&\dots\\ =&\binom{m+n}{n-1}+\binom{m+n}{n}\\ =&\binom{m+n+1}{n} \end{aligned}

    • 不知名恒等式(3):

0kn(km)=(n+1m+1)\sum_{0\le k\le n}\binom{k}{m}=\binom{n+1}{m+1}

Proof

(n+1m+1)=(nm)+(nm+1)=(nm)+(n1m)+(n1m+1)==(1kn(km))+(0m+1)=0kn(km)\begin{aligned} &\binom{n+1}{m+1}\\ =&\binom{n}{m}+\binom{n}{m+1}\\ =&\binom{n}{m}+\binom{n-1}{m}+\binom{n-1}{m+1}\\ =&\dots\\ =&\left(\sum_{1\le k\le n}\binom{k}{m}\right)+\binom{0}{m+1}\\ =&\sum_{0\le k\le n}\binom{k}{m} \end{aligned}

    • 范德蒙德卷积

k=0n(rk)(snk)=(r+sn)\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}

Proof

直接考虑组合意义,假设有 rr 个黑球与 ss 个白球,一共要选 nn 个球,前者相当于枚举了选择了几个黑球。

Powered by Hexo, theme by Facter