关于下降幂

本文主要是介绍关于下降幂，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

定义

下降幂就是形如 \(n^{\underline m}\) 的式子，表示

\[n^{\underline m} =\prod_{i=n-m+1}^n i=\frac{n!}{(n-m)!} \]

同理还有一个上升幂：

\[n^{\overline m}=\prod_{i=n}^{n+m-1} i=\frac{(n+m-1)!}{(n-1)!} \]

注意这个地方 \(n,m\) 都可能是负数，也就是 \(n^{\underline {-m}}=n^{\overline m}\)

作用

有个简单的性质：

\[n^{\underline{a+b}}=n^{\underline a}(n-a)^{\underline b}\\ n^{\overline{a+b}}=n^{\overline a}(n+a)^{\overline b} \]

还有上升下降之间的转化：

\[n^{\underline m}=(-1)^m (-n)^{\overline m}\\ n^{\underline m}=(n-m+1)^{\overline m} \]

下降幂可以解决很多与组合数有关的式子。

首先有个简单的，把组合数表示成下降幂形式。

\[\binom{n}{m}=\frac{n!}{m!(n-m)!}=\frac{n^{\underline m}}{m!} \]

这个可以把组合数扩展到实数域，也就是：

\[\binom{r}{n}=\frac{r^{\underline n}}{n!} \]

此处 \(r\) 是任意实数。

然后也满足二项式定理：

\[(x+y)^r=\sum_{i=0} \binom{r}{i}x^iy^{r-i} \]

上指标反转：

\[\binom{n}{m}=\frac{n^{\underline m}}{m!}=\frac{(-1)^m(-n)^{\overline m}}{m!}=(-1)^m\frac{(m-n-1)^{\underline m}}{m!}=(-1)^m \binom{m-n-1}{m} \]

还有下降幂与组合数相乘：

\[\binom{n}{k} k^{\underline i}=\frac{n!}{k!(n-k)!}\frac{k!}{(k-i)!}=\frac{(n-i)!}{(n-k)!(k-i)!}\frac{n!}{(n-i)!}\\=\binom{n-i}{k-i}n^{\underline i} \]

然后有一个很牛的，叫做取一半：

求

\[F(x)=\sum_{n=0} \binom{2n}{n}x^n \]

的封闭形式。

一个神秘的构造是：

\[x^{\underline k}(x-\frac{1}{2})^{\underline k}=\frac{(2x)^{\underline {2k}}}{2^{2k}} \]

证明比较简单，就是前面展开后每项乘 \(2\) 即可。

\[\binom{2n}{n}=\frac{2n^{\underline {2n}}}{(n!)^2}=\frac{n^{\underline n}(n-\frac{1}{2})^{\underline n}4^n}{(n!)^2}=\frac{(n-\frac{1}{2})^{\underline n}4^n}{n!}=4^n\binom{n-\frac{1}{2}}{n} \]

此时把右边的组合数上指标翻转一下：

\[4^n\binom{n-\frac{1}{2}}{n}=(-4)^n \binom{-\frac{1}{2}}{n}\\ F(x)=(-4x)^n \binom{-\frac{1}{2}}{n}=\frac{1}{\sqrt{1-4x}} \]

最后一步是一个简单的二项式定理。

还有一个关于下降幂的二项式定理：

\[(x+y)^{\underline n}=\sum_{i=0}^n \binom{n}{i}x^{\underline i}y^{\underline {n-i}}\\ (x+y)^{\overline n}=\sum_{i=0}^n \binom{n}{i}x^{\overline i}y^{\overline {n-i}} \]

证明比较简单，直接考虑证明第一个，第二个也差不多：

\[\sum_{i=0}^n \binom{n}{i}x^{\underline i}y^{\underline {n-i}}=\sum_{i=0}^n \frac{n!}{i!(n-i)!}x^{\underline i}y^{\underline {n-i}}=n!\sum_{i=0}^n \binom{x}{i} \binom{y}{n-i} \]

考虑后面的组合意义，就是一个范德蒙德卷积，在 \(x+y\) 个球中选 \(n\) 个然后排成一排，当然就和左边的一样了。

\[n!\sum_{i=0}^n \binom{x}{i} \binom{y}{n-i}=n!\binom{x+y}{n}=(x+y)^{\underline n} \]

这篇关于关于下降幂的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！