cp's OEIS Frontend

A059435 Number of lattice paths in plane starting at (0,0) and ending at (n,n) with steps from {(i,j): i+j > 0, i, j >= 0} that never go below the line y = x.

%I A059435 #65 Aug 16 2024 23:11:39
%S A059435 1,2,12,88,720,6304,57792,547712,5323008,52761088,531311616,
%T A059435 5420488704,55905767424,581954543616,6106210615296,64513688174592,
%U A059435 685741070942208,7328106153115648,78684992821788672,848487859401261056
%N A059435 Number of lattice paths in plane starting at (0,0) and ending at (n,n) with steps from {(i,j): i+j > 0, i, j >= 0} that never go below the line y = x.
%C A059435 Series reversion of x(1-4x)/(1-2x). - _Paul Barry_, May 19 2005
%C A059435 The Hankel transform of this sequence is 8^C(n+1,2) = [1, 8, 512, 262144, ...]. - _Philippe Deléham_, Nov 08 2007
%D A059435 W.-J. Woan, A bijective proof by induction that the n-th term of this sequence is 2^(n-1) times of the n-th term of the big Schroeder number, 2001 (unpublished).
%H A059435 Vincenzo Librandi, <a href="/A059435/b059435.txt">Table of n, a(n) for n = 0..200</a>
%H A059435 David Callan, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r82/0">A uniformly distributed statistic on a class of lattice paths</a>, Electronic J. Combinatorics, Vol. 11(1), R82, 2004.
%H A059435 Z. Chen and H. Pan, <a href="http://arxiv.org/abs/1608.02448">Identities involving weighted Catalan-Schroder and Motzkin Paths</a>, arXiv:1608.02448 (2016); see Eq. (1.13) with a=2 and b=4.
%H A059435 Ira M. Gessel, <a href="http://dx.doi.org/10.1016/0097-3165(80)90074-6">A factorization for formal Laurent series and lattice path enumeration</a>, J. Combin. Theory Ser. A 28 (1980), 321-337.
%H A059435 Elina Robeva and Melinda Sun, <a href="https://arxiv.org/abs/2007.00877">Bimonotone Subdivisions of Point Configurations in the Plane</a>, arXiv:2007.00877 [math.CO], 2020. See B(2,n) column in Table 3 (p. 10).
%H A059435 Robert A. Sulanke, <a href="https://doi.org/10.37236/1518">Counting lattice paths by Narayana polynomials</a>, Electronic J. Combinatorics 7 (2000), R40.
%F A059435 a(n) = 2^n*A001003(n).
%F A059435 G.f.: (1 + 2*x - sqrt(4*x^2 - 12*x + 1))/(8*x).
%F A059435 From _Paul Barry_, May 19 2005: (Start)
%F A059435 a(n) = (1/(n + 1)) * Sum_{k=0..n} C(n+1, k) * C(2*n-k, n)(-1)^k * 4^(n-k) * 2^k;
%F A059435 a(n) = Sum_{k=0..n} (1/n) * C(n, k) * C(n, k+1) * 4^k * 2^(n-k);
%F A059435 a(n) = Sum_{k=1..n} N(n, k)*2^(n+k-1), for n >= 1, where N(n, k) are the Narayana numbers (A001263). [Corrected by _Alejandro H. Morales_, May 14 2015]
%F A059435 (End)
%F A059435 Recurrence: (n+1)*a(n) = 6*(2*n-1)*a(n-1) - 4*(n-2)*a(n-2). - _Vaclav Kotesovec_, Oct 11 2012
%F A059435 a(n) ~ sqrt(4+3*sqrt(2))*(6+4*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 11 2012
%p A059435 gf := (1+2*x-sqrt(4*x^2-12*x+1))/(8*x): s := series(gf, x, 100): for i from 0 to 50 do printf(`%d,`,coeff(s,x,i)) od:
%t A059435 Table[SeriesCoefficient[(1+2*x-Sqrt[4*x^2-12*x+1])/(8*x),{x,0,n}],{n,0,20}] (* _Vaclav Kotesovec_, Oct 11 2012 *)
%o A059435 (PARI) x='x+O('x^66); Vec((1+2*x-sqrt(4*x^2-12*x+1))/(8*x)) \\ _Joerg Arndt_, May 06 2013
%Y A059435 Cf. A001003, A006318, A054726.
%K A059435 nonn,easy
%O A059435 0,2
%A A059435 _Wenjin Woan_, Feb 01 2001