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

Author

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

Keywords

• nonn
• nice
• easy

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

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.

Programs

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 *)

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.

Extensions

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