login
A129703
Number of different walks generated by n steps that can only go in {east, southeast, southwest} directions on the 300-degree wedge in a 60-degree equilateral triangular lattice.
0
1, 3, 6, 14, 36, 97, 268, 751, 2124, 6047, 17304, 49722, 143366, 414585, 1201918, 3492118, 10165780, 29643871, 86574832, 253188112, 741365050, 2173243129, 6377181826, 18730782253, 55062586342, 161995031227, 476941691178
OFFSET
0,2
COMMENTS
For n > 0, a(n)-1 is the sum of the n-th row of Motzkin's triangle (A026300). - Daniel Suteu, Feb 23 2018
FORMULA
Recurrence: {a(3) = 14, a(4) = 36, a(1) = 3, a(2) = 6, a(0) = 1, (-3-3*n)*a(n)+(-6-2*n)*a(1+n)+(3+n)*a(n+2)+6+4*n}.
G.f.: ((1/2)*i)*sqrt(t+1)/(t*sqrt(3*t-1))-(1/2)*(t+1)*(-1+2*t)/((t-1)*t).
a(n) = 1 + Sum_{k=0..n} Sum_{t=0..floor(k/2)} binomial(n, 2*t + n - k) * (binomial(2*t + n - k, t) - binomial(2*t + n - k, t-1)), for n > 0. - Daniel Suteu, Feb 23 2018
EXAMPLE
a(1) = 3 because all three directions are permissible from the origin;
a(2) = 6 because all three directions are permissible following the southwestern step and the southwest as well as southeast steps are permissible following the southeastern step, but only the eastern step is permissible following one step east.
CROSSREFS
Sequence in context: A332362 A196479 A147772 * A001550 A197461 A100446
KEYWORD
nonn,walk
AUTHOR
Rebecca Xiaoxi Nie (rebecca.nie(AT)utoronto.ca), Jun 01 2007
STATUS
approved