A055290 -id:A055290 - cp's OEIS frontend

A055300 Matrix inverse of triangle A055290(n+1,k).

1, -1, 1, 0, -1, 1, 1, 0, -2, 1, 0, 1, 0, -2, 1, -3, 1, 4, 0, -3, 1, -1, -3, 2, 4, 0, -3, 1, 14, -10, -15, 4, 10, 0, -4, 1, 20, 11, -36, -12, 11, 9, 0, -4, 1, -77, 92, 76, -67, -56, 16, 20, 0, -5, 1, -308, 92, 421, -24, -200, -24, 30, 17, 0, -5, 1, 147, -994, 200, 847, 196

Offset: 2

Christian G. Bower, May 09 2000

			1; -1,1; 0,-1,1; 1,0,-2,1; 0,1,0,-2,1; ...

Index entries for sequences related to trees

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 18, 14, 5, 1, 0, 1, 12, 35, 39, 21, 6, 1, 0, 1, 16, 62, 97, 72, 30, 7, 1, 0, 1, 20, 103, 212, 214, 120, 40, 8, 1, 0, 1, 25, 161, 429, 563, 416, 185, 52, 9, 1, 0, 1, 30, 241, 804, 1344, 1268, 732, 270, 65, 10, 1, 0

Offset: 1

Christian G. Bower, May 09 2000

Harary denotes the g.f. as P(x, y) on page 33 "... , and let P(x,y) = Sum Sum P_{nm} x^ny^m where P_{nm} is the number of planted trees with n points and m endpoints, in which again the plant has not been counted either as a point or as an endpoint." - Michael Somos, Nov 02 2014

			From _Joerg Arndt_, Aug 18 2014: (Start)
Triangle starts:
01: 1
02: 1    0
03: 1    1    0
04: 1    2    1    0
05: 1    4    3    1    0
06: 1    6    8    4    1    0
07: 1    9   18   14    5    1    0
08: 1   12   35   39   21    6    1    0
09: 1   16   62   97   72   30    7    1    0
10: 1   20  103  212  214  120   40    8    1    0
11: 1   25  161  429  563  416  185   52    9    1    0
12: 1   30  241  804 1344 1268  732  270   65   10    1    0
13: 1   36  348 1427 2958 3499 2544 1203  378   80   11    1    0
...
The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
:     1:  [ 0 1 2 3 4 ]   1
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]   2
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]   2
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]   2
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]   3
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]   3
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]   2
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]   3
:  O--o--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 ]   4
:  O--o
:  .--o
:  .--o
:  .--o
:
This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
(End)
G.f. = x*(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*x^3 + y^4) + ...).

F. Harary, Recent results on graphical enumeration, pp. 29-36 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees

Row sums give A000081.
Columns 2 through 12: A002620(n-1), A055278-A055287.
Cf. A055288, A055289, A055290.
Cf. A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n],Count[#,{},{-2}]===k&]],{n,13},{k,n}] (* Gus Wiseman, Mar 19 2018 *)

{T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */

G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
G.f. satisfies A(x, y) = x*y - x + x * exp(Sum_{i>0} A(x^i, y^i) / i). [Harary, p. 34, equation (10)]. - Michael Somos, Nov 02 2014
Sum_k T(n, k) = A000081(n). - Michael Somos, Aug 24 2015

A003228 Endpoints in trees with n nodes.

Original entry on oeis.org

1, 2, 2, 5, 9, 21, 43, 101, 226, 556, 1333, 3365, 8500, 22007, 57258, 151264, 401761, 1077063, 2902599, 7871250, 21440642, 58672589, 161155637, 444240627, 1228400744, 3406668865, 9472308269, 26402207803, 73755064178

Offset: 1

N. J. A. Sloane

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson and A. J. Schwenk, The distribution of trees in a large random tree, Discr. Math., 12 (1975), 359-372.
Eric Weisstein's World of Mathematics, Tree Leaf.
Index entries for sequences related to trees

Cf. A000055, A003227, A055290, A055372.

a(n) = Sum_{k=1..n} k*c(n, k), where c(n, k) = A055290(n, k) has g.f. (1-x+x*y)*B(x, y)+(1/2)*(B(x^2, y^2)-B(x, y)^2) and B(x, y) is g.f. for A055372.

Corrected and extended with formula by Christian G. Bower, May 25 2000

A358107 Number of unlabeled trees covering 2n nodes, n+1 of which are leaves.

Original entry on oeis.org

1, 1, 2, 6, 26, 119, 626, 3495, 20688, 127339, 810418, 5293790, 35351571, 240478715, 1662071181, 11646620758, 82601643511, 592110678762, 4284830131865, 31271691087861, 229980550743717, 1703097703162249, 12691879796699486, 95129358337729084, 716801612475691847

Offset: 1

Gus Wiseman, Dec 02 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
Gus Wiseman, The a(4) = 6 trees covering 8 nodes, 5 of which are leaves.

Central column of A055290.
The labeled version is the central column of A055314.
For n leaves we have A359398.
A000272 counts trees, bisection A163395, unlabeled A000055.
A001187 counts connected graphs, unlabeled A001349.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A014068 counts graphs with n vertices and n-1 edges, unordered A001433.
Cf. A185650, A358732.

Terms a(11) and beyond from Andrew Howroyd, Jan 01 2023

A349703 Irregular triangle read by rows where T(n,k) is the number of free trees attaining the maximum terminal Wiener index (A349702) for a tree of n vertices among which k are leaves.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 5, 1, 2, 1, 1, 1, 1, 7, 1, 3, 1, 2, 1, 1, 1, 8, 1, 3, 1, 2, 1, 1, 1, 1, 10, 1, 4, 1, 3, 1, 2, 1, 1, 1, 12, 1, 4, 1, 3, 1, 2, 1, 1, 1, 1, 14, 1, 5, 1, 4, 1, 3, 1, 2, 1, 1, 1, 16, 1, 5, 1, 4, 1, 3, 1, 2, 1, 1, 1

Offset: 0

Kevin Ryde, Nov 26 2021

Gutman, Furtula, and Petrović determine the maximum terminal Wiener index (A349702) possible in trees, and construct the trees which attain this maximum.
The triangle rows are all possible n,k combinations, which means k=n in rows n=0..2, and k=2..n-1 in rows n>=3.
For k even, a unique tree has the maximum index.
For k=3, all trees have the same index.

			Triangle begins
      k=0  1  2  3  4  5  6  7  8
  n=0;  1,
  n=1;     1,
  n=2;        1,
  n=3;        1,
  n=4;        1, 1,
  n=5;        1, 1, 1,
  n=6;        1, 2, 1, 1,
  n=7;        1, 3, 1, 1, 1,
  n=8;        1, 4, 1, 2, 1, 1,
  n=9;        1, 5, 1, 2, 1, 1, 1,
For n=9,k=5, the T(9,5) = 2 trees are
  *--*--*--*--*--*     *--*--*--*--*--*
    /|         \         /   |      \
   * *          *       *    *       *

Kevin Ryde, Table of n, a(n) for n = 0..9593 (rows 0..140)
Ivan Gutman, Boris Furtula and Miroslav Petrović, Terminal Wiener Index, Journal of Mathematical Chemistry, volume 46, 2009, pages 522-531.

Cf. A349702 (maximum index), A055290 (count all trees), A001399 (trees k=3 leaves).

T(n,k) = if(n==1||k%2==0,1, k==3,(n-1)^2\/12, (n-k+1)>>1);

T(n,3) = A055290(n,3) = A001399(n-4) = round((n-1)^2 / 12).
T(n,k) = 1 for k even. [Gutman, Furtula, Petrović, theorem 4 (a)]
T(n,k) = ceiling((n-k)/2) for odd k >= 5. [Gutman, Furtula, Petrović, theorem 4 (b)]
G.f.: 1 + x*y + ( x^2*y^2 + ( x^4*y^3/(1-x^3) + x^5*y^4*(1+x*y-x^2)/(1-x^2*y^2) )/(1-x^2) )/(1-x).

A359398 Number of unlabeled trees covering 2n nodes, half of which are leaves.

Original entry on oeis.org

0, 1, 2, 8, 32, 158, 833, 4755, 28389, 176542, 1131055, 7432876, 49873477, 340658595, 2362652648, 16605707901, 118082160358, 848399575321, 6152038125538, 44981009272740, 331344933928536, 2457372361637286, 18337490246234464, 137612955519565773, 1038076541372187991

Offset: 1

Gus Wiseman, Jan 01 2023

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..100
Gus Wiseman, The a(4) = 8 trees covering 8 nodes, half of which are leaves.

Left of central column of A055290.
The labeled version is the left of central column of A055314.
The rooted version is A185650.
For n+1 leaves we have A358107.
The labeled version is A358732.
A000272 counts trees, bisection A163395, unlabeled A000055.
A001187 counts connected graphs, unlabeled A001349.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A014068 counts graphs with n vertices and n-1 edges, unlabeled A001433.

a(n) = A055290(2*n, n). - Andrew Howroyd, Jan 01 2023

Terms a(12) and beyond from Andrew Howroyd, Jan 01 2023

A055291 Number of trees with n nodes and 4 leaves.

Original entry on oeis.org

1, 2, 4, 8, 14, 23, 36, 54, 78, 110, 150, 201, 264, 341, 433, 544, 674, 827, 1004, 1209, 1443, 1711, 2013, 2355, 2738, 3167, 3643, 4173, 4757, 5402, 6109, 6885, 7731, 8655, 9657, 10746, 11923, 13196, 14566, 16043, 17627, 19328, 21147, 23094

Offset: 5

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 5..250
Index entries for sequences related to trees

Column 4 of A055290.

G.f.: x^5(x^5+x^3+1)/[(1-x^3)(1+x^2)(1-x^2)^2(1-x)^2].

A055292 Number of trees with n nodes and 5 leaves.

Original entry on oeis.org

1, 2, 6, 14, 32, 64, 123, 219, 377, 616, 978, 1496, 2236, 3251, 4637, 6475, 8899, 12025, 16036, 21091, 27432, 35271, 44920, 56656, 70873, 87924, 108298, 132438, 160943, 194358, 233408, 278755, 331266, 391737, 461193, 540581, 631103

Offset: 6

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 6..250
Index entries for sequences related to trees

Column 5 of A055290.

A055293 Number of trees with n nodes and 6 leaves.

Original entry on oeis.org

1, 3, 9, 26, 66, 158, 350, 727, 1428, 2679, 4804, 8308, 13888, 22539, 35606, 54935, 82907, 122712, 178375, 255085, 359304, 499179, 684621, 927943, 1243918, 1650519, 2169112, 2825336, 3649246, 4676552, 5948727, 7514406, 9429698

Offset: 7

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 7..250
Index entries for sequences related to trees

Column 6 of A055290.

A055294 Number of trees with n nodes and 7 leaves.

Original entry on oeis.org

1, 3, 12, 39, 119, 325, 833, 1972, 4411, 9318, 18789, 36248, 67361, 120868, 210354, 355873, 587070, 946127, 1493015, 2310430, 3512236, 5251416, 7732998, 11226380, 16084556, 22762426, 31844621, 44072033, 60380915, 81940412

Offset: 8

Christian G. Bower, May 09 2000

nonn

Georg Fischer, Table of n, a(n) for n = 8..250
Index entries for sequences related to trees

Column 7 of A055290.

cp's OEIS Frontend

A055300 Matrix inverse of triangle A055290(n+1,k).

Views

Author

Keywords

Examples

Links

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A003228 Endpoints in trees with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A358107 Number of unlabeled trees covering 2n nodes, n+1 of which are leaves.

Views

Author

Keywords

Links

Crossrefs

Extensions

A349703 Irregular triangle read by rows where T(n,k) is the number of free trees attaining the maximum terminal Wiener index (A349702) for a tree of n vertices among which k are leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A359398 Number of unlabeled trees covering 2n nodes, half of which are leaves.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A055291 Number of trees with n nodes and 4 leaves.

Views

Author

Keywords

Links

Crossrefs

Formula

A055292 Number of trees with n nodes and 5 leaves.

Views

Author

Keywords

Links

Crossrefs

A055293 Number of trees with n nodes and 6 leaves.

Views

Author

Keywords

Links

Crossrefs

A055294 Number of trees with n nodes and 7 leaves.

Views

Author

Keywords

Links

Crossrefs