OFFSET
1,3
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
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.
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)
EXAMPLE
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 + ...
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 *)
PROG
(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
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Michael Somos, Jun 17 2005
STATUS
approved