A027415 Number of rooted unlabeled trees on n nodes having a primary branch.

0, 1, 1, 3, 6, 17, 37, 102, 239, 658, 1607, 4425, 11185, 30990, 80070, 222731, 586218, 1638333, 4370721, 12262003, 33077327, 93128828, 253454781, 715784848, 1962537755, 5557799401, 15332668869, 43527249088, 120716987723

Offset

1,4

Comments

Let T be a tree with root node R. If R and the edges incident with it are deleted, the resulting rooted trees are called branches. A primary branch (there can be at most one) has i nodes where n/2 <= i <= n-1.

References

A. Meir and J. W. Moon, On the branch-sizes of rooted unlabeled trees, in "Graph Theory and Its Applications", Annals New York Acad. Sci., Vol. 576, 1989, pp. 399-407. [MR 1110839]

Links

N. J. A. Sloane, Table of n, a(n) for n = 1..200

Index entries for sequences related to rooted trees

Formula

Let r(n) = A000081(n) = number of rooted trees on n nodes. Then a(n)=sum(r(n-i)*r(i), i=1..floor(n/2)) - Emeric Deutsch, Nov 21 2004. Comment from N. J. A. Sloane: The term r(n-i) gives the number of ways of picking the primary branch, while the term r(i) gives the number of ways of picking the rest of the tree including the root R.

Maple

N := 50: Y := [ 1, 1 ]: for n from 3 to N do x*mul( (1-x^i)^(-Y[ i ]), i=1..n-1); series(%, x, n+1); b := coeff(%, x, n); Y := [ op(Y), b ]; od: P:=n->sum(Y[n-i]*Y[i], i=1..floor(n/2)): seq(P(n), n=1..35); # Emeric Deutsch, Nov 21 2004

Crossrefs

This sequence + A027416 = A000081. Cf. A000081, A000055, A102911.

Sequence in context: A049943 A231184 A291227 * A280088 A151503 A319789

Adjacent sequences: A027412 A027413 A027414 * A027416 A027417 A027418

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from Emeric Deutsch, Nov 21 2004

Entry revised by N. J. A. Sloane, Feb 26 2007

Status

approved