A109081 Reversion of x*(1-x)*(1-x^2)*(1-x^3)/(1-x^6) = x*(1-x)^2/(1-x+x^2).

1, 1, 3, 10, 37, 146, 602, 2563, 11181, 49720, 224540, 1027038, 4748042, 22150519, 104146733, 493012682, 2347796965, 11239697816, 54061835288, 261130778516, 1266125122956, 6160158505040, 30065608532008, 147161532388934

Offset: 1

Author

Michael Somos, Jun 17 2005

Keywords

• nonn

Comments

From David Callan, Mar 30 2007: (Start)

a(n) is the number of vertex-labeled ordered trees (A000108) on n vertices, in which each non-leaf vertex is labeled with a positive integer <= its outdegree. Example. a(3)=3 counts the trees on 3 vertices with labels as shown (the 2 edges in each tree are shown, you have to visualize the vertices).

.

1 2 1

/ \ / \ |1

|

.

Proof. Let F(x) = x + x^2 + 3x^3 + ... denote the g.f. for these trees, with x marking number of vertices. Counting these trees by degree of the root leads to F = x + Sum_{k>=1} k*x*F^k, or F = x + x*F/(1-F)^2. This is the same equation as that satisfied by the reversion of x*(1-x)*(1-x^2)*(1-x^3)/(1-x^6) = x*(1-x)^2/(1-x+x^2). (End)

(1 + 3x + 10x^2 + ...) = (1 + 2x + 6x^2 + ...)*(1 + x + 2x^2 + 6x^3 + ...), where A106228 = (1, 1, 2, 6, 21, ...). - Gary W. Adamson, Nov 15 2011

Reversion of x/(1 + sum(k>=1, k*x^k )) (cf. A028310). - Joerg Arndt, Aug 19 2012

a(n) is the number of Motzkin paths of length 2n-3 with no downsteps in even position (n>=2). Example: a(3)=3 counts FFF, FUD, UFD, where U denotes an upstep (1,1), F a flatstep (1,0), and D a downstep (1,-1). - David Callan, May 20 2015

a(n) is the number of peakless Motzkin paths of length 2n-2 where every pair of matching up and down edges occupies positions of the same parity. Equivalently, the number of RNA secondary structures on 2n-2 vertices where only vertices of the same parity can be matched. - Alexander Burstein, May 17 2021

Examples

			a(5) = 37 = the upper left term of M^4: (37, 26, 12, 4, 1); where (37 + 26 + 12 + 4 + 1) = 80 = A106228(5). - _Gary W. Adamson_, Nov 15 2011
G.f. = x + x^2 + 3*x^3 + 10*x^4 + 37*x^5 + 146*x^6 + 602*x^7 + 2563*x^8 + ...
		

Links

• Robert Israel, Table of n, a(n) for n = 1..1400
• Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
• Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
• Tian-Xiao He and Louis W. Shapiro, Row sums and alternating sums of Riordan arrays, Linear Algebra and its Applications, Volume 507, 15 October 2016, Pages 77-95. See R_2^{-}.
• JiSun Huh, Sangwook Kim, Seunghyun Seo, and Heesung Shin, Bijections on pattern avoiding inversion sequences and related objects, arXiv:2404.04091 [math.CO], 2024. See p. 22.
• Markus Kuba and Alois Panholzer, Enumeration formulas for pattern restricted Stirling permutations, Discrete Math. 312 (2012), no. 21, 3179--3194. MR2957938. - From _N. J. A. Sloane_, Sep 25 2012
• Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
• Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 11.
• Jun Yan, Lattice paths enumerations weighted by ascent lengths, arXiv:2501.01152 [math.CO], 2025. See p. 7.

Crossrefs

Cf. A000108, A028310, A106228, A365770.

Programs

Magma

[&+[Binomial(n, k)/(n-k+1)*Binomial(n+k-1, n-k): k in [0..n]]: n in [0..25]]; // Vincenzo Librandi, Sep 23 2015

Maple

S:= series(RootOf(-x*z^2+z^3+x*z-2*z^2-x+z, z), x, 101):
seq(coeff(S,x,j),j=1..100); # Robert Israel, Nov 19 2015

Mathematica

a[ n_] := If[ n < 2, Boole[n == 1], (n - 1) HypergeometricPFQ[ {n, 1 - n, 2 - n}, {3/2, 2}, 1/4]]; (* Michael Somos, May 28 2014 *)
Join[{1}, Table[Sum[ Binomial[n,k] / (n-k+1) Binomial[n+k-1, n-k], {k, n}], {n, 25}]] (* Vincenzo Librandi, Sep 23 2015 *)

PARI

{a(n) = if( n<1, 0, polcoeff( serreverse( x * (1 - x) * (1 - x^2) * (1 - x^3) / (1 - x^6) + x * O(x^n)), n))};

PARI

{a(n)=sum(k=0,n,binomial(n,k)/(n-k+1)*binomial(n+k-1,n-k))} \\ Paul D. Hanna, Jun 19 2009

Sage

def A109081(n) :
    return (n-1)*hypergeometric([n,1-n,2-n],[3/2, 2],1/4) if n > 1 else 1
[simplify(A109081(n)) for n in (1..24)] # Peter Luschny, Aug 02 2012, Nov 13 2014

Formula

G.f. A(x) satisfies 0 = f(x, A(x)) where f(x, y) = x*(1 - y + y^2) - y*(1 - y)^2.

G.f. A(x) satisfies 0 = f(x, A(x)) where f(x, y) = y*(1 - y)*((1 - y) / x + 1) - 1.

From Paul D. Hanna, Jun 19 2009: (Start)

G.f. satisfies: A(x) = x/(1 - x/(1 - A(x))^2).

a(n) = Sum_{k=0..n} C(n,k)/(n-k+1) * C(n+k-1,n-k). (End)

From Gary W. Adamson, Nov 15 2011: (Start)

a(n) is the upper left term in M^(n-1), M = an infinite square matrix as follows:

1, 1, 0, 0, 0, ...

2, 1, 1, 0, 0, ...

3, 2, 1, 1, 0, ...

4, 3, 2, 1, 1, ...

5, 4, 3, 2, 1, ...

... (End)

With different signs, g.f. = 2/(3-sqrt(1-4xC(x))) where C = g.f. for A000108 [He-Shapiro]. - N. J. A. Sloane, Apr 28 2017

From Vaclav Kotesovec, Aug 14 2018: (Start)

Recurrence: 2*n*(2*n - 1)*(19*n^2 - 85*n + 90)*a(n) = 2*(190*n^4 - 1230*n^3 + 2783*n^2 - 2595*n + 828)*a(n-1) + 2*(n-3)*(38*n^3 - 189*n^2 + 289*n - 132)*a(n-2) + 3*(n-4)*(n-3)*(19*n^2 - 47*n + 24)*a(n-3).

a(n) ~ (1 - (1-s)*s)^(n + 1/2) / (2*sqrt(Pi*(3 - 6*s + s^2)) * n^(3/2) * s^n * (1-s)^(2*n-2)), where s = 0.3611030805286473776346465621590281395264149... is the real root of the equation (s^2 - s + 3)*s = 1. (End)