A271205 -id:A271205 - cp's OEIS frontend

A000014 Number of series-reduced trees with n nodes.

0, 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, 26, 42, 78, 132, 249, 445, 842, 1561, 2988, 5671, 10981, 21209, 41472, 81181, 160176, 316749, 629933, 1256070, 2515169, 5049816, 10172638, 20543579, 41602425, 84440886, 171794492, 350238175, 715497037, 1464407113

Offset: 0

N. J. A. Sloane

Other terms for "series-reduced tree": (i) homeomorphically irreducible tree, (ii) homeomorphically reduced tree, (iii) reduced tree, (iv) topological tree.

In a series-reduced tree, vertices cannot have degree 2; they can be leaves or have >= 2 branches.

			G.f. = x + x^2 + x^4 + x^5 + 2*x^6 + 2*x^7 + 4*x^8 + 5*x^9 + 10*x^10 + ...
The star graph with n nodes (except for n=3) is a series-reduced tree. For n=6 the other series-reduced tree is shaped like the letter H. - _Michael Somos_, Dec 19 2014

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 284.
D. G. Cantor, personal communication.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Fig. 3.3.3.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Matthew Parker, Table of n, a(n) for n = 0..1000 (first 501 terms from Christian G. Bower)
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], 30 June 2014.
Ira M. Gessel, Good Will Hunting's Problem: Counting Homeomorphically Irreducible Trees, arXiv:2305.03157 [math.CO], 2023.
James Grime and Brady Haran, The problem in Good Will Hunting, 2013 (Numberphile video).
Frank Harary and Geert Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503.
F. Harary, R. W. Robinson and A. J. Schwenk, Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes. [Cached copy of top page only, pdf file, no active links, with permission]
Matthew Parker, The first 2000 terms (7-Zip compressed file)
A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972
N. J. A. Sloane, Illustration of initial terms
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Series-Reduced Tree
Index entries for sequences related to trees
Index entries for "core" sequences

Cf. A000055 (trees), A001678 (series-reduced planted trees), A007827 (series-reduced trees by leaves), A271205 (series-reduced trees by leaves and nodes).

with(powseries): with(combstruct): n := 30: Order := n+3: sys := {B = Prod(C,Z), S = Set(B,1 <= card), C = Union(Z,S)}:
G001678 := (convert(gfseries(sys,unlabeled,x) [S(x)], polynom)) * x^2: G0temp := G001678 + x^2:
G059123 := G0temp / x + G0temp - (G0temp^2+eval(G0temp,x=x^2))/(2*x):
G000014 := ((x-1)/x) * G059123 + ((1+x)/x^2) * G0temp - (1/x^2) * G0temp^2:
A000014 := 0,seq(coeff(G000014,x^i),i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)

a[n_] := If[n<1, 0, A = x/(1-x^2) + x*O[x]^n; For[k=3, k <= n-1, k++, A = A/(1 - x^k + x*O[x]^n)^SeriesCoefficient[A, k]]; s = ((Normal[A] /. x -> x^2) + O[x]^(2n))*(1-x) + A*(2-A)*(1+x); SeriesCoefficient[s, n]/2]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 02 2016, adapted from PARI *)

{a(n) = my(A); if( n<1, 0, A = x / (1 - x^2) + x * O(x^n); for(k=3, n-1, A /= (1 - x^k + x * O(x^n))^polcoeff(A, k)); polcoeff( (subst(A, x, x^2) * (1 - x) + A * (2 - A) * (1 + x)) / 2, n))}; /* Michael Somos, Dec 19 2014 */

G.f.: A(x) = ((x-1)/x)*f(x) + ((1+x)/x^2)*g(x) - (1/x^2)*g(x)^2 where f(x) is g.f. for A059123 and g(x) is g.f. for A001678. [Harary and E. M. Palmer, p. 62, Eq. (3.3.10) with extra -(1/x^2)*Hbar(x)^2 term which should be there according to eq.(3.3.14), p. 63, with eq.(3.3.9)]. [corrected by Wolfdieter Lang, Jan 09 2001]

a(n) ~ c * d^n / n^(5/2), where d = A246403 = 2.189461985660850..., c = 0.684447272004914061023163279794145361469033868145768075109924585532604582794... - Vaclav Kotesovec, Aug 25 2014

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

Original entry on oeis.org

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

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

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

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.

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

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.

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

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

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.

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

A271362 Number T(n,k) of series-reduced free trees with n nodes of which exactly k>=3 are leaves, k+1 <= n <= 2k-2.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 2, 4, 3, 1, 4, 6, 3, 1, 2, 10, 9, 4, 1, 8, 17, 12, 4, 1, 4, 22, 30, 16, 5, 1, 15, 47, 44, 20, 5, 1, 6, 53, 91, 67, 25, 6, 1, 32, 127, 158, 91, 30, 6, 1, 11, 121, 282, 258, 126

Offset: 4

Stephan Beyer, Apr 05 2016

The length of row n is floor((n-2)/2).

			    Irregular triangle begins
    n \ k 3   4   5   6   7  8
     4     1;
     5     1;
     6     1,  1;
     7     1,  1;
     8     1,  2,  1;
     9     2,  2,  1;
    10     2,  4,  3,  1;
    11     4,  6,  3,  1;
    12     2, 10,  9,  4, 1;
    13     8, 17, 12,  4, 1;
    14     4, 22, 30, 16, 5, 1;
    15    15, 47, 44, 20, 5, 1;
    ...

Washington Bomfim, Table of n, a(n) for n = 4..199
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.

Transpose of A271205.

Cf. A000014 (row sums), A345971.

\\ using files hitree4.txt etc from McKay.
nL(n, Tr) = { my(E = strsplit(Tr, "  "), u_v, Deg = vectorsmall(n));
for(j = 1, n-1, u_v = strsplit(E[j], " "); u_v = eval(u_v);
   Deg[ u_v[1]+1 ]++; Deg[ u_v[2]+1 ]++); sum(v = 1, n, Deg[v] == 1)
};
Rows(r1, r2) = {my(F, C, nF); for(n = r1, r2,
F = readstr(Str("hitree", n, ".txt")); C = vectorsmall(n-1);
for(i = 1, #F, nF = nL(n, F[i]); C[nF]++ );
print1(n" "); for(i=1, #C, if(C[i] > 0, print1(C[i]", "))); print() )
}; \\ Washington Bomfim, Jul 09 2021

T(n,k) = A271205(k,n).

cp's OEIS Frontend

A000014 Number of series-reduced trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A271362 Number T(n,k) of series-reduced free trees with n nodes of which exactly k>=3 are leaves, k+1 <= n <= 2k-2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula