A244399 -id:A244399 - cp's OEIS frontend

A244372 Number T(n,k) of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 2, 1, 0, 1, 10, 6, 2, 1, 0, 1, 22, 16, 6, 2, 1, 0, 1, 45, 43, 17, 6, 2, 1, 0, 1, 97, 113, 49, 17, 6, 2, 1, 0, 1, 206, 300, 136, 50, 17, 6, 2, 1, 0, 1, 450, 787, 386, 142, 50, 17, 6, 2, 1, 0, 1, 982, 2074, 1081, 409, 143, 50, 17, 6, 2, 1

Offset: 1

Joerg Arndt and Alois P. Heinz, Jun 26 2014

			The A000081(5) = 9 rooted trees with 5 nodes sorted by maximal outdegree are:
:  o  :   o     o     o       o     o   :   o     o   :    o    :
:  |  :   |     |    / \     / \   / \  :   |    /|\  :  /( )\  :
:  o  :   o     o   o   o   o   o o   o :   o   o o o : o o o o :
:  |  :   |    / \  |      / \    |   | :  /|\  |     :         :
:  o  :   o   o   o o     o   o   o   o : o o o o     :         :
:  |  :  / \  |     |                   :             :         :
:  o  : o   o o     o                   :             :         :
:  |  :                                 :             :         :
:  o  :                                 :             :         :
:     :                                 :             :         :
: -1- : ---------------2--------------- : -----3----- : ---4--- :
Thus row 5 = [0, 1, 5, 2, 1].
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,   1;
  0,  1,   2,    1;
  0,  1,   5,    2,    1;
  0,  1,  10,    6,    2,   1;
  0,  1,  22,   16,    6,   2,   1;
  0,  1,  45,   43,   17,   6,   2,  1;
  0,  1,  97,  113,   49,  17,   6,  2,  1;
  0,  1, 206,  300,  136,  50,  17,  6,  2,  1;
  0,  1, 450,  787,  386, 142,  50, 17,  6,  2,  1;
  0,  1, 982, 2074, 1081, 409, 143, 50, 17,  6,  2,  1;

Alois P. Heinz, Rows n = 1..141, flattened

Columns k=2-10 give: A244398, A244399, A244400, A244401, A244402, A244403, A244404, A244405, A244406.
T(2n,n) gives A244407(n).
T(2n+1,n) gives A244410(n).
Row sum give A000081.
Cf. A244454.

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
T:= (n, k)-> b(n-1$2, k$2) -`if`(k=0, 0, b(n-1$2, k-1$2)):
seq(seq(T(n, k), k=0..n-1), n=1..14);

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, 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]}]]]; T[n_, k_] := b[n-1, n-1, k, k] - If[k == 0, 0, b[n-1, n-1, k-1, k-1]]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Jul 01 2014, translated from Maple *)

A261340 Decimal expansion of the radius of convergence of the generating function of A000598, the number of rooted ternary trees of n vertices.

Original entry on oeis.org

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

Offset: 0

Jean-François Alcover, Aug 15 2015

			0.35518174231437739288224447364763263670874695417532...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.6 Otter's tree enumeration constants, p. 298.

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; p. 478.

Cf. A000598, A000642, A002094, A121331, A244399.

digits = 97; m = 2 digits + 10; For[gf = 0; i = 0, i <= m, i++, gf = Series[1 + x*(gf^3/6 + (gf /. x -> x^2)*gf/2 + (gf /. x -> x^3)/3), {x, 0, m + 1}] // Normal];
g[r_] := Module[{r2, r3, X, ym}, r2 = gf /. x -> r^2; r3 = gf /. x -> r^3; X[y_] = (y - 1)/(y^3/6 + r2*y/2 + r3/3); ym = y /. FindRoot[X'[y] == 0, {y, 2}, WorkingPrecision -> digits + 5]; X[ym]]; rho = FixedPoint[g, 1/3, SameTest -> (Abs[#1 - #2] < 10^-digits &)]; RealDigits[rho, 10, digits] // First

More digits from Vaclav Kotesovec, Aug 15 2015

More digits and Mma code updated by Jean-François Alcover, Apr 18 2016

cp's OEIS Frontend

A244372 Number T(n,k) of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica