|
|
A238372
|
|
Number of labeled rooted trees with n nodes with every leaf at the same height.
|
|
2
|
|
|
1, 2, 9, 40, 265, 1956, 18529, 183520, 2226753, 28663300, 421589641, 6696832704, 117283627201, 2190260755060, 44645172510345, 964646320357696, 22317294448547329, 547594529028427908, 14246751684203363593, 390309056795283743200, 11276891642831796476481
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
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):
|
|
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);
|
|
CROSSREFS
|
Cf. A048816 for the unlabeled version.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|