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
Keywords
Examples
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.
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.
Crossrefs
Cf. A001006.
Programs
-
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 *)
Formula
a(n) = Sum_{j=0..floor(n/2)-1} binomial(n-2-j, j)*m(j), where m(j) = Sum_{k=0..floor(j/2)} binomial(j, 2*k)*binomial(2*k, k)/(k+1) is the Motzkin number A001006(j) for n > 2.
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
Comments