A318753 -id:A318753 - cp's OEIS frontend

A032305 Number of rooted trees where any 2 subtrees extending from the same node have a different number of nodes.

1, 1, 1, 2, 3, 6, 12, 25, 51, 111, 240, 533, 1181, 2671, 6014, 13795, 31480, 72905, 168361, 393077, 914784, 2150810, 5040953, 11914240, 28089793, 66702160, 158013093, 376777192, 896262811, 2144279852, 5120176632, 12286984432, 29428496034, 70815501209

Offset: 1

Christian G. Bower

nonn

			The a(6) = 6 fully unbalanced trees: (((((o))))), (((o(o)))), ((o((o)))), (o(((o)))), (o(o(o))), ((o)((o))). - _Gus Wiseman_, Jan 10 2018

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Gus Wiseman, Illustration of the first 8 terms of A032305.
Index entries for sequences related to rooted trees

Cf. A000081, A001678, A003238, A004111, A213920, A273873, A290689, A291443, A297571.

Column k=1 of A318753.

A:= proc(n) if n<=1 then x else convert(series(x* (product(1+ coeff(A(n-1), x,i)*x^i, i=1..n-1)), x=0, n+1), polynom) fi end: a:= n-> coeff(A(n), x,n): seq(a(n), n=1..31);  # Alois P. Heinz, Aug 22 2008
# second Maple program:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(`if`(j=0, 1, g((i-1)$2))*g(n-i*j, i-1), j=0..min(1, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=1..35);  # Alois P. Heinz, Mar 04 2013

nn=30;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0 == Series[f[x]-x Product[1+a[i]x^i,{i,1,nn}],{x,0,nn}],x];Table[a[n],{n,1,nn}]/.sol  (* Geoffrey Critzer, Nov 17 2012 *)
allnim[n_]:=If[n===1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[allnim/@c]],UnsameQ@@(Count[#,_List,{0,Infinity}]&/@#)&]]/@IntegerPartitions[n-1]];
Table[Length[allnim[n]],{n,15}] (* Gus Wiseman, Jan 10 2018 *)
g[n_, i_] := g[n, i] = If[n == 0, 1, If[i < 1, 0,
     Sum[If[j == 0, 1, g[i-1, i-1]]*g[n-i*j, i-1], {j, 0, Min[1, n/i]}]]];
a[n_] := g[n-1, n-1];
Array[a, 35] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

a(n)=polcoeff(x*prod(i=1,n-1,1+a(i)*x^i)+x*O(x^n),n)

Shifts left under "EFK" (unordered, size, unlabeled) transform.
G.f.: A(x) = x*Product_{n>=1} (1+a(n)*x^n) = Sum_{n>=1} a(n)*x^n. - Paul D. Hanna, Apr 07 2004
Lim_{n->infinity} a(n)^(1/n) = 2.5119824... - Vaclav Kotesovec, Nov 20 2019
G.f.: x * exp(Sum_{n>=1} Sum_{k>=1} (-1)^(k+1) * a(n)^k * x^(n*k) / k). - Ilya Gutkovskiy, Jun 30 2021

A318754 Number T(n,k) of rooted trees with n nodes such that k equals the maximal number of subtrees extending from the same node and having the same number of nodes; 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, 2, 1, 1, 0, 3, 4, 1, 1, 0, 6, 9, 3, 1, 1, 0, 12, 22, 9, 3, 1, 1, 0, 25, 54, 23, 8, 3, 1, 1, 0, 51, 139, 60, 23, 8, 3, 1, 1, 0, 111, 346, 166, 61, 22, 8, 3, 1, 1, 0, 240, 892, 447, 167, 61, 22, 8, 3, 1, 1, 0, 533, 2290, 1219, 461, 168, 60, 22, 8, 3, 1, 1

Offset: 1

Alois P. Heinz, Sep 02 2018

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k < n. T(n,k) = 0 for k >= n.

			Triangle T(n,k) begins:
  1;
  0,   1;
  0,   1,   1;
  0,   2,   1,   1;
  0,   3,   4,   1,  1;
  0,   6,   9,   3,  1,  1;
  0,  12,  22,   9,  3,  1, 1;
  0,  25,  54,  23,  8,  3, 1, 1;
  0,  51, 139,  60, 23,  8, 3, 1, 1;
  0, 111, 346, 166, 61, 22, 8, 3, 1, 1;

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

Columns k=0-10 give: A063524, A032305 (for n>1), A318817, A318818, A318819, A318820, A318821, A318822, A318823, A318824, A318825.
Row sums give A000081.
T(2n+2,n+1) give A255705.
Cf. A318753.

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

g[n_, i_, k_] := g[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[g[i - 1, i - 1, k] + j - 1, j]*g[n - i*j, i - 1, k], {j, 0, Min[k, n/i]}]]];
T[n_, k_] := g[n - 1, n - 1, k] - If[k == 0, 0, g[n - 1, n - 1, k - 1]];
Table[T[n, k], {n, 1, 14}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, May 27 2019, after Alois P. Heinz *)

T(n,k) = A318753(n,k) - A318753(n,k-1) for k > 0, A(n,0) = A063524(n).

A318757 Number A(n,k) of rooted trees with n nodes such that no more than k isomorphic subtrees extend from the same node; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 2, 3, 3, 0, 0, 1, 1, 2, 4, 7, 6, 0, 0, 1, 1, 2, 4, 8, 15, 12, 0, 0, 1, 1, 2, 4, 9, 18, 34, 25, 0, 0, 1, 1, 2, 4, 9, 19, 43, 79, 52, 0, 0, 1, 1, 2, 4, 9, 20, 46, 102, 190, 113, 0, 0, 1, 1, 2, 4, 9, 20, 47, 110, 250, 459, 247, 0

Offset: 0

Alois P. Heinz, Sep 02 2018

			Square array A(n,k) begins:
  0,  0,  0,   0,   0,   0,   0,   0,   0, ...
  1,  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,  2,   2,   2,   2,   2,   2,   2, ...
  0,  2,  3,   4,   4,   4,   4,   4,   4, ...
  0,  3,  7,   8,   9,   9,   9,   9,   9, ...
  0,  6, 15,  18,  19,  20,  20,  20,  20, ...
  0, 12, 34,  43,  46,  47,  48,  48,  48, ...
  0, 25, 79, 102, 110, 113, 114, 115, 115, ...

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

Columns k=0-10 give: A063524, A004111, A248869, A318850, A318851, A318852, A318853, A318854, A318855, A318856, A318857.
Main diagonal gives A000081.
Cf. A318753, A318758.

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

h[n_, m_, t_, k_] := h[n, m, t, k] = If[m == 0, Binomial[n + t, t], If[n == 0, 0, Sum[h[n - 1, m - j, t + 1, k], {j, 1, Min[k, m]}]]];
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, i - 1, k]*h[A[i, k], j, 0, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n, b[n - 1, n - 1, k]];
Table[A[n, d - n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 11 2019, after Alois P. Heinz *)

A(n,k) = Sum_{j=0..k} A318758(n,j) for n > 0.

A(n,n+j) = A000081(n) for j >= -1.

A213920 Number of rooted trees with n nodes such that no more than two subtrees corresponding to children of any node have the same number of nodes.

Original entry on oeis.org

0, 1, 1, 2, 3, 7, 15, 34, 79, 190, 457, 1132, 2823, 7126, 18136, 46541, 120103, 312109, 815012, 2137755, 5632399, 14895684, 39519502, 105198371, 280815067, 751490363, 2016142768, 5420945437, 14604580683, 39425557103, 106618273626, 288792927325, 783516425820

Offset: 0

Alois P. Heinz, Mar 05 2013

nonn

Coincides with A248869 up to a(9) = 190.

a(n+1)/a(n) tends to 2.845331... - Vaclav Kotesovec, Jun 04 2019

			:  o  :  o  :    o   o  :    o     o   o  :
:     :  |  :   / \  |  :    |    / \  |  :
:     :  o  :  o   o o  :    o   o   o o  :
:     :     :        |  :   / \  |     |  :
:     :     :        o  :  o   o o     o  :
:     :     :           :              |  :
: n=1 : n=2 :  n=3      :  n=4         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 :
:                                       | :
: n=5                                   o :
:.........................................:

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

Cf. A000081, A032305, A248869.

Column k=2 of A318753.

g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=0..min(2, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=0..40);

g[n_, i_] := g[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[g[i-1, i-1]+j-1, j]*g[n-i*j, i-1], {j, 0, Min[2, n/i]}]]]; a[n_] := g[n-1, n-1]; Table[ a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 21 2017, translated from Maple *)

A318804 Number of rooted trees with n nodes such that no more than ten subtrees of the same size extend from the same node.

Original entry on oeis.org

0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4765, 12484, 32968, 87798, 235346, 634752, 1720897, 4687949, 12824195, 35216118, 97039045, 268237121, 743594937, 2066803841, 5758576675, 16080698759, 44998355630, 126161517745, 354354779794, 996963790045, 2809334906744, 7928088014833, 22404525682610

Offset: 0

Alois P. Heinz, Sep 03 2018

nonn

This differs from A318857 first at n=34.

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

Column k=10 of A318753.

Cf. A318857.

g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=0..min(10, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=0..40);

A318797 Number of rooted trees with n nodes such that no more than three subtrees of the same size extend from the same node.

Original entry on oeis.org

0, 1, 1, 2, 4, 8, 18, 43, 102, 250, 623, 1579, 4042, 10470, 27350, 72034, 190956, 509259, 1365271, 3677522, 9947145, 27007988, 73582758, 201103314, 551190098, 1514683667, 4172470962, 11519509386, 31869341642, 88337853393, 245301368188, 682307613945

Offset: 0

Alois P. Heinz, Sep 03 2018

nonn

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

Column k=3 of A318753.

g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=0..min(3, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=0..40);

A318798 Number of rooted trees with n nodes such that no more than four subtrees of the same size extend from the same node.

Original entry on oeis.org

0, 1, 1, 2, 4, 9, 19, 46, 110, 273, 684, 1746, 4503, 11758, 30943, 82118, 219337, 589477, 1592427, 4322386, 11781435, 32235285, 88502260, 243747792, 673238061, 1864400173, 5175591107, 14399672901, 40146278964, 112143682477, 313822403439, 879673332422

Offset: 0

Alois P. Heinz, Sep 03 2018

nonn

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

Column k=4 of A318753.

g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=0..min(4, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=0..40);

A318799 Number of rooted trees with n nodes such that no more than five subtrees of the same size extend from the same node.

Original entry on oeis.org

0, 1, 1, 2, 4, 9, 20, 47, 113, 281, 706, 1807, 4671, 12223, 32245, 85777, 229670, 618732, 1675523, 4558995, 12456746, 34166520, 94034681, 259621349, 718846409, 1995609079, 5553497132, 15489246752, 43290735944, 121226413303, 340079037154, 955633681302

Offset: 0

Alois P. Heinz, Sep 03 2018

nonn

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

Column k=5 of A318753.

g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=0..min(5, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=0..40);

A318800 Number of rooted trees with n nodes such that no more than six subtrees of the same size extend from the same node.

Original entry on oeis.org

0, 1, 1, 2, 4, 9, 20, 48, 114, 284, 714, 1829, 4731, 12391, 32711, 87083, 233347, 629132, 1705026, 4642964, 12696279, 34851400, 95996667, 265251800, 735029359, 2042187008, 5687725928, 15876511087, 44409195451, 124459715968, 349434210318, 982723567822

Offset: 0

Alois P. Heinz, Sep 03 2018

nonn

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

Column k=6 of A318753.

g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=0..min(6, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=0..40);

A318801 Number of rooted trees with n nodes such that no more than seven subtrees of the same size extend from the same node.

Original entry on oeis.org

0, 1, 1, 2, 4, 9, 20, 48, 115, 285, 717, 1837, 4753, 12451, 32878, 87549, 234654, 632813, 1715444, 4672539, 12780498, 35091807, 96684475, 267223388, 740690724, 2058468449, 5734614700, 16011714519, 44799497408, 125587597723, 352696619768, 992168346445

Offset: 0

Alois P. Heinz, Sep 03 2018

nonn

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

Column k=7 of A318753.

g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=0..min(7, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=0..40);

cp's OEIS Frontend

A032305 Number of rooted trees where any 2 subtrees extending from the same node have a different number of nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A318754 Number T(n,k) of rooted trees with n nodes such that k equals the maximal number of subtrees extending from the same node and having the same number of nodes; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A318757 Number A(n,k) of rooted trees with n nodes such that no more than k isomorphic subtrees extend from the same node; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A213920 Number of rooted trees with n nodes such that no more than two subtrees corresponding to children of any node have the same number of nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A318804 Number of rooted trees with n nodes such that no more than ten subtrees of the same size extend from the same node.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A318797 Number of rooted trees with n nodes such that no more than three subtrees of the same size extend from the same node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A318798 Number of rooted trees with n nodes such that no more than four subtrees of the same size extend from the same node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A318799 Number of rooted trees with n nodes such that no more than five subtrees of the same size extend from the same node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple