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.)
 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   nextOKrun    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   nextOKrun  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

 Search: Search body:
Forums (0)