A049125 Revert transform of (1 + x - x^2) / (1 + x)^2.

1, 1, 2, 4, 10, 25, 68, 187, 534, 1544, 4554, 13576, 40968, 124681, 382636, 1182116, 3674674, 11483243, 36057516, 113701968, 359927638, 1143327888, 3643379152, 11643793399, 37311200060, 119852247220, 385864664018, 1244896820476

Offset

1,3

Comments

a(n) is the number of ordered trees (A000108) with n edges in which every non-leaf non-root vertex has at most one leaf child. The g.f. A(x) is given by A(x)= x/(1-x B(x)) where B(x)=1+x+2x^2+4x^3+... is the g.f. for A143363. [David Callan, Aug 22 2014]

Conjecturally, the number of sequences (e(1), ..., e(n-1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(k). [Martinez and Savage, 2.10] - Eric M. Schmidt, Jul 17 2017

Links

Table of n, a(n) for n=1..28.

Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy

Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.

Index entries for reversions of series

Formula

Given g.f. A(x), then series reversion of B(x) = x + x * A(x) is -B(-x). - Michael Somos, Sep 07 2005

Given g.f. A(x), then B(x) = x + x * A(x) satisfies B(x) = x + C(x * B(x)) where C(x) is g.f. of A001764 offset 1.

D-finite with recurrence 5*n*(n-1)*(37*n-106)*a(n) -4*(n-1) *(74*n^2-323*n+288)*a(n-1) +16*(-74*n^3+508*n^2-1157*n+876)* a(n-2) +2*(2*n-5)*(37*n-69)*(n-4)*a(n-3)=0. - R. J. Mathar, Jun 24 2018

a(n) ~ (1+s)^2 / (2 * sqrt(Pi*(1+4*s)) * n^(3/2) * (s*(1 + s - s^2)/(1+s)^2)^(n - 1/2)), where s = 0.675130870566646070889621798150060480808032527677372732 = 2*cos(arctan(sqrt(37/27))/3)/sqrt(3) + 2*sin(arctan(sqrt(37/27))/3) - 1 is the root of the equation s^3 + 3*s^2 - s = 1. - Vaclav Kotesovec, Aug 17 2018

Example

x + x^2 + 2*x^3 + 4*x^4 + 10*x^5 + 25*x^6 + 68*x^7 + 187*x^8 + 534*x^9 + ...

Mathematica

a[1] = 1;
a[n_] := SeriesCoefficient[InverseSeries[x(1+x-x^2)/(1+x)^2 + x O[x]^n, x], {x, 0, n}];
Array[a, 28] (* Jean-François Alcover, Aug 17 2018, from PARI *)
CoefficientList[InverseSeries[Series[x*(1 + x - x^2)/(1 + x)^2, {x, 0, 30}], x], x] (* Vaclav Kotesovec, Aug 17 2018 *)

Prog

(PARI) {a(n) = if( n<1, 0, polcoeff( serreverse( x * (1 + x - x^2) / (1 + x)^2 + x * O(x^n)), n))} /* Michael Somos, Jul 13 2003 */

Crossrefs

Sequence in context: A317876 A124501 A124344 * A191768 A027432 A032128

Adjacent sequences: A049122 A049123 A049124 * A049126 A049127 A049128

Keyword

nonn

Author

Olivier Gérard

Status

approved