A151374 Number of walks within N^2 (the first quadrant of Z^2) starting at (0, 0), ending on the vertical axis and consisting of 2n steps taken from {(-1, -1), (-1, 0), (1, 1)}.

1, 2, 8, 40, 224, 1344, 8448, 54912, 366080, 2489344, 17199104, 120393728, 852017152, 6085836800, 43818024960, 317680680960, 2317200261120, 16992801914880, 125210119372800, 926554883358720, 6882979133521920, 51309480813527040, 383705682605506560, 2877792619541299200

Offset: 0

Author

Manuel Kauers, Nov 18 2008

Keywords

• nonn
• walk

Comments

A052701 shifted one place left. - R. J. Mathar, Dec 13 2008

Expansion of c(2*x), where c(x) is the g.f. of A000108. - Philippe Deléham, Feb 26 2009; simplified by Alexander Burstein, Jul 31 2018

From Joerg Arndt, Oct 22 2012: (Start)

Also the number of strings of length 2*n of two different types of balanced parentheses.

For example, a(1) = 2, since the two possible strings of length 2 are [] and (), a(2) = 8, since the 8 possible strings of length 4 are (()), [()], ([]), [[]], ()(), [](), ()[], and [][].

The number of strings of length 2*n of t different types of balanced parentheses is given by t^n * A000108(n): there are n opening parentheses in the strings, giving t^n choices for the type (the closing parentheses are chosen to match). (End)

Number of Dyck paths of length 2n in which the step U=(1,1) come in 2 colors. - José Luis Ramírez Ramírez, Jan 31 2013

Row sums of triangle in A085880. - Philippe Deléham, Nov 15 2013

Hankel transform is 2^(n+n^2) = A053763(n+1). - Philippe Deléham, Nov 15 2013

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.
• Paul Barry, Riordan arrays, the A-matrix, and Somos 4 sequences, arXiv:1912.01126 [math.CO], 2019.
• Mireille Bousquet-Mélou and Marni Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008-2009.
• J. Bouttier, P. Di Francesco and E. Guitter, Statistics of planar graphs viewed from a vertex: a study via labeled trees, Nucl. Phys. B, Vol. 675, No. 3 (2003), pp. 631-660. See p. 631, eq. (3.3).
• Marek Bożejko, Maciej Dołęga, Wiktor Ejsmont and Światosław R. Gal, Reflection length with two parameters in the asymptotic representation theory of type B/C and applications, arXiv:2104.14530 [math.RT], 2021.
• Vedran Čačić and Vjekoslav Kovač, On the fraction of IL formulas that have normal forms, arXiv:1309.3408 [math.LO], 2013.
• Stefano Capparelli and Alberto Del Fra, Dyck Paths, Motzkin Paths, and the Binomial Transform, Journal of Integer Sequences, Vol. 18 (2015), Article 15.8.5.
• Grégory Chatel and Vincent Pilaud, Cambrian Hopf algebras, Adv. Math. 311, 598-633 (2017). Prop. 3.
• Zhi Chen and Hao Pan, Identities involving weighted Catalan-Schröder and Motzkin Paths, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=b=2.
• Nicolas Crampe, Julien Gaboriaud and Luc Vinet, Racah algebras, the centralizer Z_n(sl_2) and its Hilbert-Poincaré series, arXiv:2105.01086 [math.RT], 2021.
• Hsien-Kuei Hwang, Mihyun Kang and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
• Bradley Robert Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
• Georg Muntingh, Implicit Divided Differences, Little Schröder Numbers and Catalan Numbers, J. Int. Seq., Vol. 15 (2012), Article 12.6.5; arXiv preprint, arXiv:1204.2709 [math.CO], 2012.
• L. Poulain d'Andecy, Centralisers and Hecke algebras in Representation Theory, with applications to Knots and Physics, arXiv:2304.00850 [math.RT], 2023. See p. 64.

Crossrefs

Cf. A000108, A046521, A052701, A053763, A085880.

Programs

Magma

[2^n * Catalan(n): n in [0..25]]; // Vincenzo Librandi, Oct 24 2012

Maple

A151374_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := 2*(a[w-1]+add(a[j]*a[w-j-1],j=1..w-1)) od;
convert(a,list)end: A151374_list(23); # Peter Luschny, May 19 2011

Mathematica

aux[i_Integer, j_Integer, n_Integer] := Which[Min[i, j, n] < 0 || Max[i, j] > n, 0, n == 0, KroneckerDelta[i, j, n], True, aux[i, j, n] = aux[-1 + i, -1 + j, -1 + n] + aux[1 + i, j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[Sum[aux[0, k, 2 n], {k, 0, 2 n}], {n, 0, 25}]

PARI

my(x='x+O('x^66)); Vec(sqrt(2-8*x-2*sqrt(1-8*x))/(4*x)) \\ Joerg Arndt, May 11 2013

Sage

def A151374():
    a, n = 1, 1
    while True:
        yield a
        n += 1
        a = a * (8*n - 12) // n
A = A151374()
print([next(A) for  in range(24)]) # _Peter Luschny, Nov 30 2016

Formula

a(n) = 2^n * A000108(n). - Philippe Deléham, Feb 01 2009

From Gary W. Adamson, Jul 12 2011: (Start)

a(n) is the top left term in M^n, M = the following infinite square production matrix:

2, 2, 0, 0, 0, 0, ...

2, 2, 2, 0, 0, 0, ...

2, 2, 2, 2, 0, 0, ...

2, 2, 2, 2, 2, 0, ...

2, 2, 2, 2, 2, 2, ...

...

(End)

E.g.f.: KummerM(1/2, 2, 8*x). - Peter Luschny, Aug 26 2012

From Sergei N. Gladkovskii, Apr 05 2013: (Start)

E.g.f.: Let F(x)=Sum_{n>=0} a(n)*x^n/(2*n)!, then F(x) = E(0)/(1-sqrt(x)) where E(k) = 1 - sqrt(x)/(1 - sqrt(x)/(sqrt(x) - (k+1)*(k+2)/2/E(k+1) )); (continued fraction ).

G.f.: 1 + 4*x/(G(0)-4*x) where G(k) = k*(8*x+1) + 4*x + 2 - 2*x*(2*k+3)*(2*k+4)/G(k+1); (continued fraction). (End)

G.f.: sqrt(2-8*x-2*sqrt(1-8*x))/(4*x). - Mark van Hoeij, May 10 2013

G.f.: (1-sqrt(1-8*x))/(4*x). - Philippe Deléham, Nov 15 2013

D-finite with recurrence (n+1)*a(n) + 4*(-2*n+1)*a(n-1) = 0. - R. J. Mathar, Mar 05 2014

a(n) = 4^n*2F1((1-n)/2,-n/2;1;1)/(n+1). - Benedict W. J. Irwin, Jul 12 2016

a(n) ~ 8^n*n^(-3/2)/sqrt(Pi). - Ilya Gutkovskiy, Jul 12 2016

From Peter Bala, Aug 17 2021: (Start)

a(n) = Sum_{k = 0..floor(n/2)} A046521(n,2*k)*Catalan(2*k).

G.f.: A(x) = 1/sqrt(1 - 4*x)*e(x/(1 - 4*x)), where e(x) = (c(x) + c(-x))/2 is the even part of the function c(x) = (1 - sqrt(1 - 4*x))/(2*x), the g.f. of the Catalan numbers A000108. Inversely, (c(x) + c(-x))/2 = 1/sqrt(1 + 4*x)*A(x/(1 + 4*x)).

x*A(x) = Series reversion of (x - 2*x^2). (End)

Sum_{n>=0} 1/a(n) = 68/49 + 96*arctan(1/sqrt(7)) / (49*sqrt(7)). - Vaclav Kotesovec, Nov 23 2021

Sum_{n>=0} (-1)^n/a(n) = 20/27 - 16*log(2)/81. - Amiram Eldar, Jan 25 2022

G.f.: 1/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-2*x/(1-...))))))))) (continued fraction). - Nikolaos Pantelidis, Nov 20 2022

a(n) = 2*Sum_{k=1..n} a(k-1)*a(n-k), a(0) = 1. - Mehdi Naima, Jan 16 2023