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

1, 2, 9, 40, 265, 1956, 18529, 183520, 2226753, 28663300, 421589641, 6696832704, 117283627201, 2190260755060, 44645172510345, 964646320357696, 22317294448547329, 547594529028427908, 14246751684203363593, 390309056795283743200, 11276891642831796476481

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..200

Formula

E.g.f.: Sum_{i>=1} P_i with P_1 = x and P_i = x * (exp(P_{i-1})-1) for i>1.

a(n) = T(n,1), T(n,m) = n!/(n-m)!*Sum_{k=1..n-m}(stirling2(k,m)*T(n-m,k)), T(n,n)=1. - Vladimir Kruchinin, Apr 01 2015

Example

On 4 vertices, there are:
24 rooted trees X-O-O-O
12 rooted trees X-O-O
                   \
                    O
4 rooted trees    X
                 /|\
                O O O

Maple

p:= proc(i) p(i):= `if`(i=1, x, x*(exp(p(i-1))-1)) end:
s:= proc(n) s(n):= `if`(n=0, 0, s(n-1)+p(n)) end:
a:= n-> n! * coeff(series(s(n), x, n+1), x, n):
seq(a(n), n=1..25);  # Alois P. Heinz, Feb 26 2014

Mathematica

T[n_, n_] = 1; T[n_, m_] := T[n, m] = n!/(n-m)!*Sum[StirlingS2[k, m]*T[n-m, k], {k, 1, n-m}]; a[n_] := T[n, 1]; Array[a, 25] (* Jean-François Alcover, Jan 08 2016, after Vladimir Kruchinin *)

Prog

(Sage)
x = QQ[['x']].gen()
P = {}
N = 20
P[1] = x.O(N)
for i in range(2, N):
    P[i] = x*(P[i-1].exp(N)-1)
add(P[u] for u in P)
(Maxima)
T(n, m):=if n=m then 1 else n!/(n-m)!*sum(stirling2(k, m)*T(n-m, k), k, 1, n-m);
makelist(T(n, 1), n, 1, 15); /* Vladimir Kruchinin, Apr 01 2015 */

Crossrefs

Cf. A048816 for the unlabeled version.

Sequence in context: A056844 A220471 A213095 * A308475 A002825 A259339

Adjacent sequences: A238369 A238370 A238371 * A238373 A238374 A238375

Keyword

nonn

Author

F. Chapoton, Feb 25 2014

Status

approved