All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 So many ways.... (Posted on 2013-03-21)
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)=...

 See The Solution Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Some short answers | Comment 1 of 3
There are a few ways of stating a recurrence.

The simplest to me is D(a,b)=D(a,b-1)+D(a-1,b)+D(a-1,b-1)
From which it is simple to extend a row if you have the previous row.
I worked my way out to (6,6) as suggested.  Rather than list them all I'll note D(6,6)=8989

Also D(a,b) is a degree b polynomial in a (and visa versa)
D(n,0)=1
D(n,1)=2n+1
D(n,2)=2n^2+2n+1
D(n,3)=(4n^3+6n^2+8n+3)/3
D(n,4)=(2n^4+4n^3+10n^2+8n+3)/3

 Posted by Jer on 2013-03-21 14:55:59

 Search: Search body:
Forums (0)