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.)
Solution solution | Comment 2 of 3 |

Designating the destination point as (a,b):

If either a or b is zero, the number of paths is 1.

If neither is zero, the penultimate point on the path is either (a-1,b), (a-1,b-1) or (a,b-1) and these are mutually exclusive possibilities. Thus the number ways to get to (a,b) is the sum of the ways to get to (a-1,b), (a-1,b-1) and (a,b-1).

Following these rules (for a<=b as the table is symmetrical):

     \b 1   2    3     4     5      6      7       8        9       10
    a  
    1   3
    2   5  13
    3   7  25   63
    4   9  41  129   321
    5  11  61  231   681   1683
    6  13  85  377  1289   3653    8989
    7  15 113  575  2241   7183   19825  48639
    8  17 145  833  3649  13073   40081 108545   265729
    9  19 181 1159  5641  22363   75517 224143   598417  1462563
   10  21 221 1561  8361  36365  134245 433905  1256465  3317445  8097453

  
The table being created using:  

DEFDBL A-Z
CLEAR , , 25000
CLS
FOR a = 1 TO 10
 FOR b = 1 TO a
    PRINT USING STRING$(b + 2, "#"); ways(a, b);
 NEXT: PRINT
NEXT

FUNCTION ways (x, y)
IF x = 0 OR y = 0 THEN
    ways = 1
ELSE
    ways = ways(x - 1, y) + ways(x - 1, y - 1) + ways(x, y - 1)
END IF
END FUNCTION

The sequence of D(m,m) is seen as 3, 13, 63, 321, 1683, .... Sloane's OEIS calls it A001850 Central Delannoy numbers: Sum_{k=0..n} C(n,k)*C(n+k,k).

Googling Delannoy numbers finds in Wolfram MathWorld, where you can find the general formula D(n,k) = Sum{d=0 to n}(C(k,d)*C(n+k-d,k)). The following program shows that this is true for k>=n, but when k<n there is an illegal parameter when C(k,d) is sought where d>k:

list
   10   for N=1 to 6
   15   for K=1 to N-1:print "     ";:next
   20   for K=N to 6
   30    Sum=0
   40    for D=0 to N
   50      Sum=Sum+combi(K,D)*combi(N+K-D,K)
   60    next
   70    print using(5,0),Sum;
   80   next:print
   90   next
OK
run
    3    5    7    9   11   13
        13   25   41   61   85
             63  129  231  377
                 321  681 1289
                     1683 3653
                          8989
                         


Since the answers are symmetrical, n and k can be switched before computation.                         

list
   10   for A=1 to 10
   20   for B=1 to 10
   25   if A>B then K=A:N=B:else K=B:N=A
   30    Sum=0
   40    for D=0 to N
   50      Sum=Sum+combi(K,D)*combi(N+K-D,K)
   60    next
   70    print using(B+2,0),Sum;
   80   next:print
   90   next
OK
run
  3   5    7     9     11      13      15      17      19       21
  5  13   25    41     61      85     113     145     181      221
  7  25   63   129    231     377     575     833    1159     1561
  9  41  129   321    681    1289    2241    3649    5641     8361
 11  61  231   681   1683    3653    7183   13073   22363    36365
 13  85  377  1289   3653    8989   19825   40081   75517   134245
 15 113  575  2241   7183   19825   48639  108545  224143   433905
 17 145  833  3649  13073   40081  108545  265729  598417  1256465
 19 181 1159  5641  22363   75517  224143  598417 1462563  3317445
 21 221 1561  8361  36365  134245  433905 1256465 3317445  8097453
 
 

  Posted by Charlie on 2013-03-21 16:11:36
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 (3)
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