cp's OEIS Frontend

A139383 Number of n-level labeled rooted trees with n leaves.

%I A139383 #56 Feb 01 2025 23:20:34
%S A139383 1,1,2,12,154,3455,120196,5995892,406005804,35839643175,3998289746065,
%T A139383 550054365477936,91478394767427823,18091315306315315610,
%U A139383 4196205472500769304318,1128136777063831105273242,347994813261017613045578964,122080313159891715442898099217
%N A139383 Number of n-level labeled rooted trees with n leaves.
%C A139383 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
%H A139383 Alois P. Heinz, <a href="/A139383/b139383.txt">Table of n, a(n) for n = 0..247</a>
%F A139383 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
%F A139383 a(n) = n! * [x^n] 1 + g^n(x), where g(x) = exp(x)-1. - _Alois P. Heinz_, Aug 14 2015
%F A139383 From _Vaclav Kotesovec_, Aug 14 2015: (Start)
%F A139383 Conjecture: a(n) ~ c * n^(2*n-5/6) / (2^(n-1) * exp(n)), where c = 2.86539...
%F A139383 a(n) ~ exp(-1) * A261280(n).
%F A139383 (End)
%e A139383 If we form a table from the family of sequences defined by:
%e A139383 number of k-level labeled rooted trees with n leaves,
%e A139383 then this sequence equals the diagonal in that table:
%e A139383 n=1:A000012=[1,1,1,1,1,1,1,1,1,1,...];
%e A139383 n=2:A000110=[1,2,5,15,52,203,877,4140,21147,115975,...];
%e A139383 n=3:A000258=[1,3,12,60,358,2471,19302,167894,1606137,...];
%e A139383 n=4:A000307=[1,4,22,154,1304,12915,146115,1855570,26097835,...];
%e A139383 n=5:A000357=[1,5,35,315,3455,44590,660665,11035095,204904830,...];
%e A139383 n=6:A000405=[1,6,51,561,7556,120196,2201856,45592666,1051951026,...];
%e A139383 n=7:A001669=[1,7,70,910,14532,274778,5995892,148154860,4085619622,...];
%e A139383 n=8:A081624=[1,8,92,1380,25488,558426,14140722,406005804,13024655442,...];
%e A139383 n=9:A081629=[1,9,117,1989,41709,1038975,29947185,979687005,35839643175,..].
%e A139383 Row n in the above table equals column 0 of matrix power A008277^n where A008277 = triangle of Stirling numbers of 2nd kind:
%e A139383 1;
%e A139383 1,1;
%e A139383 1,3,1;
%e A139383 1,7,6,1;
%e A139383 1,15,25,10,1;
%e A139383 1,31,90,65,15,1; ...
%e A139383 The name of this sequence is a generalization of the definition given in the above sequences by _Christian G. Bower_.
%p A139383 A:= proc(n, k) option remember; `if`(n=0 or k=0, 1,
%p A139383       add(binomial(n-1, j-1)*A(j, k-1)*A(n-j, k), j=1..n))
%p A139383     end:
%p A139383 a:= n-> A(n, n-1):
%p A139383 seq(a(n), n=0..20);  # _Alois P. Heinz_, Aug 14 2015
%p A139383 # second Maple program:
%p A139383 g:= x-> exp(x)-1:
%p A139383 a:= n-> n! * coeff(series(1+(g@@n)(x), x, n+1), x, n):
%p A139383 seq(a(n), n=0..20);  # _Alois P. Heinz_, Jul 31 2017
%p A139383 # third Maple program:
%p A139383 b:= proc(n, t, m) option remember; `if`(t=0, `if`(n<2, 1, 0),
%p A139383      `if`(n=0, b(m, t-1, 0), m*b(n-1, t, m)+b(n-1, t, m+1)))
%p A139383     end:
%p A139383 a:= n-> b(n$2, 0):
%p A139383 seq(a(n), n=0..20);  # _Alois P. Heinz_, Aug 04 2021
%t A139383 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_ *)
%o A139383 (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)}
%o A139383 (Maxima) T(n,m):=if m=1 then 1 else sum(stirling2(n,i)*T(i,m-1),i,1,n);
%o A139383 makelist(T(n,n),n,1,7); /* _Vladimir Kruchinin_, May 19 2012 */
%o A139383 (Python)
%o A139383 from sympy.core.cache import cacheit
%o A139383 from sympy import binomial
%o A139383 @cacheit
%o A139383 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))
%o A139383 def a(n): return A(n, n - 1)
%o A139383 print([a(n) for n in range(21)]) # _Indranil Ghosh_, Aug 07 2017, after Maple code
%Y A139383 Cf. A008277; A000110, A000258, A000307, A000357, A000405, A001669, A081624, A081629, A261280, A290354.
%Y A139383 A diagonal of A144150.
%K A139383 nonn
%O A139383 0,3
%A A139383 _Paul D. Hanna_, Apr 16 2008
%E A139383 a(0)=1 prepended by _Alois P. Heinz_, Jul 31 2017