|
%I #54 Feb 09 2018 21:46:39
%S 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,
%T 76,93,61,26,7,1,1,29,147,225,180,94,34,8,1,1,41,277,528,498,308,136,
%U 43,9,1,1,55,509,1198,1323,941,487,188,53,10,1
%N Triangle of number of rooted trees with n >= 2 nodes and height h >= 1.
%H Alois P. Heinz, <a href="/A034781/b034781.txt">Rows n = 2..142, flattened</a>
%H Marko Riedel, <a href="http://math.stackexchange.com/questions/1801039/">Counting the number of rooted trees of a certain height</a>
%H Marko Riedel, <a href="/A034781/a034781_1.maple.txt">Maple code for sequence (OGF)</a>
%H J. Riordan, <a href="http://dx.doi.org/10.1147/rd.45.0473">Enumeration of trees by height and diameter</a>, IBM J. Res. Dev. 4 (1960), 473-478.
%H J. Riordan, <a href="/A007401/a007401_8.pdf">The enumeration of trees by height and diameter</a>, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)
%H Peter Steinbach, <a href="/A000055/a000055_10.pdf">Field Guide to Simple Graphs, Volume 3</a>, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F Reference gives recurrence.
%e Triangle begins:
%e 1;
%e 1 1;
%e 1 2 1;
%e 1 4 3 1;
%e 1 6 8 4 1;
%e 1 10 18 13 5 1;
%e 1 14 38 36 19 6 1;
%e thus there are 10 trees with 7 nodes and height 2.
%p b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
%p add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
%p end:
%p T:= (n, k)-> b((n-1)$2, k) -b((n-1)$2, k-1):
%p seq(seq(T(n, k), k=1..n-1), n=2..16); # _Alois P. Heinz_, Jul 31 2013
%t Drop[Map[Select[#, # > 0 &] &,
%t Transpose[
%t Prepend[Table[
%t f[n_] :=
%t Nest[CoefficientList[
%t Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x,
%t 0, 10}], x] &, {1}, n]; f[m] - f[m - 1], {m, 2, 10}],
%t Prepend[Table[1, {10}], 0]]]], 1] // Grid (* _Geoffrey Critzer_, Aug 01 2013 *)
%t 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_ *)
%Y Columns h=2-10 give: A000065, A000235, A000299, A000342, A000393, A000418, A000429, A126085, A245068.
%Y T(2n,n) = A245102(n), T(2n+1,n) = A245103(n).
%Y Row sums give A000081.
%Y Cf. A001853, A227819.
%K tabl,nonn,easy,nice
%O 2,5
%A _N. J. A. Sloane_
%E More terms from Victoria A Sapko (vsapko(AT)canes.gsw.edu), Sep 19 2003
|
