A003227 - OEIS

A003227

Endpoints (leaves) in rooted trees with n nodes.
(Formerly M2744)

1, 1, 3, 8, 22, 58, 160, 434, 1204, 3341, 9363, 26308, 74376, 210823, 599832, 1710803, 4891876, 14015505, 40231632, 115669419, 333052242, 960219982, 2771707332, 8009222307, 23166563032, 67069289457, 194332834601

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

Number of unlabeled rooted trees with n nodes and a distinguished leaf. - Gus Wiseman, Jul 31 2018

REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Table of n, a(n) for n=1..27.

R. W. Robinson and A. J. Schwenk, The distribution of trees in a large random tree, Discr. Math., 12 (1975), 359-372.

Eric Weisstein's World of Mathematics, Tree Leaf.

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

FORMULA

a(n) = Sum_{k=1..n} k*A055277(n, k).

EXAMPLE

The a(4) = 8 rooted trees with a distinguished leaf are (((O))), ((Oo)), ((oO)), (O(o)), (o(O)), (Ooo), (oOo), (ooO). - Gus Wiseman, Jul 31 2018

MATHEMATICA

urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]], {ptn, IntegerPartitions[n-1]}];

Table[Sum[Length[Flatten[{t/.{}->1}]], {t, urt[n]}], {n, 15}] (* Gus Wiseman, Jul 31 2018 *)

CROSSREFS

Cf. A000081, A003228, A004111, A038046, A055277, A317580.

Sequence in context: A271893 A001853 A217898 * A291399 A077848 A300662

Adjacent sequences: A003224 A003225 A003226 * A003228 A003229 A003230

KEYWORD

nonn,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

Corrected and extended with formula by Christian G. Bower, May 25 2000

STATUS

approved