Consider all "integer" points in the 1st Quadrant, i.e. North-East part of the coordinates system.
How many lattice paths from (0,0) to (b,a) exist if only east (1,0), north (0,1), and northeast (1,1) steps are allowed?

Provide a general recurrence formula, supported by few samples, say all (a,b) points between (0,0) and (6,6).

What can be said about the numbers thus obtained?
Try to formulate a direct formula for the integer points on the y=x line, i.e. D(m,m)=...

(In reply to solution by Charlie)

The numbers are also appear to be the centered orthoplicial polytopic numbers, and can be given by the recurrence equation:
_cP^(d)(2d,n) = _cP^(d)(2d,n-1)
+ _cP^(d-1)(2(d-1),n)
+ _cP^(d-1)(2(d-1),n-1),
with initial conditions
_cP^(d)(2d,0) = 1
_cP⁽¹⁾(2·1,n) = 2n + 1


_cP⁽¹⁾(2·1,n) = (2n+1)
Centered square gnomom (1-orthoplex) numbers:
{1,3,5,7,9,11,13,...}

_cP⁽²⁾(2·2,n) = 2n(n+1)+1
Centered square (2-orthoplex) Tetragonal numbers:
{1,5,13,25,41,61,85,...}

_cP⁽³⁾(2·3,n) = (2n+1)(2n²+2n+3)/3
Centered octahedral (3-orthoplex) Octahedral numbers:
{1,7,25,63,129,231,377,...}

_cP⁽⁴⁾(2·4,n) = (3+8n+10n²+4n³+2n⁴)/3
Centered tetracross (4-orthoplex) numbers:
{1,9,41,129,321,681,1280,...}

_cP⁽⁵⁾(2·5,n) = (15+46n+50n²+40n³+10n⁴+4n⁵)/15
Centered pentacross (5-orthoplex) numbers: 
{1,11,61,231,681,1683,3653,...}

_cP⁽⁶⁾(2·6,n) =(45+138n+196n²+120n³+70n⁴+12n⁵+4n⁶)/45
Centered hexacross (6-orthoplex) numbers:
{1,13,85,377,1289,3653,8989,...}

Posted by Dej Mar on 2013-03-22 06:06:00