\[S(r, c) = \sum_{i=0}^r \sum_{j=0}^c f(i, j)\]

とおくと, 求める値は

\[S(r_2, c_2) - S(r_1-1, c_2) - S(r_2, c_1-1) + S(r_1-1, c_1-1)\]

となる. あとは \(S(r, c)\) をどう効率よく求めるかである.

ここで,

\[f(r + 1, c) = f(r, 0) + f(r, 1) + \cdots + f(r, c)\]

である. \(f(r + 1, c)\) に到達するには道 \((r, i)\) 〜 \((r + 1, i)\) のどれかを通る. \(i\) 番目の道を通る組み合わせの数は \(f(r, i)\) にたどりつく組み合わせの数に等しいので, 上の式が成り立つことが分かる.

よって,

\[S(r, c) = f(1, c) + f(2, c) + \cdots + f(r+1, c)\]

となる.

\[f(r, c + 1) = f(0, c) + f(1, c) + \cdots + f(r, c)\]

が同様に成り立つので,

\[S(r, c) = f(r+1, c+1) - f(0, c) = f(r+1, c+1) - 1\]

となる. なお, 当然ながら

\[f(r, c) = \combi{r+c}{c}\]

である.