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

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

Author

N. J. A. Sloane

Extensions

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

Status

approved