A026418 Number of ordered trees with n edges and having no branches of length 1.

1, 0, 1, 1, 2, 3, 6, 11, 22, 43, 87, 176, 362, 748, 1560, 3270, 6897, 14613, 31104, 66459, 142518, 306603, 661572, 1431363, 3104619, 6749390, 14704387, 32098729, 70198656, 153785705, 337443785, 741551614, 1631910081, 3596083215

Offset

0,5

Comments

Hankel transform is A166446(n+2). - Paul Barry, Mar 29 2011

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Jean-Luc Baril and Sergey Kirgizov, Lattice paths with a first return decomposition constrained by the maximal height of a pattern, arXiv:2110.02831 [math.CO], 2021.

Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Motzkin paths with a restricted first return decomposition, Integers (2019) Vol. 19, A46.

Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.

Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.

Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 21.

John Riordan, Enumeration of plane trees by branches and endpoints, J. Comb. Theory (A) 19, 1975, 214-222.

Formula

a(n) = sum(binomial(n-2-j, j)*m{j), j=0..floor(n/2)-1), where m(j)=sum(binomial(n, 2k)*binomial(2k, k)/(k+1), k=0..floor(n/2)) is the Motzkin number A001006(j).

G.f.: g=g(z) satisfies z^2g^2-(1-z+z^2)g+1-z+z^2=0

G.f.: [1,1,2,3,...] has g.f. 1/(1-x-x^2-x^4/(1-x-x^2-x^4/(1-x-x^2-x^4/(1... (continued fraction). - Paul Barry, Jul 16 2009

G.f.: c(x^2/(1-x+x^2)) where c(x) is the g.f. of A000108.

G.f.: g(x)=1/(1-x^2/(1-x+x^2-x^2*g(x)))=1/(1-x^2/(1-x+x^2-x^2/(1-x^2/(1-x+x^2-x^2/(1-... (continued fraction). - Paul Barry, Mar 29 2011

D-finite with recurrence (n+2)*a(n) +(-2*n-1)*a(n-1) +(-n+1)*a(n-2) +(2*n-5)*a(n-3) +3*(-n+4)*a(n-4)=0. - R. J. Mathar, Nov 24 2012

G.f.: (1 - x + x^2 - sqrt(1- 2*x - x^2 + 2*x^3 - 3*x^4))/(2*x^2). - Sergei N. Gladkovskii, Oct 04 2013

a(n) ~ sqrt(26+2*sqrt(13)) * ((1+sqrt(13))/2)^n / (4 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 12 2014

Example

a(6)=6 because we have the following six ordered trees with 6 edges and no branches of length 1 (hanging from the root): (i) a path of length 6, (ii) a path of length 2 and a path of length 4, (iii) two paths of length 3, (iv) a path of length 4 and a path of length 2, (v) three paths of length 2 and (vi) a path of length 2 at the end of which two paths of length 2 are hanging.

Mathematica

CoefficientList[Series[(1-x+x^2-Sqrt[1-2*x-x^2+2*x^3-3*x^4])/(2*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)

Crossrefs

Cf. A001006.

Sequence in context: A247968 A005578 A058050 * A063895 A337090 A331993

Adjacent sequences: A026415 A026416 A026417 * A026419 A026420 A026421

Keyword

nonn

Author

Emeric Deutsch, Dec 04 2003

Status

approved