Theorem 1: Let a(n) be the number of lattice walks from (0,0,0) to (n,n,n) using the following Fundamental Steps: {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1]} By the way, the first few terms (starting at n=1), are [7, 115, 2371, 54091, 1307377, 32803219, 844910395, 22188235867, 591446519797, 15953338537885] a(n) satisfies the following linear recurrence: 2 2 3 (3 n + 8) (n + 1) a(n) (54 + 92 n + 51 n + 9 n ) a(n + 1) - ----------------------- + ----------------------------------- 2 2 (3 n + 5) (n + 3) (3 n + 5) (n + 3) 2 (3 n + 7) (30 n + 130 n + 133) a(n + 2) - ---------------------------------------- + a(n + 3) = 0 2 (3 n + 5) (n + 3) Skecth of proof: Conjecture a linear rerurrence operator with polynomial coeffs. of the form Q(m,n,MN) annihilating F(m,n), the number of walks from the origin to (m,n) Here M and N are the shift operators in the m- and n- variales: Mf(m,n):=f(m+1,n) ; Nf(m,n):=f(m,n+1). Let P(M,N) be the obvious linear partial recurrence operator with constant coeffs. annihilating F(m,n). Note that conjecturing Q(MN,m,n) takes much longer to do, hence we don't want to bother. Next prove the correctness of Q by taking succesive commutators with P Finally set m=n in Q(MN,m,n) and get an ordinary recurrence for the diagonal a(n):=F(n,n). The recurrence implies, via the Birkhoff-Trijinski-Proincare method that the asymptotics of a(n) is: / 1/2 1/3 \n / / |3 (292 + 4 5 ) 66 | | | 0.28520275027276382 |------------------- + ----------------- + 10| |1 + |- 4/9 | 2 1/2 1/3 | \ \ \ (292 + 4 5 ) / 1/2 1/3 1/2 1/3 1/2 1/2 2/3 1/2 7 (292 + 4 5 ) (292 + 4 5 ) 5 (292 + 4 5 ) 5 + ------------------- - ---------------------- + ---------------------- 396 396 2904 1/2 2/3\ / 1/2 1/3 23 (292 + 4 5 ) | | (292 + 4 5 ) + --------------------|/n + |4/27 - ----------------- 8712 / \ 108 1/2 1/3 1/2 1/2 2/3 1/2 (292 + 4 5 ) 5 35 (292 + 4 5 ) 5 + ---------------------- - ------------------------- 324 78408 1/2 2/3\ / 1/2 1/3 1/2 107 (292 + 4 5 ) | / 2 | 47 (292 + 4 5 ) 5 - ---------------------| / n + |- 2/2187 - ------------------------- 78408 / / \ 32076 1/2 1/3 1/2 2/3 1/2 2/3 1/2\ 7 (292 + 4 5 ) 59 (292 + 4 5 ) 155 (292 + 4 5 ) 5 | + ------------------- + -------------------- + --------------------------| 10692 705672 705672 / / 1/2 1/3 1/2 1/3 1/2 / 3 | 64 145 (292 + 4 5 ) 643 (292 + 4 5 ) 5 / n + |- ----- + --------------------- - -------------------------- / \ 19683 866052 866052 1/2 2/3 1/2 2/3 1/2\ \ 335 (292 + 4 5 ) 709 (292 + 4 5 ) 5 | / 4| + --------------------- + --------------------------| / n |/n 19053144 6351048 / / / n And in pure floating-point, 0.2852027503 29.90078669 / 0.2106885107 0.02623893449 0.00732751082 0.00125521179\ |1. - ------------ + ------------- + ------------- - -------------|/n | n 2 3 4 | \ n n n / ---------------------------- Theorem 2: Let b(n) be the number of lattice walks from (0,0,0) to (n,n,n) using the following Fundamental Steps: {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1]} Staying in the region m>=n>0 (i.e. ballot walks). By the way, the first few terms (starting at n=1), are [2, 10, 88, 1043, 14778, 236001, 4107925, 76314975, 1491934038, 30389576308] b(n) satisfies the following linear recurrence 2 (n - 1) (n - 3) (3 n + 8) b(n) (n + 3) (9 n - 3 n - 16) b(n + 1) - ------------------------------ + ---------------------------------- (3 n + 5) (n + 5) (n + 4) (3 n + 5) (n + 5) (n + 4) 2 2 (3 n + 7) (15 n + 65 n + 62) b(n + 2) - ---------------------------------------- + b(n + 3) = 0 (3 n + 5) (n + 5) (n + 4) Skecth of proof: Analogous to the above. This implies, via the Birkhoff-Trijinski-Proincare method, that the the asymptotics of b(n) is: / 1/2 1/3 \n / / |3 (292 + 4 5 ) 66 | | | 0.767112201356 |------------------- + ----------------- + 10| |1 + |14/9 | 2 1/2 1/3 | \ \ \ (292 + 4 5 ) / 1/2 1/3 1/2 1/2 1/3 1/2 2/3 (292 + 4 5 ) 5 41 (292 + 4 5 ) 68 (292 + 4 5 ) + ---------------------- - -------------------- - -------------------- 495 99 1089 1/2 2/3 1/2\ / 1/2 1/3 1/2 (292 + 4 5 ) 5 | |367 14 (292 + 4 5 ) 5 + ----------------------|/n + |--- + ------------------------- 1815 / \27 891 1/2 1/3 1/2 2/3 1/2 1/2 2/3 62 (292 + 4 5 ) 19 (292 + 4 5 ) 5 307 (292 + 4 5 ) - -------------------- - ------------------------- - --------------------- 297 9801 9801 \ / 1/2 1/3 1/2 1/3 1/2 | / 2 |50650 9827 (292 + 4 5 ) 3989 (292 + 4 5 ) 5 | / n + |----- - ---------------------- + --------------------------- / / \2187 2673 40095 1/2 2/3 1/2 1/2 2/3\ / 3268 (292 + 4 5 ) 5 48821 (292 + 4 5 ) | / 3 |2285423 - --------------------------- - -----------------------| / n + |------- 441045 88209 / / \ 19683 1/2 1/3 1/2 1/2 1/3 81998 (292 + 4 5 ) 5 981470 (292 + 4 5 ) + ---------------------------- - ------------------------ 216513 216513 1/2 2/3 1/2 1/2 2/3\ \ 37912 (292 + 4 5 ) 5 1619030 (292 + 4 5 ) | / 4| / 4 - ---------------------------- - -------------------------| / n | / n 793881 2381643 / / / / n And in floating-point, 0.7671122014 29.90078669 / 3.938325641 10.82777137 25.58569284 56.08507274\ / 4 |1. - ----------- + ----------- - ----------- + -----------| / n | n 2 3 4 | / \ n n n / By dividing the asymptotic expression of b(n) by that of a(n) we get the following Corollary: The asymptotics of the probabibility of a walk that winded up at (n,n) staying in m>=n is: 2.689708289 10.02625649 1 ----------- - ----------- + O(----) 3 4 5 n n n ---------------------------- Just as a check, the last 10 terms of the sequence of ratios of the probabilities to the above asymptotics is: [1.000010213, 1.000010193, 1.000010172, 1.000010152, 1.000010131, 1.000010111, 1.000010091, 1.000010070, 1.000010050, 1.000010030] as you can see, they are pretty close to 1 ---------------------------- The whole thing took , 216.550, seconds of CPU time.