A063020 - OEIS

%I #55 Sep 21 2023 11:32:17

%S 0,1,1,3,9,32,119,466,1881,7788,32868,140907,611871,2685732,11896906,

%T 53115412,238767737,1079780412,4909067468,22424085244,102865595140,

%U 473678981820,2188774576575,10145798119530,47165267330415,219839845852692,1027183096151244,4810235214490986

%N Reversion of y - y^2 - y^3 + y^4.

%C Seems to be the inverse of A007858. Can someone prove this?

%C a(n+1) counts paths from (0,0) to (n,n) which do not go above the line y=x, using steps (1,0) and (2k,1), where k ranges over the nonnegative integers. For example, the 9 paths from (0,0) to (3,3) are the 5 Catalan paths, as well as DNEN, DENN, EDNN and ENDN. Here E=(1,0), N=(0,1), D=(2,1). - _Brian Drake_, Sep 20 2007

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

%H Brian Drake, <a href="http://dx.doi.org/10.1016/j.disc.2008.11.020">Limits of areas under lattice paths</a>, Discrete Math. 309 (2009), no. 12, 3936-3953.

%H Elżbieta Liszewska and Wojciech Młotkowski, <a href="https://arxiv.org/abs/1907.10725">Some relatives of the Catalan sequence</a>, arXiv:1907.10725 [math.CO], 2019.

%H A. Mironov and A. Morozov, <a href="https://arxiv.org/abs/2009.11641">Algebra of quantum C-polynomials</a>, arXiv:2009.11641 [hep-th], 2020.

%H Hanna Mularczyk, <a href="https://arxiv.org/abs/1908.04025">Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations</a>, arXiv:1908.04025 [math.CO], 2019.

%H <a href="/index/Res#revert">Index entries for reversions of series</a>

%F a(n) = (1/n)*Sum_{k=0..n-1} binomial(n+k-1,n-1) * Sum_{j=0..k} binomial(j,n-3*k+2*j-1)*(-1)^(j-k)*binomial(k,j). - _Vladimir Kruchinin,_ Oct 11 2011

%F a(n) = (1/n)*Sum_{i=0..n-1} (-1)^(i)*binomial(n+i-1,i)*binomial(3*n-i-2,n-i-1), n > 0. - _Vladimir Kruchinin_, Feb 13 2014

%F Recurrence: 16*(n-1)*n*(2*n-1)*(17*n-27)*a(n) = (n-1)*(1819*n^3 - 6527*n^2 + 7350*n - 2520)*a(n-1) + 8*(2*n-3)*(4*n-9)*(4*n-7)*(17*n-10)*a(n-2). - _Vaclav Kotesovec_, Feb 13 2014

%F a(n) ~ sqrt(11-3/sqrt(17))/16 * (107+51*sqrt(17))^n / (sqrt(Pi) * n^(3/2) * 2^(6*n)). - _Vaclav Kotesovec_, Feb 13 2014

%F The g.f. A(x) satisfies x*A'(x)/A(x) = 1 + x + 5*x^2 + 19*x^3 + 85*x^4 + ..., the g.f. of A348410. - _Peter Bala_, Feb 22 2022

%p A:= series(RootOf(_Z-_Z^2-_Z^3+_Z^4-x), x, 21): seq(coeff(A,x,i), i=0..20); # _Brian Drake_, Sep 20 2007

%t CoefficientList[InverseSeries[Series[y - y^2 - y^3 + y^4, {y, 0, 30}], x], x]

%o (Maxima)

%o a(n):=sum((sum(binomial(j,n-3*k+2*j-1)*(-1)^(j-k)*binomial(k,j),j,0,k))*binomial(n+k-1,n-1),k,0,n-1)/n; /* _Vladimir Kruchinin_, Oct 11 2011 */

%o (PARI) x='x+O('x^66); concat([0],Vec(serreverse(x-x^2-x^3+x^4))) \\ _Joerg Arndt_, May 28 2013

%o (Maxima)

%o a(n):=sum((-1)^(i)*binomial(n+i-1,i)*binomial(3*n-i-2,n-i-1),i,0,n-1)/n; /* _Vladimir Kruchinin_, Feb 13 2014 */

%o (SageMath)

%o def b(n):

%o     h = binomial(3*n + 1, n) * hypergeometric([-n, n + 1], [-3*n - 1], -1) / (n + 1)

%o     return simplify(h)

%o print([0] + [b(n) for n in range(27)])  # _Peter Luschny_, Sep 21 2023

%Y Cf. A007848, A052709, A064641, A348410.

%K nonn,easy

%O 0,4

%A _Olivier Gérard_, Jul 05 2001