A063020 Reversion of y - y^2 - y^3 + y^4.

0, 1, 1, 3, 9, 32, 119, 466, 1881, 7788, 32868, 140907, 611871, 2685732, 11896906, 53115412, 238767737, 1079780412, 4909067468, 22424085244, 102865595140, 473678981820, 2188774576575, 10145798119530, 47165267330415, 219839845852692, 1027183096151244, 4810235214490986

Offset: 0

Author

Olivier Gérard, Jul 05 2001

Keywords

• nonn
• easy

Comments

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

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.
• Elżbieta Liszewska and Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.
• A. Mironov and A. Morozov, Algebra of quantum C-polynomials, arXiv:2009.11641 [hep-th], 2020.
• Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
• Index entries for reversions of series

Crossrefs

Cf. A007848, A052709, A064641, A348410.

Programs

Maple

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

Mathematica

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

Maxima

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

Maxima

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

PARI

x='x+O('x^66); concat([0],Vec(serreverse(x-x^2-x^3+x^4))) \\ Joerg Arndt, May 28 2013

SageMath

def b(n):
    h = binomial(3*n + 1, n) * hypergeometric([-n, n + 1], [-3*n - 1], -1) / (n + 1)
    return simplify(h)
print([0] + [b(n) for n in range(27)])  # Peter Luschny, Sep 21 2023

Formula

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

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

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

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

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