|
Search: id:A026418
|
|
|
| A026418 |
|
Number of ordered trees with n edges and having no branches of length 1. |
|
+0
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; listen)
|
|
|
OFFSET
|
0,5
|
|
|
REFERENCES
|
J. 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); [From Paul Barry (pbarry(AT)wit.ie), Jul 16 2009]
|
|
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 this_sequence A063895 A027214 A132831
Adjacent sequences: A026415 A026416 A026417 this_sequence A026419 A026420 A026421
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 04 2003
|
|
|
Search completed in 0.002 seconds
|
