A034781 - OEIS

%I #58 Aug 30 2024 04:38: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.

%F T(n, k) = A375467(n, k) - A375467(n, k - 1). - _Peter Luschny_, Aug 30 2024

%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_ *)

%o (Python)

%o def A034781(n, k): return A375467(n, k) - A375467(n, k - 1)

%o for n in range(2, 10): print([A034781(n, k) for k in range(2, n + 1)])

%o # _Peter Luschny_, Aug 30 2024

%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, A375467.

%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