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

Author

N. J. A. Sloane

Keywords

• nonn

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

Crossrefs

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

Programs

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

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.

Extensions

More terms from Emeric Deutsch, Nov 21 2004

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