A007827 - OEIS

%I #38 Nov 20 2023 09:27:51

%S 1,1,1,1,2,3,7,13,32,73,190,488,1350,3741,10765,31311,92949,278840,

%T 847511,2599071,8044399,25082609,78758786,248803504,790411028,

%U 2523668997,8095146289,26076714609,84329102797,273694746208

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

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

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

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

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

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

%H Vincenzo Librandi, <a href="/A007827/b007827.txt">Table of n, a(n) for n = 0..100</a>

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H M. D. Hendy, C. H. C. Little, David Penny, <a href="https://www.jstor.org/stable/2101137">Comparing trees with pendant vertices labelled</a>, SIAM J. Appl. Math. 44 (5) (1984). See Table 1.

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F 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.

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

%t (* 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 *)

%Y 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).

%Y Number of row entries of A064060.

%K nonn,nice,easy

%O 0,5

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

%E Corrected and extended by _Christian G. Bower_, Nov 15 1999