A048816 Number of rooted trees with n nodes with every leaf at the same height.

1, 1, 2, 3, 5, 7, 12, 17, 28, 42, 68, 103, 168, 260, 420, 665, 1075, 1716, 2787, 4489, 7304, 11849, 19333, 31504, 51561, 84347, 138378, 227096, 373445, 614441, 1012583, 1669774, 2756951, 4555183, 7533988, 12469301, 20655523, 34238310, 56795325, 94270949

Offset

1,3

Comments

The trees are unordered (see A000081). For balanced ordered rooted trees see A079500. - Joerg Arndt, Jul 20 2014

The trees are unlabeled. For labeled version see A238372. - Alois P. Heinz, Dec 29 2014

Links

Vaclav Kotesovec, Table of n, a(n) for n = 1..3500 (terms 1..300 from Alois P. Heinz)

Joerg Arndt, balanced unordered rooted trees for n = 1..10

Index entries for sequences related to rooted trees

Example

See Arndt link.
From Gus Wiseman, Oct 08 2018: (Start)
The a(1) = 1 through a(7) = 12 balanced rooted trees with n nodes:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)      (oooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))     ((ooooo))
                 (((o)))  (((oo)))   (((ooo)))    (((oooo)))
                          ((o)(o))   ((o)(oo))    ((o)(ooo))
                          ((((o))))  ((((oo))))   ((oo)(oo))
                                     (((o)(o)))   ((((ooo))))
                                     (((((o)))))  (((o)(oo)))
                                                  ((o)(o)(o))
                                                  (((((oo)))))
                                                  ((((o)(o))))
                                                  (((o))((o)))
                                                  ((((((o))))))
(End)

Mathematica

T[n_, k_] := T[n, k] = If[n==1, 1, If[k==0, 0, Sum[Sum[If[d<k, 0, T[d, k-1] * d], {d, Divisors[j]}]*T[n-j, k], {j, 1, n-1}]/(n-1)]]; a[n_] := Sum[ T[n, k], {k, 0, n-1}]; Array[a, 40] (* Jean-François Alcover, Jan 08 2016, after Alois P. Heinz *)

Crossrefs

Cf. A048808-A048815.

Row sums of A244925.

Cf. A079500, A238372.

Cf. A000081, A000311, A001678, A120803, A320154, A320160, A316624, A320169.

Sequence in context: A123569 A305651 A318185 * A080528 A245152 A334271

Adjacent sequences: A048813 A048814 A048815 * A048817 A048818 A048819

Keyword

nonn

Author

Christian G. Bower, Apr 15 1999

Status

approved