A242249 - OEIS

A242249

Number A(n,k) of rooted trees with n nodes and k-colored non-root nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%I #45 Dec 13 2018 11:27:49

%S 0,0,1,0,1,0,0,1,1,0,0,1,2,2,0,0,1,3,7,4,0,0,1,4,15,26,9,0,0,1,5,26,

%T 82,107,20,0,0,1,6,40,188,495,458,48,0,0,1,7,57,360,1499,3144,2058,

%U 115,0,0,1,8,77,614,3570,12628,20875,9498,286,0,0,1,9,100,966,7284,37476,111064,142773,44947,719,0

%N Number A(n,k) of rooted trees with n nodes and k-colored non-root nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%C From _Vaclav Kotesovec_, Aug 26 2014: (Start)

%C Column k > 0 is asymptotic to c(k) * d(k)^n / n^(3/2), where constants c(k) and d(k) are dependent only on k. Conjecture: d(k) ~ k * exp(1). Numerically:

%C d(1) = 2.9557652856519949747148175... (A051491)

%C d(2) = 5.6465426162329497128927135... (A245870)

%C d(3) = 8.3560268792959953682760695...

%C d(4) = 11.0699628777593263124193026...

%C d(5) = 13.7856511100846851989303249...

%C d(6) = 16.5022088446930015657112211...

%C d(7) = 19.2192613290638657575973462...

%C d(8) = 21.9366222112987115910888213...

%C d(9) = 24.6541883249893084812976812...

%C d(10) = 27.3718979186642404090999595...

%C d(100) = 272.0126359583480733207362718...

%C d(101) = 274.7309127032967881125015217...

%C d(200) = 543.8405620978790523837823296...

%C d(201) = 546.5588426492458787468860222...

%C d(101)-d(100) = 2.718276744...

%C d(201)-d(200) = 2.718280551...

%C (End)

%H Alois P. Heinz, <a href="/A242249/b242249.txt">Antidiagonals n = 0..140, flattened</a>

%H L. Foissy, <a href="https://arxiv.org/abs/1811.07572">Algebraic structures on typed decorated rooted trees</a>, arXiv:1811.07572 (2018)

%F G.f. for column k: x*Product_{n>=1} 1/(1 - x^n)^(k*A(n,k)). - _Geoffrey Critzer_, Nov 13 2014

%e Square array A(n,k) begins:

%e 0, 0, 0, 0, 0, 0, 0, 0, ...

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 2, 3, 4, 5, 6, 7, ...

%e 0, 2, 7, 15, 26, 40, 57, 77, ...

%e 0, 4, 26, 82, 188, 360, 614, 966, ...

%e 0, 9, 107, 495, 1499, 3570, 7284, 13342, ...

%e 0, 20, 458, 3144, 12628, 37476, 91566, 195384, ...

%e 0, 48, 2058, 20875, 111064, 410490, 1200705, 2984142, ...

%p with(numtheory):

%p A:= proc(n, k) option remember; `if`(n<2, n, (add(add(d*

%p A(d, k), d=divisors(j))*A(n-j, k)*k, j=1..n-1))/(n-1))

%p end:

%p seq(seq(A(n, d-n), n=0..d), d=0..12);

%t nn = 10; t[x_] := Sum[a[n] x^n, {n, 1, nn}]; Transpose[ Table[Flatten[ sol = SolveAlways[ 0 == Series[ t[x] - x Product[1/(1 - x^i)^(n a[i]), {i, 1, nn}], {x, 0, nn}], x]; Flatten[{0, Table[a[n], {n, 1, nn}]}] /. sol], {n, 0, nn}]] // Grid (* _Geoffrey Critzer_, Nov 11 2014 *)

%t A[n_, k_] := A[n, k] = If[n<2, n, Sum[Sum[d*A[d, k], {d, Divisors[j]}] *A[n-j, k]*k, {j, 1, n-1}]/(n-1)]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* _Jean-François Alcover_, Dec 04 2014, translated from Maple *)

%o (PARI) \\ ColGf gives column generating function

%o ColGf(N,k) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = k/n * sum(i=1, n, sumdiv(i, d, d*A[d]) * A[n-i+1] ) ); x*Ser(A)}

%o Mat(vector(8, k, concat(0, Col(ColGf(7, k-1))))) \\ _Andrew Howroyd_, May 12 2018

%Y Columns k=0-10 give: A063524, A000081, A000151, A006964, A052763, A052788, A246235, A246236, A246237, A246238, A246239.

%Y Rows n=0-3 give: A000004, A000012, A001477, A005449.

%Y Lower diagonal gives A242375.

%Y Cf. A255517, A256064.

%K nonn,tabl

%O 0,13

%A _Alois P. Heinz_, May 09 2014