A191354 Number of lattice paths from (0,0) to (n,n) using steps (1,0), (1,1), (1,2), and (2,1).

1, 1, 3, 9, 25, 75, 227, 693, 2139, 6645, 20757, 65139, 205189, 648427, 2054775, 6526841, 20775357, 66251247, 211617131, 676930325, 2168252571, 6953348149, 22322825865, 71735559255, 230735316795, 742773456825, 2392949225565, 7714727440755, 24888317247705, 80341227688095

Offset

0,3

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.

Formula

G.f.: 1/sqrt(1-2*x-3*x^2-4*x^3). - Mark van Hoeij, Apr 16 2013

G.f.: Q(0), where Q(k) = 1 + x*(2+3*x+4*x^2)*(4*k+1)/( 4*k+2 - x*(2+3*x+4*x^2)*(4*k+2)*(4*k+3)/(x*(2+3*x+4*x^2)*(4*k+3) + 4*(k+1)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 14 2013

a(n) = Sum_{k=0..n} (binomial(2*k,k) * Sum_{j=0..k} (binomial(j,n-k-j) *binomial(k,j)*2^(j-k)*3^(-n+k+2*j)*4^(n-k-2*j))). - Vladimir Kruchinin, Feb 27 2016

D-finite with recurrence: +(n)*a(n) +(-2*n+1)*a(n-1) +3*(-n+1)*a(n-2) +2*(-2*n+3)*a(n-3)=0. - R. J. Mathar, Jan 14 2020

Mathematica

a[n_]:= Sum[Binomial[2k, k]*Sum[Binomial[j, n-k-j]*Binomial[k, j]*2^(j-k) *3^(-n+k+2j)*4^(n-k-2j), {j, 0, k}], {k, 0, n}];
Array[a, 30, 0] (* Jean-François Alcover, Jul 21 2018, after Vladimir Kruchinin *)
CoefficientList[Series[1/Sqrt[1-2*x-3*x^2-4*x^3], {x, 0, 30}], x] (* G. C. Greubel, Feb 18 2019 *)

Prog

(PARI) /* same as in A092566 but use */
steps=[[1, 0], [1, 1], [1, 2], [2, 1]];
/* Joerg Arndt, Jun 30 2011 */
(PARI) my(x='x+O('x^30)); Vec(1/sqrt(1-2*x-3*x^2-4*x^3)) \\ G. C. Greubel, Feb 18 2019
(Maxima)
a(n):=sum(binomial(2*k, k) * sum(binomial(j, n-k-j) * 2^(j-k) * binomial(k, j) * 3^(-n+k+2*j) * 4^(n-k-2*j), j, 0, k), k, 0, n); /* Vladimir Kruchinin, Feb 27 2016 */
(Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!( 1/Sqrt(1-2*x-3*x^2-4*x^3) )); // G. C. Greubel, Feb 18 2019
(Sage) (1/sqrt(1-2*x-3*x^2-4*x^3)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Feb 18 2019

Crossrefs

Cf. A001850, A026641, A036355, A137644, A192364, A192365, A192369.

Sequence in context: A244826 A183111 A132835 * A001189 A212352 A198180

Adjacent sequences: A191351 A191352 A191353 * A191355 A191356 A191357

Keyword

nonn

Author

Joerg Arndt, Jun 30 2011

Status

approved