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)=...
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 |
solution
