A000672 -id:A000672 - cp's OEIS frontend

A144528 Triangle read by rows: T(n,k) is the number of trees on n unlabeled nodes with all nodes of degree <= k (n>=1, 0 <= k <= n-1).

1, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 2, 3, 0, 0, 1, 4, 5, 6, 0, 0, 1, 6, 9, 10, 11, 0, 0, 1, 11, 18, 21, 22, 23, 0, 0, 1, 18, 35, 42, 45, 46, 47, 0, 0, 1, 37, 75, 94, 101, 104, 105, 106, 0, 0, 1, 66, 159, 204, 223, 230, 233, 234, 235, 0, 0, 1, 135, 355, 473, 520, 539, 546, 549, 550, 551

Offset: 1

N. J. A. Sloane, Dec 20 2008

			Triangle begins:
  1
  0 1
  0 0 1
  0 0 1  2
  0 0 1  2  3
  0 0 1  4  5  6
  0 0 1  6  9 10  11
  0 0 1 11 18 21  22  23
  0 0 1 18 35 42  45  46  47
  0 0 1 37 75 94 101 104 105 106
  ...
From _Andrew Howroyd_, Dec 17 2020: (Start)
Formatted as an array to show the full columns:
================================================
n\k  | 0 1 2   3   4   5   6   7   8   9  10
-----+------------------------------------------
   1 | 1 1 1   1   1   1   1   1   1   1   1 ...
   2 | 0 1 1   1   1   1   1   1   1   1   1 ...
   3 | 0 0 1   1   1   1   1   1   1   1   1 ...
   4 | 0 0 1   2   2   2   2   2   2   2   2 ...
   5 | 0 0 1   2   3   3   3   3   3   3   3 ...
   6 | 0 0 1   4   5   6   6   6   6   6   6 ...
   7 | 0 0 1   6   9  10  11  11  11  11  11 ...
   8 | 0 0 1  11  18  21  22  23  23  23  23 ...
   9 | 0 0 1  18  35  42  45  46  47  47  47 ...
  10 | 0 0 1  37  75  94 101 104 105 106 106 ...
  11 | 0 0 1  66 159 204 223 230 233 234 235 ...
  12 | 0 0 1 135 355 473 520 539 546 549 550 ...
  ...
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Rebecca Neville, Graphs whose vertices are forests with bounded degree, Graph Theory Notes of New York, LIV (2008), 12-21. [Wayback Machine link]

Columns k=2..7 are A000012, A000672, A000602, A036650, A036653, A359392.
The last three diagonals give A144527, A144520, A000055.
Cf. A144215, A238414, A299038.

b[n_, i_, t_, k_] := b[n, i, t, k] = If[i<1, 0, Sum[Binomial[b[i-1, i-1,
  k, k] + j-1, j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
b[0, i_, t_, k_] = 1; a = {}; nmax = 20;
For[ni=2, ni < nmax-1, ni++, (* columns 3 to max-1 *)
  gf[x_] = 1 + Sum[b[j-1, j-1, ni, ni] x^j, {j, 1, nmax}];
  ci[x_] = SymmetricGroupIndex[ni+1, x] /. x[i_] -> gf[x^i];
  a = Append[a, CoefficientList[Normal[Series[
    gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x], {x, 0, nmax}]], x]];]
Join[{1, 0, 1, 0, 0, 1}, Table[Join[{0, 0, 1}, Table[a[[k-3]][[n+1]],
{k, 4, n}]], {n, 4, nmax}]] // Flatten (* Robert A. Russell, Feb 05 2023 *)

\\ here V(n,k) gives column k as a vector.
MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={Mat(vector(m, k, V(n,k-1)[2..1+n]~))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ Andrew Howroyd, Dec 18 2020

a(53) corrected and terms a(56) and beyond from Andrew Howroyd, Dec 17 2020

A086317 Decimal expansion of asymptotic constant xi for counts of weakly binary trees.

Original entry on oeis.org

2, 4, 8, 3, 2, 5, 3, 5, 3, 6, 1, 7, 2, 6, 3, 6, 8, 5, 8, 5, 6, 2, 2, 8, 8, 5, 1, 8, 1, 7, 8, 2, 2, 1, 2, 8, 9, 1, 8, 8, 6, 9, 7, 3, 4, 0, 8, 1, 4, 3, 6, 4, 5, 8, 5, 9, 2, 0, 2, 5, 9, 6, 9, 7, 3, 0, 6, 7, 4, 2, 5, 4, 0, 8, 8, 5, 8, 0, 9, 8, 3, 9, 0, 6, 4, 7, 6, 4, 0, 1, 6, 9, 1, 6, 7, 2, 1, 8, 2, 7, 4, 7

Offset: 1

Eric W. Weisstein, Jul 15 2003

			2.48325353617263685856228851817822128918869734...

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Lyuben Lichev, Dieter Mitsche, On the modularity of 3-regular random graphs and random graphs with given degree sequences, arXiv:2007.15574 [math.PR], 2020.
Eric Weisstein's World of Mathematics, Weakly binary tree

Cf. A001190, A086318, A240943.

Cf. A000672, A003214.

digits = 102; c[0] = 2; c[n_] := c[n] = c[n - 1]^2 + 2; xi[n_Integer] := xi[n] = c[n]^(2^-n); xi[5]; xi[n = 10]; While[RealDigits[xi[n], 10, digits] != RealDigits[xi[n - 5], 10, digits], n = n + 5]; RealDigits[xi[n], 10, digits] // First (* Jean-François Alcover, May 27 2014 *)

Equals 1/A240943.

Equals lim_{n->infinity} A001190(n)^(1/n). - Vaclav Kotesovec, Jul 28 2014

Typos corrected by Jean-François Alcover, May 27 2014

A129860 Number of unrooted bifurcating tree shapes with n leaves.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 11, 18, 37, 66, 135, 265, 552, 1132, 2410, 5098, 11020, 23846, 52233, 114796, 254371, 565734, 1265579, 2841632, 6408674, 14502229, 32935002, 75021750, 171404424, 392658842, 901842517, 2076217086, 4790669518, 11077270335

Offset: 2

Barry Cipra, May 23 2007

nonn

Alternatively, the number of unrooted, unlabeled binary tree topologies with n leaves. - Steven Kelk, Jul 22 2016

This sequence is identical to A000672 (3-valent trees, boron trees, or binary trees) except the offset is different. A000672 is the main entry for this sequence and has much more information (including a b-file with many more terms). Thanks to Steven Kelk for noticing the errors in the present sequence (which have now been corrected), and for discovering the connection with A000672. - N. J. A. Sloane, Jul 22 2016

Joseph Felsenstein, Inferring Phylogenies. Sinauer Associates, Inc., 2004, page 33. Note that at least the first two editions give an incorrect version of this sequence.

Jean-François Fortin, Wen-Jie Ma, Witold Skiba, Seven-Point Conformal Blocks in the Extended Snowflake Channel and Beyond, arXiv:2006.13964 [hep-th], 2020.
Jean-François Fortin, Wen-Jie Ma, Witold Skiba, All Global One- and Two-Dimensional Higher-Point Conformal Blocks, arXiv:2009.07674 [hep-th], 2020.

Essentially the same sequence as A000672.

Entry revised by N. J. A. Sloane, Jul 22 2016 at the suggestion of Steven Kelk

A000673 Number of bicentered 3-valent (or boron, or binary) trees with n nodes.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 2, 2, 6, 8, 18, 30, 67, 127, 275, 551, 1192, 2507, 5475, 11820, 26007, 57077, 126686, 281625, 630660, 1416116, 3195784, 7232624, 16430563, 37429146, 85528079, 195940960, 450074270, 1036226173, 2391193488, 5529420585

Offset: 0

N. J. A. Sloane

A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 451).
R. C. Read, personal communication.
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).

Nicolas Broutin and Philippe Flajolet, The distribution of height and diameter in random non-plane binary trees, Random Struct. Algorithms 41, No. 2, 215-252 (2012).
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
Index entries for sequences related to trees

A000672 = A000673 + A000675. Cf. A000022, A000200, A000602.

n = 50; (* algorithm from Rains and Sloane *)
S2[f_,h_,x_] := f[h,x]^2/2 + f[h,x^2]/2;
T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S2[T,h-1,z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + (T[h,z] - T[h-1,z])^2/2 + (T[h,z^2] - T[h-1,z^2])/2, z],n+1], {h,0,n/2}] (* Robert A. Russell, Sep 15 2018 *)

A000675 Number of centered 3-valent (or boron, or binary) trees with n nodes.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 2, 4, 5, 10, 19, 36, 68, 138, 277, 581, 1218, 2591, 5545, 12026, 26226, 57719, 127685, 284109, 634919, 1425516, 3212890, 7269605, 16504439, 37592604, 85876345, 196717882, 451768247, 1039990913, 2399476030, 5547849750

Offset: 0

N. J. A. Sloane

A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 451).
R. C. Read, personal communication.
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).

E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
Index entries for sequences related to trees

A000672 = A000673 + A000675. Cf. A000022, A000200, A000602.

n = 50; (* algorithm from Rains and Sloane *)
S2[f_,h_,x_] := f[h,x]^2/2 + f[h,x^2]/2;
S3[f_,h_,x_] := f[h,x]^3/6 + f[h,x] f[h,x^2]/2 + f[h,x^3]/3;
T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S2[T,h-1,z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + S3[T,h-1,z]z - S3[T,h-2,z]z - (T[h-1,z] - T[h-2,z]) (T[h-1,z]-1),z], n+1], {h,1,n/2}] + PadRight[{1,1}, n+1] (* Robert A. Russell, Sep 15 2018 *)

A380633 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes of degree at most 3 with k cycles and each node a member of exactly one cycle, 0 <= k <= floor(n/3).

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 2, 0, 1, 2, 1, 0, 1, 3, 3, 0, 1, 3, 6, 0, 1, 4, 11, 2, 0, 1, 4, 17, 5, 0, 1, 5, 26, 17, 0, 1, 5, 36, 37, 2, 0, 1, 6, 50, 78, 12, 0, 1, 6, 65, 140, 44, 0, 1, 7, 85, 248, 131, 4, 0, 1, 7, 106, 396, 325, 23

Offset: 0

Andrew Howroyd, Feb 24 2025

All such graphs are cactus graphs (with bridges allowed).

			Triangle begins:
  1;
  0;
  0;
  0, 1;
  0, 1;
  0, 1;
  0, 1, 1;
  0, 1, 1;
  0, 1, 2;
  0, 1, 2,  1;
  0, 1, 3,  3;
  0, 1, 3,  6;
  0, 1, 4, 11,  2;
  0, 1, 4, 17,  5;
  0, 1, 5, 26, 17;
  0, 1, 5, 36, 37, 2;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1750 (rows 0..100)
Wikipedia, Cactus graph.
Index entries for sequences related to cacti.

Columns 0..3 are A000007, A000012(n+3), A004526(n+4), A003453(n+4).
Row sums are A380805.
Cf. A000672, A380631 (with vertices of any degree).

raise(p,d) = {my(n=serprec(p,x)-1); substvec(p + O(x^(n\d+1)), [x, y], [x^d,y^d])}
R(n,y)={my(g=O(x^3)); for(n=1, (n-1)\2, my(p=x*(1 + g), p2=raise(p,2)); g=x*y*(p^2/(1 - p) + (1 + p)*p2/(1 - p2))/2); g}
G(n,y=1)={my(g=R(n,y), p = x*(1+g) + O(x*x^n));
  my( r=((1 + p)^2/(1 - raise(p,2)) - 1)/2 );
  my( c=-sum(d=1, n, eulerphi(d)/d*log(raise(1-p,d))) );
  1 + (raise(g,2) - g^2 + y*(r + c - 2*p - p^2 - raise(p,2)))/2 }
T(n)={[Vecrev(p) | p<-Vec(G(n,y))]}
{my(A=T(15)); for(i=1, #A, print(A[i]))}

T(3*n,n) = A000672(n).

A363251 Number of nonisomorphic open quipus with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 11, 18, 36, 64, 127, 241, 480, 935, 1868, 3688, 7373, 14655, 29305, 58432, 116859, 233367, 466727, 932761, 1865513, 3729648, 7459286, 14915826, 29831640, 59657802, 119315589, 238620236, 477240456, 954459044, 1908918069, 3817792423

Offset: 0

Didrik Fosse, May 31 2023

An open quipu is a tree of maximal valency 3 such that all nodes of degree 3 lie on a path.

			The 4 open quipus with 6 nodes are:
  ._._._._._.   ._._._._.   ._._._._.   ._._._.
                  |             |         | |
The smallest interesting nonexample, a 3-valent tree where the nodes of degree 3 do not lie on a path, is:
     .   .
     |   |
   ._._._._.
       |
     ._._.

Paolo Xausa, Table of n, a(n) for n = 0..1000
Renee Woo and Arnold Neumaier, On Graphs Whose Spectral Radius is Bounded by 3/2*sqrt(2), Graphs and Combinatorics 23 (2007), 713-726. Also preprint and slides.
Index entries for linear recurrences with constant coefficients, signature (2,3,-5,-3,-1,3,7,0,-1,-6,-2,4).

A000672 minus the trees where the nodes of degree 3 do not lie on a path.

Cf. A130131 (any maximum degree).

LinearRecurrence[{2,3,-5,-3,-1,3,7,0,-1,-6,-2,4},{1,1,1,1,2,2,4,6,11,18,36,64,127},50] (* Paolo Xausa, Aug 13 2023 *)

G.f.: (1 - x - 4*x^2 + x^3 + 5*x^4 + 4*x^5 - 4*x^7 - 6*x^8 - 3*x^9 + 5*x^10 + 4*x^11 - x^12)/((1 - x)^3*(1 + x)^2*(1 - 2*x)*(1 + x^2)*(1 + x + x^2)*(1 - 2*x^2)). - Andrew Howroyd, May 31 2023

A052120 Number of 3-valent trees (= boron trees or binary trees) with n nodes.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 4, 0, 6, 0, 11, 0, 18, 0, 37, 0, 66, 0, 135, 0, 265, 0, 552, 0, 1132, 0, 2410, 0, 5098, 0, 11020, 0, 23846, 0

Offset: 1

N. J. A. Sloane

Trees with n nodes each of valency either 1 or 3.

Eric Weisstein's World of Mathematics, Cayley Tree.
Eric Weisstein's World of Mathematics, Trivalent Tree
Index entries for sequences related to trees

See A000672, the subsequence of even-numbered terms, which is the main entry for this sequence, for more terms, references, etc.

A335408 Diameter of nearest neighbor interchange distance for free 3-trees.

Original entry on oeis.org

0, 1, 3, 5, 7, 10, 12, 15, 18, 21

Offset: 3

Martin R. Smith, Jun 06 2020

a(n) is the maximum value of the nearest neighbor interchange distance between two unrooted binary trees with n leaves, obtained by evaluating the distance from one tree with each of the unlabeled n-leaf tree shapes (see A000672) to each labeled n-leaf tree (A001147) using the C script described in Li et al. (1996).

The known terms a(3),...,a(12) happen (coincidentally?) to match the first ten terms of A211266. However, it seems unlikely that the sequences will agree for ever.

Ming Li, John Tromp, and Louxin Zhang, Some notes on the nearest neighbour interchange distance, in Goos, G., Hartmanis, J., Leeuwen, J., Cai, J.-Y., and Wong, C. K., eds., "Computing and Combinatorics" 1090, Springer (Berlin, Heidelberg) (1996), 343-351. doi:10.1007/3-540-61332-3_168.

Ming Li, John Tromp, and Louxin Zhang, Some notes on the nearest neighbour interchange distance, on ResearchGate.
Ming Li, John Tromp, and Louxin Zhang, On the Nearest Neighbour Interchange Distance Between Evolutionary Trees, J. Theoretical Biology, 182 (1996), 463-467.

Cf. A211266, which happens to have the same initial terms (offset by two). It is not clear whether this correspondence continues for higher terms.

A000672 gives the number of unrooted tree shapes on n leaves; A001147 gives the number of (labeled) unrooted trees.

cp's OEIS Frontend

A144528 Triangle read by rows: T(n,k) is the number of trees on n unlabeled nodes with all nodes of degree <= k (n>=1, 0 <= k <= n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A086317 Decimal expansion of asymptotic constant xi for counts of weakly binary trees.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A129860 Number of unrooted bifurcating tree shapes with n leaves.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A000673 Number of bicentered 3-valent (or boron, or binary) trees with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

A000675 Number of centered 3-valent (or boron, or binary) trees with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

A380633 Triangle read by rows: T(n,k) is the number of simple connected graphs on n unlabeled nodes of degree at most 3 with k cycles and each node a member of exactly one cycle, 0 <= k <= floor(n/3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A363251 Number of nonisomorphic open quipus with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A052120 Number of 3-valent trees (= boron trees or binary trees) with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

A335408 Diameter of nearest neighbor interchange distance for free 3-trees.