A032305
Number of rooted trees where any 2 subtrees extending from the same node have a different number of nodes.
Original entry on oeis.org
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
The a(6) = 6 fully unbalanced trees: (((((o))))), (((o(o)))), ((o((o)))), (o(((o)))), (o(o(o))), ((o)((o))). - _Gus Wiseman_, Jan 10 2018
-
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)
A318753
Number A(n,k) of rooted trees with n nodes such that no more than k subtrees extending from the same node have the same number of nodes; 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, 51, 0, 0, 1, 1, 2, 4, 9, 20, 46, 102, 190, 111, 0, 0, 1, 1, 2, 4, 9, 20, 47, 110, 250, 457, 240, 0
Offset: 0
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, ...
Columns k=0-10 give:
A063524,
A032305,
A213920,
A318797,
A318798,
A318799,
A318800,
A318801,
A318802,
A318803,
A318804.
-
g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
binomial(A(i, k)+j-1, j)*g(n-i*j, i-1, k), j=0..min(k, n/i))))
end:
A:= (n, k)-> g(n-1$2, k):
seq(seq(A(n, d-n), n=0..d), d=0..14);
-
g[n_, i_, k_] := g[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j]*g[n - i*j, i - 1, k], {j, 0, Min[k, n/i]}]]];
A[n_, k_] := g[n - 1, n - 1, k];
Table[A[n, d - n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 27 2019, after Alois P. Heinz *)
A248869
Satisfies Sum_{n>=0} a(n)*x^n = x * Product_{n>=0} (1 + x^n + x^(2*n))^a(n).
Original entry on oeis.org
0, 1, 1, 2, 3, 7, 15, 34, 79, 190, 459, 1136, 2833, 7154, 18206, 46723, 120656, 313514, 818763, 2148434, 5660790, 14972103, 39734107, 105779291, 282403830, 755921733, 2028277115, 5454368549, 14697955778, 39682793675, 107330573239, 290783511134, 789032648219
Offset: 0
-
h:= proc(n, m, t) option remember; `if`(m=0, binomial(n+t, t),
`if`(n=0, 0, add(h(n-1, m-j, t+1), j=1..min(2, m))))
end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(b(n-i*j, i-1)*h(a(i), j, 0), j=0..n/i)))
end:
a:= n-> `if`(n<2, n, b(n-1$2)):
seq(a(n), n=0..35); # Alois P. Heinz, Sep 04 2018
-
h[n_, m_, t_] := h[n, m, t] = If[m == 0, Binomial[n + t, t], If[n == 0, 0, Sum[h[n - 1, m - j, t + 1], {j, 1, Min[2, m]}]]];
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i j, i - 1]* h[a[i], j, 0], {j, 0, n/i}]]];
a[n_] := If[n < 2, n, b[n - 1, n - 1]];
a /@ Range[0, 32] (* Jean-François Alcover, Oct 02 2019, after Alois P. Heinz *)
A248890
Number of rooted trees with n nodes such that for each inner node no more than k subtrees corresponding to its children have exactly k nodes.
Original entry on oeis.org
0, 1, 1, 1, 2, 4, 8, 16, 34, 75, 166, 374, 849, 1952, 4522, 10566, 24840, 58760, 139693, 333702, 800412, 1927207, 4655997, 11283835, 27423930, 66825194, 163227234, 399587270, 980222058, 2409181633, 5931839530, 14629639579, 36137308192, 89395224033
Offset: 0
: 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=1 : n=2 : n=3 : n=4 : n=5 o :
:.....:.....:.....:...........:.......................:
-
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(i, 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[i, n/i]}]]]; a[n_] := g[n-1, n-1]; Table[ a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 28 2017, translated from Maple *)
Showing 1-4 of 4 results.
Comments