The Delannoy numbers: (Minimal paths with diagonal steps) D(n,n) = P_n(3) where P_n is the Legendre polynomial. Recursion: D(p,q) = D(p,q-1) + D(p-1,q) + D(p-1,q-1). GF: Sum_{p,q} D(p,q)*x^p*y^q = 1/(1 - x - y - x*y) Sum_{n} D(n,n)*x^n = 1/sqrt(1 - 6x + x*x) Table D(n,m): 1 1 1 1 1 1 1 1 3 5 7 9 11 13 1 5 13 25 41 61 85 1 7 25 63 129 231 377 1 9 41 129 321 681 1289 1 11 61 231 681 1683 3653 1 13 85 377 1289 3653 8989 Reference: L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, Holland, 1974. Section 1.Supl.21: Minimal paths with diagonal steps, p80-81 Moser & Zayachkowski, Lattice paths with diagonal steps, Scripta Mathematica, 26 (1963) 223-229