A102911 -id:A102911 - cp's OEIS frontend

A000676 Number of centered trees with n nodes.

1, 1, 0, 1, 1, 2, 3, 7, 12, 27, 55, 127, 284, 682, 1618, 3979, 9823, 24722, 62651, 160744, 415146, 1081107, 2831730, 7462542, 19764010, 52599053, 140580206, 377244482, 1016022191, 2745783463, 7443742141, 20239038700, 55178647926, 150820588425, 413226000775

Offset: 0

N. J. A. Sloane

A tree has either a center or a bicenter and either a centroid or a bicentroid. (These terms were introduced by Jordan.)
If the number of edges in a longest path in the tree is 2m, then the middle node in the path is the unique center, otherwise the two middle nodes in the path are the unique bicenters.
On the bottom of first page 266 of article Cayley (1881) is a table of A000676 and A000677 for n = 1..13. - Michael Somos, Aug 20 2018

			G.f. = 1 + x + x^3 + x^4 + 2*x^5 + 3*x^6 + 7*x^7 + 12*x^8 + 27*x^9 + 55*x^10 + ... - _Michael Somos_, Aug 20 2018

N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 49.
F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1994; pp. 35, 36.
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).

Geoffrey Critzer, Table of n, a(n) for n = 0..200 (replacing the first version from N. J. A. Sloane)
Jean-François Alcover, Mathematica program
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. 438).
A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 266-268.
C. Jordan, Sur les assemblages des lignes, J. Reine angew. Math., 70 (1869), 185-190.
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. [This articles states incorrectly that A000676 and A000677 give the numbers of trees with respectively a centroid and bicentroid.]
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 [but beware errors] (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 [but beware errors] (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Centered Tree.
Index entries for sequences related to trees.

Cf. A102911 (trees with a bicentroid), A027416 (trees with a centroid), A000677 (trees with a bicenter), A000055 (trees), A000081 (rooted trees).

Mathematica
```
(* See link. *)
```

a(n) + A000677(n) = A000055(n).

A027416 Number of unlabeled (and unrooted) trees on n nodes having a centroid.

Original entry on oeis.org

1, 1, 0, 1, 1, 3, 3, 11, 13, 47, 61, 235, 341, 1301, 1983, 7741, 12650, 48629, 82826, 317955, 564225, 2144505, 3926353, 14828074, 27940136, 104636890, 201837109, 751065460, 1479817181, 5469566585, 10975442036, 40330829030, 82270184950

Offset: 0

N. J. A. Sloane

nonn

Also, number of rooted unlabeled trees on n nodes not having a primary branch.
A tree has either a center or a bicenter and either a centroid or a bicentroid. (These terms were introduced by Jordan.)
If the number of edges in a longest path in the tree is 2m, then the middle node in the path is the unique center, otherwise the two middle nodes in the path are the unique bicenters.
On the other hand, define the weight of a node P to be the greatest number of nodes in any subtree connected to P. Then either there is a unique node of minimal weight, the centroid of the tree, or there is a unique pair of minimal weight nodes, the bicentroids.
Let T be a tree with root node R. If R and the edges incident with it are deleted, the resulting rooted trees are called branches. A primary branch (there can be at most one) has i nodes where n/2 <= i <= n-1.

F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1994; pp. 35, 36.

N. J. A. Sloane, Table of n, a(n) for n = 0..200
A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 266-268.
C. Jordan, Sur les assemblages des lignes, J. Reine angew. Math., 70 (1869), 185-190.
A. Meir and J. W. Moon, On the branch-sizes of rooted unlabeled trees, in "Graph Theory and Its Applications", Annals New York Acad. Sci., Vol. 576, 1989, pp. 399-407.
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. [This articles states incorrectly that A000676 and A000677 give the numbers of trees with respectively a centroid and bicentroid.]
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.)
Index entries for sequences related to rooted trees

Cf. A102911 (trees with a bicentroid), A027415 (trees with a primary branch), A000676 (trees with a center), A000677 (trees with a bicenter), A000055 (trees), A000081 (rooted trees).

N := 50: Y := [ 1,1 ]: for n from 3 to N do x*mul( (1-x^i)^(-Y[ i ]), i=1..n-1); series(%,x,n+1); b := coeff(%,x,n); Y := [ op(Y),b ]; od: P:=n->sum(Y[n-i]*Y[i],i=1..floor(n/2)): seq(Y[n]-P(n),n=1..35); # Emeric Deutsch, Nov 21 2004

a(n) = A000055(n) - A102911(n/2) if n is even, else a(n) = A000055(n).
a(n) = A000081(n) - A027415(n). - Emeric Deutsch, Nov 21 2004
a(n) = [x^n] 1 + x/Product_{i=1..ceiling(n/2)-1} (1-x^i)^A000081(i).  See Cayley link above. - Geoffrey Critzer, Jul 30 2022

More terms from Emeric Deutsch, Nov 21 2004

Entry revised (with new definition) by N. J. A. Sloane, Feb 26 2007

A027415 Number of rooted unlabeled trees on n nodes having a primary branch.

Original entry on oeis.org

0, 1, 1, 3, 6, 17, 37, 102, 239, 658, 1607, 4425, 11185, 30990, 80070, 222731, 586218, 1638333, 4370721, 12262003, 33077327, 93128828, 253454781, 715784848, 1962537755, 5557799401, 15332668869, 43527249088, 120716987723

Offset: 1

N. J. A. Sloane

nonn

Let T be a tree with root node R. If R and the edges incident with it are deleted, the resulting rooted trees are called branches. A primary branch (there can be at most one) has i nodes where n/2 <= i <= n-1.

A. Meir and J. W. Moon, On the branch-sizes of rooted unlabeled trees, in "Graph Theory and Its Applications", Annals New York Acad. Sci., Vol. 576, 1989, pp. 399-407. [MR 1110839]

N. J. A. Sloane, Table of n, a(n) for n = 1..200
Index entries for sequences related to rooted trees

This sequence + A027416 = A000081. Cf. A000081, A000055, A102911.

N := 50: Y := [ 1,1 ]: for n from 3 to N do x*mul( (1-x^i)^(-Y[ i ]), i=1..n-1); series(%,x,n+1); b := coeff(%,x,n); Y := [ op(Y),b ]; od: P:=n->sum(Y[n-i]*Y[i],i=1..floor(n/2)): seq(P(n),n=1..35); # Emeric Deutsch, Nov 21 2004

Let r(n) = A000081(n) = number of rooted trees on n nodes. Then a(n)=sum(r(n-i)*r(i), i=1..floor(n/2)) - Emeric Deutsch, Nov 21 2004. Comment from N. J. A. Sloane: The term r(n-i) gives the number of ways of picking the primary branch, while the term r(i) gives the number of ways of picking the rest of the tree including the root R.

More terms from Emeric Deutsch, Nov 21 2004

Entry revised by N. J. A. Sloane, Feb 26 2007

A283826 Irregular triangle read by rows: T(n,k) = number of trees on n nodes with radius k, n>=1, 1 <= k <= floor(n/2).

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 3, 1, 11, 10, 1, 1, 17, 25, 4, 1, 25, 61, 18, 1, 1, 36, 132, 61, 5, 1, 50, 277, 194, 28, 1, 1, 70, 554, 553, 117, 6, 1, 94, 1077, 1495, 451, 40, 1, 1, 127, 2034, 3823, 1552, 197, 7, 1, 168, 3770, 9427, 5020, 879, 54, 1, 1, 222, 6853, 22466, 15289, 3485, 305, 8, 1

Offset: 1

N. J. A. Sloane, Mar 19 2017

The radius of a tree is the maximal distance of a node from the center.

			Triangle begins:
  0,
  1,
  1,
  1,  1,
  1,  2,
  1,  4,   1,
  1,  7,   3,
  1, 11,  10,   1,
  1, 17,  25,   4,
  1, 25,  61,  18,  1,
  1, 36, 132,  61,  5,
  1, 50, 277, 194, 28, 1,
  ...

Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 8 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Cf. A283827.

See also A000676, A000677, A027416, A102911, A004250 (column 2?), A000055 (row sums).

T(n,k) = A034853(n,2k-1) + A034853(n,2k). - R. J. Mathar, Apr 03 2017

A283827 Irregular triangle read by rows: T(n,k) = number of trees on n nodes with load k, n>=1, 1 <= k <= floor(n/2).

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 3, 7, 1, 3, 9, 10, 1, 4, 12, 30, 1, 4, 18, 38, 45, 1, 5, 21, 64, 144, 1, 5, 27, 91, 217, 210

Offset: 1

N. J. A. Sloane, Mar 19 2017

The load of a tree is the maximal branch weight from the centroid.

			Triangle begins:
  0,
  1,
  1,
  1, 1,
  1, 2,
  1, 2,  3,
  1, 3,  7,
  1, 3,  9, 10,
  1, 4, 12, 30,
  1, 4, 18, 38,  45,
  1, 5, 21, 64, 144,
  1, 5, 27, 91, 217, 210,
  ...

Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 8 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

Cf. A283826.

See also A000676, A000677, A027416, A102911.

A338859 Square array A(m,k) is the number of unicyclic graphs with m trees of k nodes; m,k >= 0, read by falling antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 4, 3, 1, 1, 0, 1, 9, 10, 4, 1, 1, 0, 1, 20, 45, 20, 6, 1, 1, 0, 1, 48, 210, 165, 55, 8, 1, 1, 0, 1, 115, 1176, 1540, 1035, 136, 13, 1, 1, 0, 1, 286, 6670, 19600, 22155, 6273, 430, 18, 1, 1, 0, 1, 719, 41041, 260130, 692076, 324008, 46185, 1300, 30, 1, 1, 0

Offset: 0

Washington Bomfim, Nov 24 2020

The number of unicyclic graphs with m k-trees is equal to the number of bracelets with m beads using up to A000081(k) colors, so A(m,k) = A321791(m, A000081(k)).
Because A102911(k) is the number of graphs constituted by 2 k-node rooted trees with the roots joined by an edge, A(2,k) = A102911(k). [Bomfim illustration for k=2,3].
Column 1 refers to Cyclic graphs, Column 2 refers to Sunlet graphs.

			A begins,
---+------------------------------------------------------------------------------
m/k|0 1 2  3    4      5        6           7              8                 9
---+------------------------------------------------------------------------------
0  |1 1 1  1    1      1        1           1              1                 1 ...
1  |0 1 1  2    4      9       20          48            115               286 ...
2  |0 1 1  3   10     45      210        1176           6670             41041 ...
3  |0 1 1  4   20    165     1540       19600         260130           3939936 ...
4  |0 1 1  6   55   1035    22155      692076       22247785         842202361 ...
5  |0 1 1  8  136   6273   324008    25535712     2012117671      191362445560 ...
6  |0 1 1 13  430  46185  5376070  1020580232   192799298140    45606942211831 ...
7  |0 1 1 18 1300 344925 91508580 41936107248 19000229453710 11179807512382366 ...
...|           ...            ...            ...            ...            ...
---+------------------------------------------------------------------------------
The A(3,3) = 4 unicyclic graphs with 3 trees of 3 nodes
         0                                  0
         |                                  |
         0                0   0             0             0   0
         |                 \ /              |              \ /
         0                  0               0               0
        /*\                /*\             /*\             /*\
       /***\              /***\           /***\           /***\
      0-----0            0---- 0         0-----0         0-----0
     /       \          / \   / \       / \   / \        |     |
    0         0        0   0 0   0     0   0 0   0       0     0
   /           \                                         |     |
  0             0                                        0     0
The graphs above are also representations of bracelets with m = 3 beads using up to A000081(k=3) = 2 colors.

Index entries for sequences related to bracelets
Washington Bomfim, Illustraction of graphs counted by A(2,k), k=2,3
Eric Weisstein's World of Mathematics, Sunlet graph

Cf. A000081 (row 1), A321791, A102911 (row 2), A000029 (column 3), A032275 (column 4).

\\ From Robert A. Russell formula of A321791.
A(m, k)={ if( m == 0, return(1),
(k^((m+1)>>1)+k^ceil((m+1)/2)) / 4 + sumdiv(m, d, eulerphi(d)*k^(m/d) )/(m<<1)) };
seq(max_m) = { my(f = vector(max_m), kk, mm, ff); f[1] = 1;
for(j=1, max_m - 1, f[j+1] = 1/j * sum(k=1, j, sumdiv(k, d, d * f[d]) * f[j-k+1]));
print1(A(0,0) ", "); for(k = 1, max_m, kk = k; mm = 0; ff = f[kk];
until(A(mm,ff)==0, print1(A(mm,ff)", "); mm++; kk--; if(kk==0, ff=0, ff = f[kk]) );
print1("0, ")) };

A(m,k) = A321791(m, A000081(k)).

A356186 Number of labeled trees on [2n] with a bicentroid.

Original entry on oeis.org

0, 1, 12, 810, 143360, 49218750, 27935373312, 23751648836916, 28301429298954240, 45046920790988254710, 92378000000000000000000, 237289687212632836205339916, 746430126201849206626773368832, 2822726846177838977566127355808300

Offset: 0

Geoffrey Critzer, Jul 31 2022

nonn

This sequence is the labeled version of A102911 where the pertinent definitions can be found.

			a(3) = 810.  In the illustrations by Sloane found in the link above, for n = 6, there are A102911(3) = 3 trees with a bicentroid: the first, second and last trees shown.  They have 360, 360, and 90 labelings respectively.  360 + 360 + 90 = 810.

N. J. A. Sloane, Illustration of initial terms

Cf. A102911, A000984, A000169.

Prepend[Table[Binomial[2 n, n] n^(n - 1) n^(n - 1)/2, {n, 1, 12}], 0]

a(n) = binomial(2n,n)*n^(2n-2)/2 = A000984(n)*A000169(n)^2/2.

cp's OEIS Frontend

A000676 Number of centered trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A027416 Number of unlabeled (and unrooted) trees on n nodes having a centroid.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A027415 Number of rooted unlabeled trees on n nodes having a primary branch.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A283826 Irregular triangle read by rows: T(n,k) = number of trees on n nodes with radius k, n>=1, 1 <= k <= floor(n/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A283827 Irregular triangle read by rows: T(n,k) = number of trees on n nodes with load k, n>=1, 1 <= k <= floor(n/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A338859 Square array A(m,k) is the number of unicyclic graphs with m trees of k nodes; m,k >= 0, read by falling antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A356186 Number of labeled trees on [2n] with a bicentroid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula