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

Author

Joerg Arndt, Jun 30 2011

Keywords

• nonn

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.

Crossrefs

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

Programs

Magma

m:=30; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!( 1/Sqrt(1-2*x-3*x^2-4*x^3) )); // G. C. Greubel, Feb 18 2019

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

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

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

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

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