login
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)}.
29

%I #174 Apr 06 2023 02:35:24

%S 1,2,8,40,224,1344,8448,54912,366080,2489344,17199104,120393728,

%T 852017152,6085836800,43818024960,317680680960,2317200261120,

%U 16992801914880,125210119372800,926554883358720,6882979133521920,51309480813527040,383705682605506560,2877792619541299200

%N 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)}.

%C A052701 shifted one place left. - _R. J. Mathar_, Dec 13 2008

%C 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

%C From _Joerg Arndt_, Oct 22 2012: (Start)

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

%C 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 [][].

%C 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)

%C 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

%C Row sums of triangle in A085880. - _Philippe Deléham_, Nov 15 2013

%C Hankel transform is 2^(n+n^2) = A053763(n+1). - _Philippe Deléham_, Nov 15 2013

%H Vincenzo Librandi, <a href="/A151374/b151374.txt">Table of n, a(n) for n = 0..200</a>

%H Paul Barry, <a href="https://arxiv.org/abs/1803.10297">Generalized Eulerian Triangles and Some Special Production Matrices</a>, arXiv:1803.10297 [math.CO], 2018.

%H Paul Barry, <a href="https://arxiv.org/abs/1912.01126">Riordan arrays, the A-matrix, and Somos 4 sequences</a>, arXiv:1912.01126 [math.CO], 2019.

%H Mireille Bousquet-Mélou and Marni Mishna, <a href="http://arxiv.org/abs/0810.4387">Walks with small steps in the quarter plane</a>, arXiv:0810.4387 [math.CO], 2008-2009.

%H J. Bouttier, P. Di Francesco and E. Guitter, <a href="http://dx.doi.org/10.1016/j.nuclphysb.2003.09.046">Statistics of planar graphs viewed from a vertex: a study via labeled trees</a>, Nucl. Phys. B, Vol. 675, No. 3 (2003), pp. 631-660. See p. 631, eq. (3.3).

%H Marek Bożejko, Maciej Dołęga, Wiktor Ejsmont and Światosław R. Gal, <a href="https://arxiv.org/abs/2104.14530">Reflection length with two parameters in the asymptotic representation theory of type B/C and applications</a>, arXiv:2104.14530 [math.RT], 2021.

%H Vedran Čačić and Vjekoslav Kovač, <a href="http://arxiv.org/abs/1309.3408">On the fraction of IL formulas that have normal forms</a>, arXiv:1309.3408 [math.LO], 2013.

%H Stefano Capparelli and Alberto Del Fra, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Capparelli/cap3.html">Dyck Paths, Motzkin Paths, and the Binomial Transform</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.8.5.

%H Chatel, Grégory; Pilaud, Vincent <a href="https://doi.org/10.1016/j.aim.2017.02.027">Cambrian Hopf algebras.</a> Adv. Math. 311, 598-633 (2017). Prop. 3.

%H Zhi Chen and Hao Pan, <a href="http://arxiv.org/abs/1608.02448">Identities involving weighted Catalan-Schröder and Motzkin Paths</a>, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=b=2.

%H Nicolas Crampe, Julien Gaboriaud and Luc Vinet, <a href="https://arxiv.org/abs/2105.01086">Racah algebras, the centralizer Z_n(sl_2) and its Hilbert-Poincaré series</a>, arXiv:2105.01086 [math.RT], 2021.

%H Hsien-Kuei Hwang, Mihyun Kang and Guan-Huei Duh, <a href="https://doi.org/10.4230/LIPIcs.AofA.2018.29">Asymptotic Expansions for Sub-Critical Lagrangean Forms</a>, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.

%H Bradley Robert Jones, <a href="http://summit.sfu.ca/item/14554">On tree hook length formulas, Feynman rules and B-series</a>, Master's thesis, Simon Fraser University, 2014.

%H Georg Muntingh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Muntingh/muntingh2.html">Implicit Divided Differences, Little Schröder Numbers and Catalan Numbers</a>, J. Int. Seq., Vol. 15 (2012), Article 12.6.5; <a href="http://arxiv.org/abs/1204.2709">arXiv preprint</a>, arXiv:1204.2709 [math.CO], 2012.

%H L. Poulain d'Andecy, <a href="https://arxiv.org/abs/2304.00850">Centralisers and Hecke algebras in Representation Theory, with applications to Knots and Physics</a>, arXiv:2304.00850 [math.RT], 2023. See p. 64.

%F a(n) = 2^n * A000108(n). - _Philippe Deléham_, Feb 01 2009

%F From _Gary W. Adamson_, Jul 12 2011: (Start)

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

%F 2, 2, 0, 0, 0, 0, ...

%F 2, 2, 2, 0, 0, 0, ...

%F 2, 2, 2, 2, 0, 0, ...

%F 2, 2, 2, 2, 2, 0, ...

%F 2, 2, 2, 2, 2, 2, ...

%F ...

%F (End)

%F E.g.f.: KummerM(1/2, 2, 8*x). - _Peter Luschny_, Aug 26 2012

%F 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 ). - _Sergei N. Gladkovskii_, Apr 05 2013

%F 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). - _Sergei N. Gladkovskii_, Apr 05 2013

%F G.f.: sqrt(2-8*x-2*sqrt(1-8*x))/(4*x). - _Mark van Hoeij_, May 10 2013

%F G.f.: (1-sqrt(1-8*x))/(4*x). - _Philippe Deléham_, Nov 15 2013

%F D-finite with recurrence (n+1)*a(n) + 4*(-2*n+1)*a(n-1) = 0. - _R. J. Mathar_, Mar 05 2014

%F a(n) = 4^n*2F1((1-n)/2,-n/2;1;1)/(n+1). - _Benedict W. J. Irwin_, Jul 12 2016

%F a(n) ~ 8^n*n^(-3/2)/sqrt(Pi). - _Ilya Gutkovskiy_, Jul 12 2016

%F From _Peter Bala_, Aug 17 2021: (Start)

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

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

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

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

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

%F 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

%F a(n) = 2*Sum_{k=1..n} a(k-1)*a(n-k), a(0) = 1. - _Mehdi Naima_, Jan 16 2023

%p A151374_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;

%p 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;

%p convert(a,list)end: A151374_list(23); # _Peter Luschny_, May 19 2011

%t 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}]

%o (Magma) [2^n * Catalan(n): n in [0..25]]; // _Vincenzo Librandi_, Oct 24 2012

%o (PARI) x='x+O('x^66); Vec(sqrt(2-8*x-2*sqrt(1-8*x))/(4*x)) \\ _Joerg Arndt_, May 11 2013

%o (Sage)

%o def A151374():

%o a, n = 1, 1

%o while True:

%o yield a

%o n += 1

%o a = a * (8*n - 12) // n

%o A = A151374()

%o print([next(A) for _ in range(24)]) # _Peter Luschny_, Nov 30 2016

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

%K nonn,walk

%O 0,2

%A _Manuel Kauers_, Nov 18 2008