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

Home > Numbers
So many ways.... (Posted on 2013-03-21) Difficulty: 3 of 5
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.)
re: solution Comment 3 of 3 |
(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(1)(21,n) = 2n + 1


cP(1)(21,n) = (2n+1)
Centered square gnomom (1-orthoplex) numbers:
{1,3,5,7,9,11,13,...}

cP(2)(22,n) = 2n(n+1)+1
Centered square (2-orthoplex) Tetragonal numbers:
{1,5,13,25,41,61,85,...}

cP(3)(23,n) = (2n+1)(2n2+2n+3)/3
Centered octahedral (3-orthoplex) Octahedral numbers:
{1,7,25,63,129,231,377,...}

cP(4)(24,n) = (3+8n+10n2+4n3+2n4)/3
Centered tetracross (4-orthoplex) numbers:
{1,9,41,129,321,681,1280,...}

cP(5)(25,n) = (15+46n+50n2+40n3+10n4+4n5)/15
Centered pentacross (5-orthoplex) numbers: 
{1,11,61,231,681,1683,3653,...}

cP(6)(26,n) =(45+138n+196n2+120n3+70n4+12n5+4n6)/45
Centered hexacross (6-orthoplex) numbers:
{1,13,85,377,1289,3653,8989,...}


  Posted by Dej Mar on 2013-03-22 06:06:00
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information