A244372 -id:A244372 - cp's OEIS frontend

A299038 Number A(n,k) of rooted trees with n nodes where each node has at most k children; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 0, 1, 1, 1, 2, 3, 1, 0, 1, 1, 1, 2, 4, 6, 1, 0, 1, 1, 1, 2, 4, 8, 11, 1, 0, 1, 1, 1, 2, 4, 9, 17, 23, 1, 0, 1, 1, 1, 2, 4, 9, 19, 39, 46, 1, 0, 1, 1, 1, 2, 4, 9, 20, 45, 89, 98, 1, 0, 1, 1, 1, 2, 4, 9, 20, 47, 106, 211, 207, 1, 0

Offset: 0

Alois P. Heinz, Feb 01 2018

			Square array A(n,k) begins:
  1, 1,   1,   1,   1,   1,   1,   1,   1,   1,   1, ...
  1, 1,   1,   1,   1,   1,   1,   1,   1,   1,   1, ...
  0, 1,   1,   1,   1,   1,   1,   1,   1,   1,   1, ...
  0, 1,   2,   2,   2,   2,   2,   2,   2,   2,   2, ...
  0, 1,   3,   4,   4,   4,   4,   4,   4,   4,   4, ...
  0, 1,   6,   8,   9,   9,   9,   9,   9,   9,   9, ...
  0, 1,  11,  17,  19,  20,  20,  20,  20,  20,  20, ...
  0, 1,  23,  39,  45,  47,  48,  48,  48,  48,  48, ...
  0, 1,  46,  89, 106, 112, 114, 115, 115, 115, 115, ...
  0, 1,  98, 211, 260, 277, 283, 285, 286, 286, 286, ...
  0, 1, 207, 507, 643, 693, 710, 716, 718, 719, 719, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=1-11 give: A000012, A001190(n+1), A000598, A036718, A036721, A036722, A182378, A292553, A292554, A292555, A292556.
Main diagonal gives A000081 for n>0.
A(2n,n) gives A299039.
Cf. A244372.

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:
A:= (n, k)-> `if`(n=0, 1, b(n-1$2, k$2)):
seq(seq(A(n, d-n), n=0..d), d=0..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]}]]];
A[n_, k_] := If[n == 0, 1, b[n - 1, n - 1, k, k]];
Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jun 04 2018, from Maple *)

from sympy import binomial
from sympy.core.cache import cacheit
@cacheit
def b(n, i, t, k): return 1 if n==0 else 0 if i<1 else sum([binomial(b(i-1, i-1, k, k)+j-1, j)*b(n-i*j, i-1, t-j, k) for j in range(min(t, n//i)+1)])
def A(n, k): return 1 if n==0 else b(n-1, n-1, k, k)
for d in range(15): print([A(n, d-n) for n in range(d+1)]) # Indranil Ghosh, Mar 02 2018, after Maple code

A(n,k) = Sum_{i=0..k} A244372(n,i) for n>0, A(0,k) = 1.

A036718 Number of rooted trees where each node has at most 4 children.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 19, 45, 106, 260, 643, 1624, 4138, 10683, 27790, 72917, 192548, 511624, 1366424, 3666930, 9881527, 26730495, 72556208, 197562840, 539479354, 1477016717, 4053631757, 11149957667, 30732671572, 84871652538, 234802661446, 650684226827

Offset: 0

N. J. A. Sloane

			From _Joerg Arndt_, Feb 25 2017: (Start)
The a(5) = 9 rooted trees with 5 nodes and out-degrees <= 4 are:
:         level sequence    out-degrees (dots for zeros)
:     1:  [ 0 1 2 3 4 ]    [ 1 1 1 1 . ]
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]    [ 1 1 2 . . ]
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]    [ 1 2 1 . . ]
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]    [ 2 1 1 . . ]
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]    [ 1 3 . . . ]
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]    [ 2 2 . . . ]
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]    [ 2 1 . 1 . ]
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]    [ 3 1 . . . ]
:  O--o--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 ]    [ 4 . . . . ]
:  O--o
:  .--o
:  .--o
:  .--o
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. R. Bremner and H. A. Eigendy, Alternating quaternary algebra structures on irreducible representations of sl_2(C), Lin. Alg. Applic. 433 (2010) 1686-1705.
F. Ruskey, Information on Rooted Trees

Cf. A000081, A036717, A036719, A036720, A036721, A036722, A182378, A244372.
Cf. A292553, A292554, A292555, A292556.
Column k=4 of A299038.

A := 1; f := proc(n) global A; local A2,A3,A4; A2 := subs(x=x^2,A); A3 := subs(x=x^3,A); A4 := subs(x=x^4,A);
coeff(series( 1+x*( (A^4+3*A2^2+8*A*A3+6*A^2*A2+6*A4)/2 ), x, n+1), x,n); end;
for n from 1 to 50 do A := series(A+f(n)*x^n,x,n +1); od: A;

a = 1; f[n_] := Module[{a2, a3, a4}, a2 = a /. x -> x^2; a3 = a /. x -> x^3; a4 = a /. x -> x^4; Coefficient[ Series[ 1 + x*(a^4 + 3*a2^2 + 8*a*a3 + 6*a^2*a2 + 6*a4)/24, {x, 0, n + 1}] // Normal, x, n]]; For[n = 1, n <= 30, n++, a = Series[a + f[n]*x^n, {x, 0, n + 1}] // Normal]; CoefficientList[a, x] (* Jean-François Alcover, Jan 16 2013, after Maple *)
b[0, i_, t_, k_] = 1; m = 4; (* m = maximum children *)
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]}]];
PrependTo[Table[b[n-1, n-1, m, m], {n, 1, 30}], 1] (* Robert A. Russell, Dec 27 2022 *)

G.f. satisfies A(x) = 1 + x*cycle_index(Sym(4), A(x)).
a(n) = Sum_{j=1..4} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 19 2017
a(n) / a(n+1) ~ 0.343520104570489046632074698738792654644751898257681287407149... - Robert A. Russell, Feb 11 2023

Better description from Frank Ruskey, Sep 23 2000

A036722 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(6), A(x)).

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 48, 114, 283, 710, 1816, 4690, 12267, 32338, 85978, 230080, 619521, 1676808, 4560286, 12454272, 34143682, 93928091, 259208006, 717375068, 1990625390, 5537142610, 15436744525, 43124847431, 120708508008, 338477040445, 950714584576

Offset: 0

N. J. A. Sloane

nonn

a(n) is also the number of rooted trees where each node has at most 6 children. [Patrick Devlin, Apr 29 2012]

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000081, A036717, A036718, A036719, A036720, A036721, A182378, A244372, A292553, A292554, A292555, A292556.

Column k=6 of A299038.

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:
a:= n-> `if`(n=0, 1, b(n-1$2, 6$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 20 2017

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]}]]];
a[n_] := If[n == 0, 1, b[n - 1, n - 1, 6, 6]];
Table[a[n] , {n, 0, 35}] // Flatten (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

a(n) = Sum_{j=1..6} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 19 2017

a(n) / a(n+1) ~ 0.338887196052856714304749078960983936661485522864792573284374... - Robert A. Russell, Feb 11 2023

A244454 Number T(n,k) of unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 7, 1, 0, 1, 0, 17, 2, 0, 0, 1, 0, 42, 4, 1, 0, 0, 1, 0, 105, 7, 2, 0, 0, 0, 1, 0, 267, 15, 2, 1, 0, 0, 0, 1, 0, 684, 28, 4, 2, 0, 0, 0, 0, 1, 0, 1775, 56, 7, 2, 1, 0, 0, 0, 0, 1, 0, 4639, 110, 12, 2, 2, 0, 0, 0, 0, 0, 1

Offset: 1

Joerg Arndt and Alois P. Heinz, Jun 28 2014

T(1,0) = 1 by convention.

Sum_{i=2..n-1} T(n,i) = A001678(n+1) for n>1.

			The A000081(5) = 9 rooted trees with 5 nodes sorted by minimal outdegree of inner nodes 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--- : ---4--- :
Thus row 5 = [0, 7, 1, 0, 1].
Triangle T(n,k) begins:
  1;
  0,    1;
  0,    1,   1;
  0,    3,   0,  1;
  0,    7,   1,  0, 1;
  0,   17,   2,  0, 0, 1;
  0,   42,   4,  1, 0, 0, 1;
  0,  105,   7,  2, 0, 0, 0, 1;
  0,  267,  15,  2, 1, 0, 0, 0, 1;
  0,  684,  28,  4, 2, 0, 0, 0, 0, 1;
  0, 1775,  56,  7, 2, 1, 0, 0, 0, 0, 1;
  0, 4639, 110, 12, 2, 2, 0, 0, 0, 0, 0, 1;

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

Columns k=0-10 give: A063524, A244455, A244456, A244457, A244458, A244459, A244460, A244461, A244462, A244463, A244464.
Row sums give A000081.
Cf. A001678, A244372, A244530 (ordered unlabeled rooted trees).

b:= proc(n, i, t, k) option remember; `if`(n=0, `if`(t in [0, k],
      1, 0), `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
      b(n-i*j, i-1, max(0, t-j), k), j=0..n/i)))
    end:
T:= (n, k)-> b(n-1$2, k$2) -`if`(n=1 and 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, If[t == 0 || t == k, 1, 0], If[i<1, 0, Sum[Binomial[b[i-1, i-1, k, k]+j-1, j]* b[n-i*j, i-1, Max[0, t-j], k], {j, 0, n/i}]]]; T[n_, k_] := b[n-1, n-1, k, k] - If[n == 1 && 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, Jan 08 2015, translated from Maple *)

A036721 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(5), A(x)).

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 47, 112, 277, 693, 1766, 4547, 11852, 31146, 82534, 220149, 590834, 1593951, 4320723, 11761394, 32138301, 88121176, 242383729, 668607115, 1849194691, 5126800907, 14245679652, 39666239726, 110661514973, 309280533011, 865839831118

Offset: 0

N. J. A. Sloane

nonn

Also the number of rooted trees where each node has at most 5 children. [Patrick Devlin, Apr 30 2012]

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Joerg Arndt, The a(6) = 20 rooted trees with 5 nodes and out-degrees <= 5

Cf. A000081, A036717, A036718, A036719, A036720, A036722, A182378, A244372, A292553, A292554, A292555, A292556.

Column k=5 of A299038.

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:
a:= n-> `if`(n=0, 1, b(n-1$2, 5$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 20 2017

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]}]]];
a[n_] := If[n == 0, 1, b[n - 1, n - 1, 5, 5]];
Table[a[n], {n, 0, 35}] // Flatten (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

a(n) = Sum_{j=1..5} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 19 2017

a(n) / a(n+1) ~ 0.340017469151060086823930137816585262710976835711484267209811... - Robert A. Russell, Feb 11 2023

A292085 Number A(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes or outdegrees larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 2, 0, 1, 1, 2, 4, 3, 0, 1, 1, 2, 5, 9, 6, 0, 1, 1, 2, 5, 11, 23, 11, 0, 1, 1, 2, 5, 12, 30, 58, 23, 0, 1, 1, 2, 5, 12, 32, 80, 156, 46, 0, 1, 1, 2, 5, 12, 33, 87, 228, 426, 98, 0, 1, 1, 2, 5, 12, 33, 89, 251, 656, 1194, 207, 0

Offset: 1

Alois P. Heinz, Sep 08 2017

			:               T(4,3) = 4             :
:                                      :
:       o       o         o       o    :
:      / \     / \       / \     /|\   :
:     o   N   o   o     o   N   o N N  :
:    / \     ( ) ( )   /|\     ( )     :
:   o   N    N N N N  N N N    N N     :
:  ( )                                 :
:  N N                                 :
:                                      :
Square array A(n,k) begins:
  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,   2,   2,   2,   2,   2,   2, ...
  0,  2,   4,   5,   5,   5,   5,   5, ...
  0,  3,   9,  11,  12,  12,  12,  12, ...
  0,  6,  23,  30,  32,  33,  33,  33, ...
  0, 11,  58,  80,  87,  89,  90,  90, ...
  0, 23, 156, 228, 251, 258, 260, 261, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Index entries for sequences related to rooted trees

Columns k=1-10 give: A063524, A001190, A268172, A292210, A292211, A292212, A292213, A292214, A292215, A292216.
Main diagonal gives A000669.
Cf. A244372, A288942, A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n

b[n_, i_, v_, k_] := b[n, i, v, k] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[v == n, 1, Sum[Binomial[A[i, k] + j - 1, j]*b[n - i*j, i - 1, v - j, k], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n < 2, n, Sum[b[n, n + 1 - j, j, k], {j, 2, Min[n, k]}]];
Table[Table[A[n, 1 + d - n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

A(n,k) = Sum_{j=1..k} A292086(n,j).

A292086 Number T(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that k is the maximum of 1 and the node outdegrees; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 6, 2, 1, 0, 6, 17, 7, 2, 1, 0, 11, 47, 22, 7, 2, 1, 0, 23, 133, 72, 23, 7, 2, 1, 0, 46, 380, 230, 77, 23, 7, 2, 1, 0, 98, 1096, 751, 256, 78, 23, 7, 2, 1, 0, 207, 3186, 2442, 861, 261, 78, 23, 7, 2, 1, 0, 451, 9351, 8006, 2897, 887, 262, 78, 23, 7, 2, 1

Offset: 1

Alois P. Heinz, Sep 08 2017

			:   T(4,2) = 2        :   T(4,3) = 2      : T(4,4) = 1 :
:                     :                   :            :
:       o       o     :      o       o    :     o      :
:      / \     / \    :     / \     /|\   :   /( )\    :
:     o   N   o   o   :    o   N   o N N  :  N N N N   :
:    / \     ( ) ( )  :   /|\     ( )     :            :
:   o   N    N N N N  :  N N N    N N     :            :
:  ( )                :                   :            :
:  N N                :                   :            :
:                     :                   :            :
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,   1;
  0,  2,   2,   1;
  0,  3,   6,   2,  1;
  0,  6,  17,   7,  2,  1;
  0, 11,  47,  22,  7,  2, 1;
  0, 23, 133,  72, 23,  7, 2, 1;
  0, 46, 380, 230, 77, 23, 7, 2, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Index entries for sequences related to rooted trees

Columns k=1-10 give: A063524, A001190 (for n>1), A292229, A292230, A292231, A292232, A292233, A292234, A292235, A292236.
Row sums give A000669.
Limit of reversed rows gives A292087.
Cf. A244372, A288942, A292085.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n, k)-`if`(k=1, 0, A(n, k-1)):
seq(seq(T(n, k), k=1..n), n=1..15);

b[n_, i_, v_, k_] := b[n, i, v, k] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[v == n, 1, Sum[Binomial[A[i, k] + j - 1, j]*b[n - i*j, i - 1, v - j, k], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n < 2, n, Sum[b[n, n + 1 - j, j, k], {j, 2, Min[n, k]}]];
T[n_, k_] := A[n, k] - If[k == 1, 0, A[n, k - 1]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 15}] // Flatten (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

T(n,k) = A292085(n,k) - A292085(n,k-1) for k>2, T(n,1) = A292085(n,1).

A292556 Number of rooted unlabeled trees on n nodes where each node has at most 11 children.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12485, 32970, 87802, 235355, 634771, 1720940, 4688041, 12824394, 35216524, 97039824, 268238379, 743596131, 2066801045, 5758552717, 16080588286, 44997928902, 126160000878, 354349643101, 996946927831

Offset: 0

Marko Riedel, Sep 18 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Marko Riedel, Trees with bounded degree.

Cf. A000081, A001190, A000598, A036718, A036721, A036722, A182378, A244372, A292553, A292554, A292555.

Column k=11 of A299038.

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:
a:= n-> `if`(n=0, 1, b(n-1$2, 11$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 20 2017

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]}]]];
a[n_] := If[n == 0, 1, b[n-1, n-1, 11, 11]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 05 2018, after Alois P. Heinz *)

Functional equation of g.f. is T(z) = z + z*Sum_{q=1..11} Z(S_q)(T(z)) with Z(S_q) the cycle index of the symmetric group.
Alternate FEQ is T(z) = 1 + z*Z(S_11)(T(z)).
a(n) = Sum_{j=1..11} A244372(n,j) for n > 0, a(0) = 1. - Alois P. Heinz, Sep 20 2017
Limit_{n->oo} a(n)/a(n+1) = 0.338324339068091181557475416836618315086769320447748735003402... - Robert A. Russell, Feb 11 2023

A292553 Number of rooted unlabeled trees on n nodes where each node has at most 8 children.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 48, 115, 286, 718, 1839, 4757, 12460, 32897, 87592, 234746, 633013, 1715851, 4673320, 12781759, 35093010, 96681705, 267199518, 740580555, 2058042803, 5733101603, 16006590851, 44782679547, 125533577578, 352525803976, 991634575368

Offset: 0

Marko Riedel, Sep 18 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Marko Riedel, Trees with bounded degree.
Marko Riedel, Maple code for sequences A001190, A000598, A036718, A036721, A036722, A182378, A292553, A292554, A292555, A292556 (FEQ 1).
Marko Riedel, Maple code for sequences A001190, A000598, A036718, A036721, A036722, A182378, A292553, A292554, A292555, A292556 (FEQ 2)
Marko Riedel, Maple code (FEQ 2) optimized for speed.

Cf. A000081, A001190, A000598, A036718, A036721, A036722, A182378, A244372, A292554, A292555, A292556.

Column k=8 of A299038.

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:
a:= n-> `if`(n=0, 1, b(n-1$2, 8$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 20 2017

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]}]]];
a[n_] := If[n == 0, 1, b[n - 1, n - 1, 8, 8]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

Functional equation of G.f. is T(z) = z + z*Sum_{q=1..8} Z(S_q)(T(z)) with Z(S_q) the cycle index of the symmetric group. Alternate FEQ is T(z) = 1 + z*Z(S_8)(T(z)).
a(n) = Sum_{j=1..8} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 20 2017
a(n) / a(n+1) ~ 0.338386042364849957035744926227166370702775721795018600630554... - Robert A. Russell, Feb 11 2023

A292554 Number of rooted unlabeled trees on n nodes where each node has at most 9 children.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1841, 4763, 12477, 32947, 87735, 235162, 634212, 1719325, 4683368, 12810871, 35177357, 96926335, 267909285, 742641309, 2064029034, 5750500663, 16057186086, 44929879114, 125962026154, 353773417487, 995269027339

Offset: 0

Marko Riedel, Sep 18 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Marko Riedel, Trees with bounded degree.

Cf. A000081, A001190, A000598, A036718, A036721, A036722, A182378, A244372, A292553, A292555, A292556.

Column k=9 of A299038.

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:
a:= n-> `if`(n=0, 1, b(n-1$2, 9$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 20 2017

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]}]]];
a[n_] := If[n == 0, 1, b[n - 1, n - 1, 9, 9]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

Functional equation of G.f. is T(z) = z + z*Sum_{q=1..9} Z(S_q)(T(z)) with Z(S_q) the cycle index of the symmetric group. Alternate FEQ is
T(z) = 1 + z*Z(S_9)(T(z)).
a(n) = Sum_{j=1..9} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 20 2017
a(n) / a(n+1) ~ 0.338343552789108712866488147828528012266693326385052387884853... - Robert A. Russell, Feb 11 2023

cp's OEIS Frontend

A299038 Number A(n,k) of rooted trees with n nodes where each node has at most k children; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A036718 Number of rooted trees where each node has at most 4 children.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A036722 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(6), A(x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A244454 Number T(n,k) of unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A036721 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(5), A(x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A292085 Number A(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes or outdegrees larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A292086 Number T(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that k is the maximum of 1 and the node outdegrees; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula