OFFSET
0,3
COMMENTS
Define the matrix function matexps(M) to be exp(M)/exp(1). Then the number of k-level labeled rooted trees with n leaves is also column 0 of the triangle resulting from the n-th iteration of matexps on the Pascal matrix P, A007318. The resulting triangle is also S^n*P*S^-n, where S is the Stirling2 matrix A048993. This function can be coded in PARI as sum(k=0,200,1./k!*M^k)/exp(1)), using exp(M) does not work. See A056857, which equals (1/e)*exp(P) or S*P*S^-1. - Gerald McGarvey, Aug 19 2009
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..247
FORMULA
a(n) = T(n,n), T(n,m) = Sum_{i=1..n} Stirling2(n,i)*T(i,m-1), m>1, T(n,1)=1. - Vladimir Kruchinin, May 19 2012
a(n) = n! * [x^n] 1 + g^n(x), where g(x) = exp(x)-1. - Alois P. Heinz, Aug 14 2015
From Vaclav Kotesovec, Aug 14 2015: (Start)
Conjecture: a(n) ~ c * n^(2*n-5/6) / (2^(n-1) * exp(n)), where c = 2.86539...
a(n) ~ exp(-1) * A261280(n).
(End)
EXAMPLE
If we form a table from the family of sequences defined by:
number of k-level labeled rooted trees with n leaves,
then this sequence equals the diagonal in that table:
n=1:A000012=[1,1,1,1,1,1,1,1,1,1,...];
n=2:A000110=[1,2,5,15,52,203,877,4140,21147,115975,...];
n=3:A000258=[1,3,12,60,358,2471,19302,167894,1606137,...];
n=4:A000307=[1,4,22,154,1304,12915,146115,1855570,26097835,...];
n=5:A000357=[1,5,35,315,3455,44590,660665,11035095,204904830,...];
n=6:A000405=[1,6,51,561,7556,120196,2201856,45592666,1051951026,...];
n=7:A001669=[1,7,70,910,14532,274778,5995892,148154860,4085619622,...];
n=8:A081624=[1,8,92,1380,25488,558426,14140722,406005804,13024655442,...];
n=9:A081629=[1,9,117,1989,41709,1038975,29947185,979687005,35839643175,..].
Row n in the above table equals column 0 of matrix power A008277^n where A008277 = triangle of Stirling numbers of 2nd kind:
1;
1,1;
1,3,1;
1,7,6,1;
1,15,25,10,1;
1,31,90,65,15,1; ...
The name of this sequence is a generalization of the definition given in the above sequences by Christian G. Bower.
MAPLE
A:= proc(n, k) option remember; `if`(n=0 or k=0, 1,
add(binomial(n-1, j-1)*A(j, k-1)*A(n-j, k), j=1..n))
end:
a:= n-> A(n, n-1):
seq(a(n), n=0..20); # Alois P. Heinz, Aug 14 2015
# second Maple program:
g:= x-> exp(x)-1:
a:= n-> n! * coeff(series(1+(g@@n)(x), x, n+1), x, n):
seq(a(n), n=0..20); # Alois P. Heinz, Jul 31 2017
# third Maple program:
b:= proc(n, t, m) option remember; `if`(t=0, `if`(n<2, 1, 0),
`if`(n=0, b(m, t-1, 0), m*b(n-1, t, m)+b(n-1, t, m+1)))
end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..20); # Alois P. Heinz, Aug 04 2021
MATHEMATICA
Clear[t]; t[n_, m_]:=t[n, m] = If[m==1, 1, Sum[StirlingS2[n, k]*t[k, m-1], {k, 1, n}]]; Table[t[n, n], {n, 1, 20}] (* Vaclav Kotesovec, Aug 14 2015 after Vladimir Kruchinin *)
PROG
(PARI) {a(n)=local(E=exp(x+x*O(x^n))-1, F=x); for(i=1, n, F=subst(F, x, E)); n!*polcoeff(F, n)}
(Maxima) T(n, m):=if m=1 then 1 else sum(stirling2(n, i)*T(i, m-1), i, 1, n);
makelist(T(n, n), n, 1, 7); [Vladimir Kruchinin, May 19 2012]
(Python)
from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def A(n, k): return 1 if n==0 or k==0 else sum(binomial(n - 1, j - 1)*A(j, k - 1)*A(n - j, k) for j in range(1, n + 1))
def a(n): return A(n, n - 1)
print([a(n) for n in range(21)]) # Indranil Ghosh, Aug 07 2017, after Maple code
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Apr 16 2008
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Jul 31 2017
STATUS
approved