login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A034781 Triangle of number of rooted trees with n >= 2 nodes and height h >= 1. 14
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,5

LINKS

Alois P. Heinz, Rows n = 2..142, flattened

Marko Riedel, Counting the number of rooted trees of a certain height

Marko Riedel, Maple code for sequence (OGF)

J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.

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.)

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

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):

seq(seq(T(n, k), k=1..n-1), n=2..16);  # Alois P. Heinz, Jul 31 2013

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}],

Prepend[Table[1, {10}], 0]]]], 1] // Grid (* 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}]]]; 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 *)

CROSSREFS

Columns h=2-10 give: A000065, A000235, A000299, A000342, A000393, A000418, A000429, A126085, A245068.

T(2n,n) = A245102(n), T(2n+1,n) = A245103(n).

Row sums give A000081.

Cf. A001853, A227819.

Sequence in context: A060098 A161492 A177976 * A058717 A110470 A055080

Adjacent sequences:  A034778 A034779 A034780 * A034782 A034783 A034784

KEYWORD

tabl,nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Victoria A Sapko (vsapko(AT)canes.gsw.edu), Sep 19 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 23 02:53 EDT 2017. Contains 288633 sequences.