cp's OEIS Frontend

A034781 Triangle of number of rooted trees with n >= 2 nodes and height h >= 1.

%I A034781 #58 Aug 30 2024 04:38:39
%S A034781 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 A034781 76,93,61,26,7,1,1,29,147,225,180,94,34,8,1,1,41,277,528,498,308,136,
%U A034781 43,9,1,1,55,509,1198,1323,941,487,188,53,10,1
%N A034781 Triangle of number of rooted trees with n >= 2 nodes and height h >= 1.
%H A034781 Alois P. Heinz, <a href="/A034781/b034781.txt">Rows n = 2..142, flattened</a>
%H A034781 Marko Riedel, <a href="http://math.stackexchange.com/questions/1801039/">Counting the number of rooted trees of a certain height</a>
%H A034781 Marko Riedel, <a href="/A034781/a034781_1.maple.txt">Maple code for sequence (OGF)</a>
%H A034781 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 A034781 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 A034781 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 A034781 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A034781 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A034781 Reference gives recurrence.
%F A034781 T(n, k) = A375467(n, k) - A375467(n, k - 1). - _Peter Luschny_, Aug 30 2024
%e A034781 Triangle begins:
%e A034781   1;
%e A034781   1  1;
%e A034781   1  2  1;
%e A034781   1  4  3  1;
%e A034781   1  6  8  4  1;
%e A034781   1 10 18 13  5  1;
%e A034781   1 14 38 36 19  6 1;
%e A034781 thus there are 10 trees with 7 nodes and height 2.
%p A034781 b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
%p A034781      add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
%p A034781     end:
%p A034781 T:= (n, k)-> b((n-1)$2, k) -b((n-1)$2, k-1):
%p A034781 seq(seq(T(n, k), k=1..n-1), n=2..16);  # _Alois P. Heinz_, Jul 31 2013
%t A034781 Drop[Map[Select[#, # > 0 &] &,
%t A034781    Transpose[
%t A034781     Prepend[Table[
%t A034781       f[n_] :=
%t A034781        Nest[CoefficientList[
%t A034781           Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x,
%t A034781             0, 10}], x] &, {1}, n]; f[m] - f[m - 1], {m, 2, 10}],
%t A034781 Prepend[Table[1, {10}], 0]]]], 1] // Grid (* _Geoffrey Critzer_, Aug 01 2013 *)
%t A034781 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_ *)
%o A034781 (Python)
%o A034781 def A034781(n, k): return A375467(n, k) - A375467(n, k - 1)
%o A034781 for n in range(2, 10): print([A034781(n, k) for k in range(2, n + 1)])
%o A034781 # _Peter Luschny_, Aug 30 2024
%Y A034781 Columns h=2-10 give: A000065, A000235, A000299, A000342, A000393, A000418, A000429, A126085, A245068.
%Y A034781 T(2n,n) = A245102(n), T(2n+1,n) = A245103(n).
%Y A034781 Row sums give A000081.
%Y A034781 Cf. A001853, A227819, A375467.
%K A034781 tabl,nonn,easy,nice
%O A034781 2,5
%A A034781 _N. J. A. Sloane_
%E A034781 More terms from Victoria A Sapko (vsapko(AT)canes.gsw.edu), Sep 19 2003