1,4

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.

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]

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

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.

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

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

More terms from Emeric Deutsch, Nov 21 2004

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

approved