login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A176806 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. 3
1, 0, 2, 3, 6, 20, 35, 105, 238, 588, 1512, 3630, 9339, 23166, 58487, 148148, 373230, 949416, 2406248, 6122142, 15591856, 39729000, 101432982, 259049230, 662421643, 1695149220, 4341026900, 11125755615, 28530984915, 73213888650, 187980163110, 482906682675 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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]

LINKS

Table of n, a(n) for n=0..31.

FORMULA

a(n) = Sum_{k=floor((n+2)/3)..floor(n/2)} binomial(n,k)*binomial(k,3*k-n).

G.f. g(x) satisfies (31*x^3 + 18*x^2 - x - 4)*g(x)^3 + (x+3)*g(x) + 1 = 0.

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.

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

From Wolfdieter Lang, Nov 05 2018: (Start)

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.

The g.f. G(x) can been 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).

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.

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.

(End)

EXAMPLE

a(3) = 3: (+2-1-1) or (-1+2-1) or (-1-1+2).

From Wolfdieter Lang, Nov 05 2018: (Start)

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

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.

(End)

MAPLE

a:=n->add(binomial(n, k)*binomial(k, 3*k-n), k=floor((n+2)/3)..floor(n/2));

MATHEMATICA

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 *)

CROSSREFS

Cf. A001005, A321201, A321203.

Sequence in context: A254441 A173744 A227316 * A168268 A277876 A002078

Adjacent sequences:  A176803 A176804 A176805 * A176807 A176808 A176809

KEYWORD

nonn,easy

AUTHOR

Sergey Perepechko, Apr 26 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 13:54 EST 2019. Contains 319271 sequences. (Running on oeis4.)