A244372 -id:A244372 - cp's OEIS frontend

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

1, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4765, 12483, 32964, 87785, 235305, 634628, 1720524, 4686842, 12820920, 35206475, 97010705, 268154003, 743351390, 2066090876, 5756490561, 16074597300, 44980514021, 126109353817, 354202275766, 996517941454

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, A292556.

Column k=10 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, 10$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, 10, 10]];
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..10} 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_10)(T(z)).
a(n) = Sum_{j=1..10} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 20 2017
a(n) / a(n+1) ~ 0.338329194566131211670667671160855741193081902868090986608524... - Robert A. Russell, Feb 11 2023

A182378 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(7), A(x)).

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 48, 115, 285, 716, 1833, 4740, 12410, 32754, 87176, 233547, 629540, 1705809, 4644231, 12697500, 34848694, 95973026, 265142431, 734606478, 2040683413, 5682634446, 15859800889, 44355531103, 124290064228, 348904212741, 981082979409

Offset: 0

Michael Burkhart, Apr 26 2012

nonn

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

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

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

Column k=7 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, 7$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, 7, 7]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jan 15 2018, after Alois P. Heinz *)

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

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

More terms from Patrick Devlin, Apr 29 2012

A244523 Irregular triangle read by rows: T(n,k) is the number of identity trees with n nodes and maximal branching factor k.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 2, 0, 1, 5, 0, 1, 10, 1, 0, 1, 21, 3, 0, 1, 42, 9, 0, 1, 87, 25, 0, 1, 178, 66, 2, 0, 1, 371, 170, 6, 0, 1, 773, 431, 21, 0, 1, 1630, 1076, 63, 0, 1, 3447, 2665, 185, 1, 0, 1, 7346, 6560, 512, 7, 0, 1, 15712, 16067, 1403, 26, 0, 1, 33790, 39219, 3750, 91, 0, 1, 72922, 95476, 9928, 291

Offset: 1

Joerg Arndt and Alois P. Heinz, Jul 30 2014

Row sums give A004111.

			Triangle starts:
01:  1,
02:  0, 1,
03:  0, 1,
04:  0, 1, 1,
05:  0, 1, 2,
06:  0, 1, 5,
07:  0, 1, 10, 1,
08:  0, 1, 21, 3,
09:  0, 1, 42, 9,
10:  0, 1, 87, 25,
11:  0, 1, 178, 66, 2,
12:  0, 1, 371, 170, 6,
13:  0, 1, 773, 431, 21,
14:  0, 1, 1630, 1076, 63,
15:  0, 1, 3447, 2665, 185, 1,
16:  0, 1, 7346, 6560, 512, 7,
17:  0, 1, 15712, 16067, 1403, 26,
18:  0, 1, 33790, 39219, 3750, 91,
19:  0, 1, 72922, 95476, 9928, 291,
20:  0, 1, 158020, 231970, 25969, 885, 3,
21:  0, 1, 343494, 562736, 67462, 2588, 15,
22:  0, 1, 749101, 1363640, 174039, 7373, 70,
23:  0, 1, 1638102, 3301586, 446884, 20555, 256,
24:  0, 1, 3591723, 7988916, 1142457, 56413, 884,
25:  0, 1, 7893801, 19322585, 2911078, 152812, 2840, 3,
...
The A004111(7) = 12 level-sequences and the branching sequences for the identity trees with 7 nodes are (dots for zeros), together with the maximal branching factors, are:
01:  [ . 1 2 3 4 5 6 ]    [ 1 1 1 1 1 1 . ]   1
02:  [ . 1 2 3 4 5 4 ]    [ 1 1 1 2 1 . . ]   2
03:  [ . 1 2 3 4 5 3 ]    [ 1 1 2 1 1 . . ]   2
04:  [ . 1 2 3 4 5 2 ]    [ 1 2 1 1 1 . . ]   2
05:  [ . 1 2 3 4 5 1 ]    [ 2 1 1 1 1 . . ]   2
06:  [ . 1 2 3 4 3 2 ]    [ 1 2 2 1 . . . ]   2
07:  [ . 1 2 3 4 3 1 ]    [ 2 1 2 1 . . . ]   2
08:  [ . 1 2 3 4 2 3 ]    [ 1 2 1 1 . 1 . ]   2
09:  [ . 1 2 3 4 2 1 ]    [ 2 2 1 1 . . . ]   2
10:  [ . 1 2 3 4 1 2 ]    [ 2 1 1 1 . 1 . ]   2
11:  [ . 1 2 3 2 1 2 ]    [ 2 2 1 . . 1 . ]   2
12:  [ . 1 2 3 1 2 1 ]    [ 3 1 1 . 1 . . ]   3
This gives row n=7: [0, 1, 10, 1, 0, 0, ... ].

Joerg Arndt and Alois P. Heinz, Rows n = 1..285, flattened

Columns k=0-10 give: A000007, A000012 (for n>0), A245747, A245748, A245749, A245750, A245751, A245752, A245753, A245754, A245755.

Cf. A004111 (identity trees), A244372 (unlabeled rooted trees by outdegree).

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)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
g:= proc(n) local k; if n=1 then 0 else
       for k while T(n, k)>0 do od; k-1 fi
    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..g(n)), n=1..25);

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]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]]]; g[n_] := If[ n == 1 , 0, For[k=1, T[n, k]>0 , k++]; k-1]; 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, g[n]}], {n, 1, 25}] // Flatten (* Jean-François Alcover, Feb 11 2015, after Maple *)

A244407 Number of unlabeled rooted trees with 2n nodes and maximal outdegree (branching factor) n.

Original entry on oeis.org

1, 2, 6, 17, 50, 143, 416, 1199, 3474, 10049, 29119, 84377, 244748, 710199, 2062274, 5991418, 17416401, 50652248, 147384676, 429043390, 1249508947, 3640449679, 10610613552, 30937605076, 90237313083, 263288153074, 768449666117, 2243530461067, 6552016136667

Offset: 1

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..100

Cf. A244372, A244410, A051491, A299039.

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-> b(2*n-1$2, n$2)-b(2*n-1$2, n-1$2):
seq(a(n), n=1..30);

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]}]] // FullSimplify] ; a[n_] := b[2*n - 1, 2 n - 1, n, n] - b[2*n - 1, 2 n - 1, n - 1, n - 1]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Feb 06 2015, after Maple *)

a(n) = A244372(2n,n).

a(n) ~ c * d^n / sqrt(n), where d = 2.955765285651994974714817524... is the Otter's rooted tree constant (see A051491), and c = 0.9495793... . - Vaclav Kotesovec, Jul 11 2014

A244399 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 3.

Original entry on oeis.org

1, 2, 6, 16, 43, 113, 300, 787, 2074, 5460, 14391, 37960, 100275, 265187, 702307, 1862463, 4945952, 13152441, 35023003, 93385548, 249330208, 666539949, 1784102735, 4781254117, 12828545419, 34459732110, 92668129050, 249469906115, 672296028786, 1813606782459

Offset: 4

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

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

Column k=3 of A244372.

Cf. A000598, A001190, A036656.

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-> b(n-1$2, 3$2) -`if`(k=0, 0, b(n-1$2, 2$2)):
seq(a(n), n=4..35);

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]}]]//FullSimplify]; a[n_] := b[n-1, n-1, 3, 3] - If[n == 0, 0, b[n-1, n-1, 2, 2]]; Table[a[n], {n, 4, 35}] (* Jean-François Alcover, Feb 09 2015, after Maple *)

a(n) = A000598(n) - A001190(n+1) = A000598(n) - A036656(n+1).

a(n) ~ c * d^n / n^(3/2), where d = 1/A261340 = 2.81546003317615... and c = 0.5178759064... . - Vaclav Kotesovec, Jun 27 2014

A244410 Number of unlabeled rooted trees with 2n+1 nodes and maximal outdegree (branching factor) n.

Original entry on oeis.org

1, 1, 5, 16, 49, 142, 415, 1198, 3473, 10048, 29118, 84376, 244747, 710198, 2062273, 5991417, 17416400, 50652247, 147384675, 429043389, 1249508946, 3640449678, 10610613551, 30937605075, 90237313082, 263288153073, 768449666116, 2243530461066, 6552016136666

Offset: 0

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

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

Cf. A244372, A244407, A051491.

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(2*n$2, n$2)-b(2*n$2, n-1$2)):
seq(a(n), n=0..30);

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]}]] // FullSimplify] ; a[n_] := If[n == 0, 1, b[2*n, 2 n, n, n] - b[2*n, 2 n, n - 1, n - 1]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 06 2015, after Maple *)

a(n) = A244372(2n+1,n).

a(n) ~ c * d^n / sqrt(n), where d = 2.955765285651994974714817524... is the Otter's rooted tree constant (see A051491), and c = 2.806733... . - Vaclav Kotesovec, Jul 11 2014

A244398 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 2.

Original entry on oeis.org

1, 2, 5, 10, 22, 45, 97, 206, 450, 982, 2178, 4849, 10904, 24630, 56010, 127911, 293546, 676156, 1563371, 3626148, 8436378, 19680276, 46026617, 107890608, 253450710, 596572386, 1406818758, 3323236237, 7862958390, 18632325318, 44214569099, 105061603968

Offset: 3

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

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

Column k=2 of A244372.

Cf. A001190, A036656, A086317, A086318.

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-> b(n-1$2, 2$2) -`if`(n=0, 0, 1):
seq(a(n), n=3..40);

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]}]] // FullSimplify]; a[n_] := b[n-1, n-1, 2, 2] - If[n == 0, 0, 1]; Table[a[n], {n, 3, 40}] (* Jean-François Alcover, Feb 09 2015, after Maple *)

a(n) = A001190(n+1)-1 = A036656(n+1)-1.

a(n) ~ c * d^n / n^(3/2), where d = 2.4832535361726368... = A086317 and c = 0.7916031835775118... = A086318. - Vaclav Kotesovec, Jun 27 2014

A244400 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 4.

Original entry on oeis.org

1, 2, 6, 17, 49, 136, 386, 1081, 3044, 8549, 24052, 67642, 190426, 536205, 1510920, 4259418, 12014682, 33907056, 95740913, 270468869, 764450150, 2161638413, 6115252839, 17307553766, 49005101669, 138811296158, 393351362321, 1115072623713, 3162183392471

Offset: 5

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

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

Column k=4 of A244372.

Cf. A000598, A036718.

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-> b(n-1$2, 4$2) -`if`(k=0, 0, b(n-1$2, 3$2)):
seq(a(n), n=5..40);

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]}]] // FullSimplify]; a[n_] := b[n-1, n-1, 4, 4] - If[n == 0, 0, b[n-1, n-1, 3, 3]]; Table[a[n], {n, 5, 40}] (* Jean-François Alcover, Feb 09 2015, after Maple *)

a(n) = A036718(n) - A000598(n).

A244401 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 5.

Original entry on oeis.org

1, 2, 6, 17, 50, 142, 409, 1169, 3356, 9617, 27601, 79210, 227527, 653793, 1879867, 5407806, 15564968, 44820889, 129127761, 372177974, 1073169150, 3095721985, 8933568154, 25789862435, 74477871565, 215155604291, 621754458752, 1797297119000, 5196966140656

Offset: 6

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

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

Column k=5 of A244372.

Cf. A036718, A036721.

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-> b(n-1$2, 5$2) -`if`(k=0, 0, b(n-1$2, 4$2)):
seq(a(n), n=6..40);

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]}]] // FullSimplify] ; a[n_] := b[n-1, n-1, 5, 5] - If[n == 0, 0, b[n-1, n-1, 4, 4]]; Table[a[n], {n, 6, 40}] (* Jean-François Alcover, Feb 09 2015, after Maple *)

a(n) = A036721(n) - A036718(n).

A244402 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 6.

Original entry on oeis.org

1, 2, 6, 17, 50, 143, 415, 1192, 3444, 9931, 28687, 82857, 239563, 692878, 2005381, 5806915, 16824277, 48767953, 141430699, 410341703, 1191064873, 3458607705, 10046993035, 29196507434, 84874753458, 246814998803, 717965190047, 2089140528083, 6080768466919

Offset: 7

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

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

Column k=6 of A244372.

Cf. A036721, A036722.

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-> b(n-1$2, 6$2) -`if`(k=0, 0, b(n-1$2, 5$2)):
seq(a(n), n=7..40);

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]}]] // FullSimplify] ; a[n_] := b[n - 1, n - 1, 6, 6] - If[n == 0, 0, b[n - 1, n - 1, 5, 5]]; Table[a[n], {n, 7, 40}] (* Jean-François Alcover, Feb 09 2015, after Maple *)

a(n) = A036722(n) - A036721(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A182378 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(7), A(x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A244523 Irregular triangle read by rows: T(n,k) is the number of identity trees with n nodes and maximal branching factor k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A244407 Number of unlabeled rooted trees with 2n nodes and maximal outdegree (branching factor) n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A244399 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 3.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A244410 Number of unlabeled rooted trees with 2n+1 nodes and maximal outdegree (branching factor) n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A244398 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A244400 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 4.

Views

Author

Keywords

Links

Crossrefs