第一章
定义超几何函数
\[F(a_1,a_2\dots a_n;b_1,b_2\dots b_m;z)=\sum_{k\ge 0}\frac{a_1^{\overline{k}}\dots a_n^{\overline {k}}z^k}{b_1^{\overline k}\dots b_n^{\overline k}k!}
\]
其中 \(b_i\) 不为非正的整数。
举出若干简单例子:
\[F(1;1;z)=e^z,F(1,1;1;z)=\frac{1}{1-z}
\]
\[F(a,1;1;z)=\sum_k\binom{a+k-1}{k}=\frac{1}{(1-z)^a}
\]
两种特殊的超几何函数(没什么用):
合流超几何函数:
\[F(a;b;z)=\sum_{k\ge 0}\frac{a^{\overline{k}}z^k}{b^{\overline k}k!}
\]
高斯超几何函数:
\[F(a,b;c;z)=\sum_{k\ge 0}\frac{a^{\overline{k}}b^{\overline {k}}z^k}{c^{\overline k}k!}
\]
一般的形式多少有点吓人。现在我们考察如何把一个东西变成超几何形式:
考虑
\[F=\sum_{k\ge 0}t_k,t_k=\frac{a_1^{\overline{k}}\dots a_n^{\overline {k}}z^k}{b_1^{\overline k}\dots b_n^{\overline k}k!}
\]
\[\frac{t_{k+1}}{t_k}=\frac{(k+a_1)\dots (k+a_n)z}{(k+b_1)\dots(k+b_m)(k+1)}
\]
同时 \(t_0=1\)。不为一的话在展开式外面乘上应该的 \(t_0\) 即可。
来试试手:
\[\sum_{k\le n}\binom{r+k}{k}=\binom{r+n+1}{n}
\]
使 \(k\) 最小值为 \(0\),令 \(k=n-k\)。
\[t_k=\frac{(r+n-k)!}{r!(n-k)!},\frac{t_{k+1}}{t_k}=\frac{n-k}{r+n-k}=\frac{(k+1)(k-n)(1)}{(k-r-n)(k+1)}
\]
\[=F(1,-n;-n-r;1)
\]
\[\therefore F(1,-n;-n-r;1)=\frac{r+n+1}{r+1}
\]
在上述过程中,注意到我们没有定义超几何函数在分母阶乘为负数的情况。
但是我们OIer管这么多干什么呢
对于阶乘函数,有两种本质等价的定义方法:
\[\frac{1}{z!}=\lim_{n\to \infin}\binom{n+z}{n}n^{-z}
\]
\[z!=\Gamma(z+1)=\int_{0}^{\infin}t^ze^{-t}\text{d}t,\text{Real}(z)>-1
\]
事实上,对于第二种,可以利用 \(z!=z(z-1)!\) 延拓其定义域。
有余元公式:
\[\Gamma(1-z)\Gamma(z)=(-z)!\Gamma(z)=\frac{\pi}{\sin\pi z}=\frac{\pi}{\sin\pi z}
\]
不难发现,\(z!\) 为 \(0\) 当且仅当 \(z\) 为负整数。
根据范德蒙德卷积,有:
\[\sum_k \binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}
\]
改写为超几何形式有:
\[\binom{s}{n}F(-r,-n;s-n+1;1)=\binom{r+s}{n}
\]
这时,我们发现可以改写 \(r,s,n\)。
于是可以得到高斯超几何函数的通用形式:
\[F(a,b;c;1)=\frac{(c-a-b-1)!(c-1)!}{(c-a-1)!(c-b-1)!}
\]
这里 \(b\) 为非正的整数,或者 \(c>a+b\)(事实上是他们的实部),否则原级数不收敛。
而假设 \(b=-n\),有一个看起来更好的形式:
\[F(a,-n;c;1)=\frac{(c-a)^{\overline n}}{c^{\overline n}}
\]
事实上,这个东西能秒掉很多组合数题。
这里还有一个库莫尔公式:
\[F(a,b;1-a+b;-1)=\frac{(b/2)!}{b!}(b-a)^{\underline{b/2}}
\]
如果愿意记得话,有一个可以由之前某道组合例题推广的Saalschütz公式:
\[F(a,b,-n;c,a+b-n-c+1;1)=\frac{(c-a)^{\overline n}(c-b)^{\overline n}}{(-c)^{\overline n}(c-a-b)^{\overline n}}
\]