Theorem 1: Let a(n) be the number of lattice walks from

                                 (0,0) to (n,n)

                     using the following Fundamental Steps:

                       {[0, 0, 1], [0, 1, 0], [1, 0, 0]}

             By the way, the first few terms (starting at n=1), are

[6, 90, 1680, 34650, 756756, 17153136, 399072960, 9465511770, 227873431500,

    5550996791340]

                a(n) satisfies the following linear recurrence:

                    3 (3 n + 2) (3 n + 1) a(n)
                  - -------------------------- + a(n + 1) = 0
                                    2
                             (n + 1)

                                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:

                                   n /     2      2       14   \
                0.27566444771090 27  |1 - --- + ----- + -------|
                                     |    9 n       2         3|
                                     \          81 n    2187 n /
                ------------------------------------------------
                                       n

And in pure floating-point,

                    n /     0.2222222222   0.02469135802   0.006401463192\
    0.2756644477 27.  |1. - ------------ + ------------- + --------------|
                      |          n               2                3      |
                      \                         n                n       /
    ----------------------------------------------------------------------
                                      n

                          ----------------------------

            Theorem 2: Let b(n) be the number of lattice walks from

                                 (0,0) to (n,n)

                     using the following Fundamental Steps:

                       {[0, 0, 1], [0, 1, 0], [1, 0, 0]}

               Staying in the region m>=n>0 (i.e. ballot walks).

             By the way, the first few terms (starting at n=1), are

     [1, 5, 42, 462, 6006, 87516, 1385670, 23371634, 414315330, 7646001090]

                b(n) satisfies the following linear recurrence

                    3 (3 n + 2) (3 n + 1) b(n)
                  - -------------------------- + b(n + 1) = 0
                         (n + 3) (n + 2)

                    Skecth of proof: Analogous to the above.



      This implies, via the Birkhoff-Trijinski-Proincare method, that the

                         the  asymptotics of b(n) is:

                                n /    38     965     62410 \
                  0.551328895 27  |1 - --- + ----- - -------|
                                  |    9 n       2         3|
                                  \          81 n    2187 n /
                  -------------------------------------------
                                       4
                                      n

And in floating-point,

                   n /     4.222222222   11.91358025   28.53680841\
    0.551328895 27.  |1. - ----------- + ----------- - -----------|
                     |          n             2             3     |
                     \                       n             n      /
    ---------------------------------------------------------------
                                   4
                                  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:

                             1.999999999      1
                             ----------- + O(----)
                                  3            4
                                 n            n

                          ----------------------------

        Just as a check, the last 10 terms of the sequence of ratios of

                 the probabilities to the above asymptotics is:

[0.9959748476, 0.9959788940, 0.9959829324, 0.9959869627, 0.9959909846,

    0.9959949986, 0.9959990046, 0.9960030027, 0.9960069925, 0.9960109745]

                   as you can see, they are pretty close to 1

                          ----------------------------

               The whole thing took , 9.988, seconds of CPU time.