A007827 Number of homeomorphically irreducible (or series-reduced) trees with n pendant nodes, or continua with n non-cut points, or leaves.

1, 1, 1, 1, 2, 3, 7, 13, 32, 73, 190, 488, 1350, 3741, 10765, 31311, 92949, 278840, 847511, 2599071, 8044399, 25082609, 78758786, 248803504, 790411028, 2523668997, 8095146289, 26076714609, 84329102797, 273694746208

Offset

0,5

Comments

Also, number of unrooted multifurcating tree shapes with n leaves [see Felsenstein].

References

M. Cropper, J. Combin. Math. Combin. Comp., Vol. 24 (1997), 177-184.

Joseph Felsenstein, Inferring Phylogenies. Sinauer Associates, Inc., 2004, p. 33 (Beware errors!).

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62.

S. B. Nadler Jr., Continuum Theory, Academic Press.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..100

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

M. D. Hendy, C. H. C. Little, David Penny, Comparing trees with pendant vertices labelled, SIAM J. Appl. Math. 44 (5) (1984). See Table 1.

Index entries for sequences related to trees

Index entries for sequences related to rooted trees

Formula

G.f.: 1+(1+x-B(x))*B(x) where B(x) = x+x^2+2*x^3+5*x^4+12*x^5+33*x^6+90*x^7+... is g.f. for A000669.

Maple

A := series(1+(1+x-B)*B, x, 30); # where B = g.f. for A000669; A007827 := n->coeff(A, x, n);

Mathematica

(* a9 = A000669 *) max = 29; a9[1] = 1; a9[n_] := (s = Series[1/(1 - x), {x, 0, n}]; Do[s = Series[s/(1 - x^k)^Coefficient[s, x^k], {x, 0, n}], {k, 2, n}]; Coefficient[s, x^n]/2); b[x_] := Sum[a9[n] x^n, {n, 1, max}]; gf[x_] := 1 + (1 + x - b[x])*b[x]; CoefficientList[ Series[gf[x], {x, 0, max}], x] (* Jean-François Alcover, Aug 14 2012 *)

Crossrefs

Cf. A000014 (series-reduced trees), A000055 (trees), A000311, A000669 (series-reduced planted trees by leaves), A059123 (homeomorphically irreducible rooted trees by nodes), A271205 (series-reduced trees by leaves and nodes).

Number of row entries of A064060.

Sequence in context: A003120 A032131 A324844 * A250308 A259145 A237255

Adjacent sequences: A007824 A007825 A007826 * A007828 A007829 A007830

Keyword

nonn,nice,easy

Author

Matthew Cropper (mmcrop01(AT)athena.louisville.edu).

Extensions

Corrected and extended by Christian G. Bower, Nov 15 1999

Status

approved