Processing math: 100%

嘘~ 正在从服务器偷取页面 . . .

_


范德蒙德卷积公式 (Vandermonde’s Identity)

美观起见,证明在 Part 2


Part 1

范德蒙德卷积公式:

ki=0(ni)(mki)=(n+mk)

推论1:

si=r(nr+i)(msi)=(n+mr+s)

推论2:

ni=1(ni)(ni1)=(2nn1)

推论3:

ni=0(ni)2=(2nn)

推论4:

mi=0(ni)(mi)=(n+mm)

Part 2

范德蒙德卷积公式 证明:

n+mk=0(n+mk)xk=(x+1)n+m=(x+1)n(x+1)m=nr=0(nr)xrms=0(ms)xs=n+mk=0kr=0(nr)(mkr)xk

(n+mk)=kr=0(nr)(mkr)

推论1 证明类似与原公式,这里不再说明。

推论2 证明:

ni=1(ni)(ni1)=n1i=0(ni+1)(ni)=n1i=0(nn1i)(ni)=(2nn1)

推论3 证明:

ni=0(ni)2=ni=0(ni)(nni)=(2nn)

推论4 证明:

mi=0(ni)(mi)=mi=0(ni)(mmi)=(n+mm)

推论4中的 (n+mm) 是我们较为熟悉的网格图路径计数的方案数。所以我们可以考虑其组合意义的证明。

在一张网格图中,从 (0,0) 走到 (n,m) 共走 n+m 步。规定 (0,0) 位于网格图左上角,其中向下走了 n 步,向右走了 m 步,方案数为 (n+mm)

换个视角,我们将 n+m 步拆成两部分走,先走 n 步,再走 m 步,那么 n 步中若有 i 步向右,则 m 步中就有 mi 步向右,故得证。


参考文献

[1] https://oi-wiki.org/math/combinatorics/vandermonde-convolution/


文章作者: q779
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
评论
你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3
  目录