Delannoy Number

前言

一个挺有趣的数,做题遇到了,在此mark一下。


定义

定义$D(n,m)$表示在一个$n\times m$的网格图上,每次向右/左/右上走,从$(0,0)$到达$(n,m)$的方案数。

公式

首先有一个很显然的式子就是$$D(n,m)=\sum_{k=0}^{\min(n,m)}{n+m-k\choose n}{n\choose k}$$
然后还有一个十分优美的对称的式子是$$D(n,m)=\sum_{k=0}^{\min(n,m)}{n\choose k}{m\choose k}2^k$$

推导

我们假定所有的右上都是由$\rightarrow\uparrow$走出来的。
考虑只有向右和向上两种走法,假设其中有$i$个相邻的$\rightarrow\uparrow$的组合(注意必须$\rightarrow$在前),那么就有${n\choose i}{m\choose i}$种$\rightarrow$与$\uparrow$匹配的可能性。
注意到一旦我们确定了匹配的方案,在开头结尾以及$\rightarrow\uparrow$组合之间的空隙里,我们只能是填上一系列$\uparrow$加上一系列$\rightarrow$,不然就会产生新的$\rightarrow\uparrow$组合,也就说剩下的填法是唯一确定的。
然后这$i$个$\rightarrow\uparrow$组合,我们可以选择是否将其变成右上的走法,于是就会产生$2^i$的系数。
因此最终的方案数就是$$D(n,m)=\sum_{k=0}^{\min(n,m)}{n\choose k}{m\choose k}2^k$$

题目

2017计蒜之道复赛E - 商汤智能机器人

参考资料

Wikipedia - Delannoy number
MATHEMATICS
OEIS - A008288