Displaying 1-10 of 15 results found.
Triangle of number of rooted trees with n >= 2 nodes and height h >= 1.
+10
49
1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 8, 4, 1, 1, 10, 18, 13, 5, 1, 1, 14, 38, 36, 19, 6, 1, 1, 21, 76, 93, 61, 26, 7, 1, 1, 29, 147, 225, 180, 94, 34, 8, 1, 1, 41, 277, 528, 498, 308, 136, 43, 9, 1, 1, 55, 509, 1198, 1323, 941, 487, 188, 53, 10, 1
LINKS
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
FORMULA
Reference gives recurrence.
EXAMPLE
Triangle begins:
1;
1 1;
1 2 1;
1 4 3 1;
1 6 8 4 1;
1 10 18 13 5 1;
1 14 38 36 19 6 1;
thus there are 10 trees with 7 nodes and height 2.
MAPLE
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
end:
T:= (n, k)-> b((n-1)$2, k) -b((n-1)$2, k-1):
MATHEMATICA
Drop[Map[Select[#, # > 0 &] &,
Transpose[
Prepend[Table[
f[n_] :=
Nest[CoefficientList[
Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x,
0, 10}], x] &, {1}, n]; f[m] - f[m - 1], {m, 2, 10}],
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i<1 || k<1, 0, Sum[Binomial[b[i-1, i-1, k-1]+j-1, j]*b[n-i*j, i-1, k], {j, 0, n/i}]]]; T[n_, k_] := b[n-1, n-1, k]-b[n-1, n-1, k-1]; Table[T[n, k], {n, 2, 16}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Feb 11 2014, after Alois P. Heinz *)
PROG
(Python)
for n in range(2, 10): print([ A034781(n, k) for k in range(2, n + 1)])
EXTENSIONS
More terms from Victoria A Sapko (vsapko(AT)canes.gsw.edu), Sep 19 2003
Number of n-node rooted trees of height at most 3.
(Formerly M1107 N0422)
+10
19
1, 1, 1, 2, 4, 8, 15, 29, 53, 98, 177, 319, 565, 1001, 1749, 3047, 5264, 9054, 15467, 26320, 44532, 75054, 125904, 210413, 350215, 580901, 960035, 1581534, 2596913, 4251486, 6939635, 11296231, 18337815, 29692431, 47956995, 77271074, 124212966
COMMENTS
a(n+1) is also the number of n-vertex graphs that do not contain a P_4, C_4, or K_4 as induced subgraph (K_4-free trivially perfect graphs, cf. A123467). - Falk Hüffner, Jan 10 2016
REFERENCES
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
G.f.: S[ 3 ] := x*Product (1 - x^k)^(-p(k-1)), where p(k) = number of partitions of k.
G.f.: 1 + x*exp( Sum_{n>=1} x^n/n * Product_{k>=1} 1/(1 - x^(n*k)) ). - Paul D. Hanna, Nov 01 2012
MAPLE
s[ 2 ] := x/product('1-x^i', 'i'=1..30); # G.f. for trees of ht <=2, A000041for k from 3 to 12 do # gets g.f. for trees of ht <= 3, 4, 5, ...
s[ k ] := series(x/product('(1-x^i)^coeff(s[ k-1 ], x, i)', 'i'=1..30), x, 31); od:
# For Maple program see link in A000235. with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d, j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: A000041:= etr(n-> 1): a:= n->`if`(n=0, 1, etr(k-> A000041(k-1))(n-1)): seq(a(n), n=0..40); # Alois P. Heinz, Sep 08 2008
MATHEMATICA
m = 36; CoefficientList[ Series[x*Product[(1 - x^k)^(-PartitionsP[k - 1]), {k, 1, m}], {x, 0, m}], x] // Rest // Prepend[#, 1] & (* Jean-François Alcover, Jul 05 2011, after g.f. *)
PROG
(PARI) {a(n)=polcoeff(1+x*exp(sum(m=1, n, x^m/m/prod(k=1, n\m+1, 1-x^(m*k)+x*O(x^n)))), n)} \\ Paul D. Hanna, Nov 01 2012
Number of n-node trees of height at most 5.
(Formerly M1177 N0453)
+10
5
1, 1, 1, 2, 4, 9, 20, 47, 108, 252, 582, 1345, 3086, 7072, 16121, 36667, 83099, 187885, 423610, 953033, 2139158, 4792126, 10714105, 23911794, 53273599, 118497834, 263164833, 583582570, 1292276355, 2857691087, 6311058671, 13919982308, 30664998056, 67473574130
COMMENTS
a(n+1) is also the number of n-vertex graphs that do not contain a P_4, C_4, or K_6 as induced subgraph (K_6-free trivially perfect graphs, cf. A123467). - Falk Hüffner, Jan 10 2016
REFERENCES
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
MAPLE
For Maple program see link in A000235. with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d, j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: shr:= proc(p) n->`if`(n=0, 1, p(n-1)) end: b[0]:= etr(n->1): for j from 1 to 3 do b[j]:= etr(shr(b[j-1])) od: a:= shr(b[3]): seq(a(n), n=0..35); # Alois P. Heinz, Sep 08 2008
MATHEMATICA
Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x]&, {1}, 5], 1] (* Geoffrey Critzer, Aug 01 2013 *)
Number of n-node rooted trees of height at most 6.
+10
5
1, 1, 1, 2, 4, 9, 20, 48, 114, 278, 676, 1653, 4027, 9816, 23843, 57833, 139908, 337856, 814127, 1958524, 4703322, 11278027, 27003707, 64571463, 154207616, 367841733, 876450881, 2086098057, 4960230005, 11782852600, 27963874395, 66307010599
FORMULA
Take Euler transform of A001385 and shift right. (Christian G. Bower).
MAPLE
For Maple program see link in A000235. with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d, j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: shr:= proc(p) n->`if`(n=0, 1, p(n-1)) end: b[0]:= etr(n->1): for j from 1 to 4 do b[j]:= etr(shr(b[j-1])) od: a:= shr(b[4]): seq(a(n), n=0..31); # Alois P. Heinz, Sep 08 2008
MATHEMATICA
Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x]&, {1}, 6], 1] (* Geoffrey Critzer, Aug 01 2013 *)
Number of n-node trees of height at most 4.
(Formerly M1172 N0449)
+10
4
1, 1, 1, 2, 4, 9, 19, 42, 89, 191, 402, 847, 1763, 3667, 7564, 15564, 31851, 64987, 132031, 267471, 539949, 1087004, 2181796, 4367927, 8721533, 17372967, 34524291, 68456755, 135446896, 267444085, 527027186, 1036591718, 2035083599
COMMENTS
a(n+1) is also the number of n-vertex graphs that do not contain a P_4, C_4, or K_5 as induced subgraph (K_5-free trivially perfect graphs, cf. A123467). - Falk Hüffner, Jan 10 2016
REFERENCES
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
MAPLE
For Maple program see link in A000235. with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d, j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: A000041:= etr(n->1): b1:= etr(k-> A000041(k-1)): A001383:= n->`if`(n=0, 1, b1(n-1)): b2:= etr( A001383): a:= n->`if`(n=0, 1, b2(n-1)): seq(a(n), n=0..40); # Alois P. Heinz, Sep 08 2008
MATHEMATICA
Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x]&, {1}, 4], 1] (* Geoffrey Critzer, Aug 01 2013 *)
Number of n-node rooted trees of height at most 7.
+10
4
1, 1, 1, 2, 4, 9, 20, 48, 115, 285, 710, 1789, 4514, 11431, 28922, 73182, 184917, 466755, 1176393, 2961205, 7443770, 18689435, 46869152, 117412440, 293832126, 734645046, 1835147741, 4580420719, 11423511895, 28469058647, 70899220083, 176449174539, 438854372942
MAPLE
For Maple program see link in A000235. with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d, j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: shr:= proc(p) n->`if`(n=0, 1, p(n-1)) end: b[0]:= etr(n->1): for j from 1 to 5 do b[j]:= etr(shr(b[j-1])) od: a:= shr(b[5]): seq(a(n), n=0..35); # Alois P. Heinz, Sep 08 2008
MATHEMATICA
Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x]&, {1}, 7], 1] (* Geoffrey Critzer, Aug 01 2013 *)
Number of trees of diameter 7.
(Formerly M2969 N1201)
+10
3
1, 3, 14, 42, 128, 334, 850, 2010, 4625, 10201, 21990, 46108, 94912, 191562, 380933, 746338, 1444676, 2763931, 5235309, 9822686, 18275648, 33734658, 61826344, 112550305, 203627610, 366267931, 655261559, 1166312530, 2066048261, 3643352362, 6397485909, 11188129665, 19491131627, 33831897511, 58519577756, 100885389220, 173368983090, 297021470421, 507378371670, 864277569606, 1468245046383, 2487774321958, 4204663810414, 7089200255686, 11924621337321, 20012746962064, 33513139512868, 56001473574091, 93387290773141, 155419866337746
REFERENCES
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
G.f.: a(x)=(r(x)^2+r(x^2))/2, where r(x) is the generating function of A000235. - Sean A. Irvine, Nov 21 2010
MAPLE
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
end:
g:= n-> b((n-1)$2, 3) -b((n-1)$2, 2):
a:= n-> (add(g(i)*g(n-i), i=0..n)+`if`(n::even, g(n/2), 0))/2:
MATHEMATICA
m = 50; r[x_] = (Rest @ CoefficientList[ Series[ x*Product[ (1 - x^k)^(- PartitionsP[k-1]), {k, 1, m+3}], {x, 0, m+3}], x] - PartitionsP[ Range[0, m+2]]).(x^Range[m+3]); A000550 = CoefficientList[(r[x]^2 + r[x^2])/2, x][[9 ;; m+8]] (* Jean-François Alcover, Feb 09 2016 *)
Number of n-node rooted trees of height at most 8.
+10
3
1, 1, 1, 2, 4, 9, 20, 48, 115, 286, 718, 1832, 4702, 12159, 31515, 81888, 212878, 553557, 1438741, 3737331, 9700188, 25156049, 65181067, 168746672, 436505846, 1128256918, 2914103577, 7521450053, 19400577711, 50010551503, 128841990772, 331754004302
MAPLE
For Maple program see link in A000235. with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d, j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: shr:= proc(p) n->`if`(n=0, 1, p(n-1)) end: b[0]:= etr(n->1): for j from 1 to 6 do b[j]:= etr(shr(b[j-1])) od: a:= shr(b[6]): seq(a(n), n=0..31); # Alois P. Heinz, Sep 08 2008
MATHEMATICA
Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x]&, {1}, 8], 1] (* Geoffrey Critzer, Aug 01 2013 *)
Number of n-node rooted trees of height 4.
(Formerly M3461 N1408)
+10
2
0, 0, 0, 0, 1, 4, 13, 36, 93, 225, 528, 1198, 2666, 5815, 12517, 26587, 55933, 116564, 241151, 495417, 1011950, 2055892, 4157514, 8371318, 16792066, 33564256, 66875221, 132849983, 263192599, 520087551, 1025295487, 2016745784, 3958608430, 7754810743
REFERENCES
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
F. Harary & R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)
MAPLE
For Maple program see link in A000235.
MATHEMATICA
f[n_] := Nest[CoefficientList[Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x] &, {1}, n]; f[4]-f[3] (* Geoffrey Critzer, Aug 01 2013 *)
Number of n-node rooted trees of height 5.
(Formerly M3884 N1594)
+10
2
0, 0, 0, 0, 0, 1, 5, 19, 61, 180, 498, 1323, 3405, 8557, 21103, 51248, 122898, 291579, 685562, 1599209, 3705122, 8532309, 19543867, 44552066, 101124867, 228640542, 515125815, 1156829459, 2590247002, 5784031485, 12883390590, 28629914457
REFERENCES
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
MAPLE
For Maple program see link in A000235.
MATHEMATICA
f[n_] := Nest[CoefficientList[Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x] &, {1}, n]; f[5]-f[4] (* Geoffrey Critzer, Aug 01 2013 *) b[n_, i_, k_] := b[n, i, k] = If[n==0, 1, If[i<1 || k<1, 0, Sum[ Binomial[ b[i-1, i-1, k-1]+j-1, j]*b[n-i*j, i-1, k], {j, 0, n/i}]]]; a[n_] := b[n- 1, n-1, 5] - b[n-1, n-1, 4]; Array[a, 40] (* Jean-François Alcover, Feb 07 2016, after Alois P. Heinz in A034781 *)
Search completed in 0.015 seconds
| 