|
| |
|
|
A026418
|
|
Number of ordered trees with n edges and having no branches of length 1.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Hankel transform is A166446(n+2). [Paul Barry, Mar 29 2011].
|
|
|
REFERENCES
|
J. Riordan, Enumeration of plane trees by branches and endpoints, J. Comb. Theory (A) 19, 1975, 214-222.
|
|
|
LINKS
|
Table of n, a(n) for n=0..33.
|
|
|
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); [From 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].
Conjecture: (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
|
|
|
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.
|
|
|
CROSSREFS
|
Cf. A001006.
Sequence in context: A043327 A005578 A058050 * A063895 A027214 A192652
Adjacent sequences: A026415 A026416 A026417 * A026419 A026420 A026421
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Emeric Deutsch, Dec 04 2003
|
|
|
STATUS
|
approved
|
| |
|
|
