|
%I #28 Apr 21 2023 12:47:26
%S 1,0,2,3,6,20,35,105,238,588,1512,3630,9339,23166,58487,148148,373230,
%T 949416,2406248,6122142,15591856,39729000,101432982,259049230,
%U 662421643,1695149220,4341026900,11125755615,28530984915,73213888650,187980163110,482906682675
%N Consider asymmetric 1-D random walk with set of possible jumps {-1,+1,+2}. Sequence gives number of paths of length n ending at origin.
%C It appears that a(n) is the coefficient of x^n in the expansion (1+x^2+x^3)^n. - _Joerg Arndt_, Jul 01 2011 [For the proof see the formula section. - _Wolfdieter Lang_, Nov 05 2018]
%F a(n) = Sum_{k=floor((n+2)/3)..floor(n/2)} binomial(n,k)*binomial(k,3*k-n).
%F G.f. g(x) satisfies (31*x^3 + 18*x^2 - x - 4)*g(x)^3 + (x+3)*g(x) + 1 = 0.
%F Recurrence: 2*n*(2*n-1)*(52*n-79)*a(n) + (n-1)*(52*n^2-79*n+36)*a(n-1) - 6*(n-1)*(156*n^2-315*n+106)*a(n-2) - 31*(n-1)*(n-2)*(52*n-27)*a(n-3) = 0.
%F a(n) ~ c * d^n / sqrt(Pi*n), where d = 2.61071861327603934981864900838405862... is the root of the equation -31 - 18*d + d^2 + 4*d^3 = 0 and c = 0.57803237802255683003114674597591616... is the root of the equation -31 + 324*c^2 - 1248*c^4 + 1664*c^6 = 0. - _Vaclav Kotesovec_, Mar 01 2016
%F From _Wolfdieter Lang_, Nov 05 2018: (Start)
%F G.f. G(x) = x*(d/dx)log(F^{[-1]}) = f(x)/(1 - (x*f(x))^2 - 2*(x*f(x))^3) = f(x)/(3 - 2*f(x) + (x*f(x))^2), where f(x) = F^{[-1]}(x)/x, and F^{[-1]})(x) is the compositional inverse of F(y) = x/(1 + x^2 + x^3); that is, F(F^{[-1]}(x)) = x, identically. This G can be proved to solve the equation given above for the g.f. g, if one applies the identity for f (as done above in the last formula for G): (x*f(x))^3 + (x*f(x))*2 - f(x) + 1 = 0 (following from the equation for F^{[-1]}). The expansion of f is given in A001005.
%F The g.f. G(x) can be computed from the general Lagrange series for the function h(t) with derivative h(t)" = 1/phi(t), where phi(t) = (1 + t^2 + t^3), and the inversion of x = y/phi(y) = F(y). Then one finds G(x) = (d/dx)h(F^{[-1]}(x)) = (1/phi(F^{[-1]}(x)))*(d/dx)F^{[-1]}(x), which becomes with the above mentioned identity for f(x) = F^{[-1]}(x)/x the result G(x) = f(x)/(3 - 2*f(x) + (x*f(x))^2).
%F From this special Lagrange series derivation and the proof that the g.f. g from above coincides with G, the conjecture, given by _Joerg Arndt_ as a comment above, has been proved. This uses [t^n]phi(t)^n = (1/n!)*(d/dt)^n phi(t)^n, evaluated at t = 0, which appears in the considered Lagrange series.
%F a(n) = Sum_{2*e + 3*e3 = n} n!/((n - (e2+e3))!*e2!*e3!), n >= 2, with a(0) = 1 and a(1) = 0. This is the row sum of the irregular table A321203 of these multinomial numbers for the solutions for the pairs (e2, e3). The pairs of solutions are given in A321201.
%F (End)
%e a(3) = 3: (+2-1-1) or (-1+2-1) or (-1-1+2).
%e From _Wolfdieter Lang_, Nov 05 2018: (Start)
%e a(8) = (1/8!)*(d/dt)^8 (1 + t^2 + t^3)^8 becomes for t = 0: 238. (See the comment with the conjecture by _Joerg Arndt_, now proved.)
%e a(8) = 168 + 70 = 238, the row sum of row n = 8 of A321203, arising from the two [e2, e3] pairs [1, 2] and [4, 0], given in row n = 8 of A321201.
%e (End)
%p a:=n->add(binomial(n,k)*binomial(k,3*k-n),k=floor((n+2)/3)..floor(n/2));
%t Table[Sum[Binomial[n, k]*Binomial[k, 3*k-n], {k, Floor[(n+2)/3], Floor[n/2]}], {n, 0, 30}] (* _Vaclav Kotesovec_, Mar 01 2016 *)
%Y Cf. A001005, A321201, A321203.
%K nonn,easy
%O 0,3
%A _Sergey Perepechko_, Apr 26 2010
|
