|
%I #59 Sep 02 2020 10:39:57
%S 1,1,1,2,1,1,4,3,1,1,9,6,3,1,1,20,16,7,3,1,1,48,37,18,7,3,1,1,115,96,
%T 44,19,7,3,1,1,286,239,117,46,19,7,3,1,1,719,622,299,124,47,19,7,3,1,
%U 1,1842,1607,793,320,126,47,19,7,3,1,1,4766,4235,2095,858,327,127,47,19,7,3,1,1
%N Rooted tree triangle read by rows: a(n,k) = number of forests with n nodes and k rooted trees.
%C Leading column: A000081, rows sums: A000081 shifted.
%C Also, number of multigraphs of k components, n nodes, and no cycles except one loop in each component. See link below to have a picture showing the bijection between rooted forests and multigraphs of this kind. - _Washington Bomfim_, Sep 04 2010
%C Number of rooted trees with n+1 nodes and degree of the root is k.- _Michael Somos_, Aug 20 2018
%H Alois P. Heinz, <a href="/A033185/b033185.txt">Rows n = 1..141, flattened</a>
%H W. Bomfim, <a href="http://en.wikipedia.org/wiki/File:Bijecao.gif">Bijection between rooted forests and multigraphs without cycles except one loop in each connected component.</a>
%H R. J. Mathar, <a href="http://arxiv.org/abs/1603.00077">Topologically distinct sets of non-intersecting circles in the plane</a>, arXiv:1603.00077 [math.CO] (2016), Table 2.
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F G.f.: 1/Product_{i>=1} (1-x*y^i)^A000081(i). - _Vladeta Jovovic_, Apr 28 2005
%F a(n, k) = sum over the partitions of n, 1M1 + 2M2 + ... + nMn, with exactly k parts, of Product_{i=1..n} binomial(A000081(i)+Mi-1, Mi). - _Washington Bomfim_, May 12 2005
%e Triangle begins:
%e 1;
%e 1, 1;
%e 2, 1, 1;
%e 4, 3, 1, 1;
%e 9, 6, 3, 1, 1;
%e 20, 16, 7, 3, 1, 1;
%e 48, 37, 18, 7, 3, 1, 1;
%e 115, 96, 44, 19, 7, 3, 1, 1;
%e 286, 239, 117, 46, 19, 7, 3, 1, 1;
%e 719, 622, 299, 124, 47, 19, 7, 3, 1, 1;
%e 1842, 1607, 793, 320, 126, 47, 19, 7, 3, 1, 1;
%p with(numtheory):
%p t:= proc(n) option remember; local d, j; `if` (n<=1, n,
%p (add(add(d*t(d), d=divisors(j))*t(n-j), j=1..n-1))/(n-1))
%p end:
%p b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
%p `if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j) *
%p binomial(t(i)+j-1, j), j=0..min(n/i, p)))))
%p end:
%p a:= (n, k)-> b(n, n, k):
%p seq(seq(a(n, k), k=1..n), n=1..14); # _Alois P. Heinz_, Aug 20 2012
%t nn=10;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0 == Series[f[x]-x Product[1/(1-x^i)^a[i],{i,1,nn}],{x,0,nn}],x];a[0]=0;g=Table[a[n],{n,1,nn}]/.sol//Flatten;h[list_]:=Select[list,#>0&];Map[h,Drop[CoefficientList[Series[x Product[1/(1-y x^i)^g[[i]],{i,1,nn}],{x,0,nn}],{x,y}],2]]//Grid (* _Geoffrey Critzer_, Nov 17 2012 *)
%t t[1] = 1; t[n_] := t[n] = Module[{d, j}, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n-j], {j, 1, n-1}]/(n-1)]; b[1, 1, 1] = 1; b[n_, i_, p_] := b[n, i, p] = If[p>n, 0, If[n == 0, 1, If[Min[i, p]<1, 0, Sum[b[n-i*j, i-1, p-j]*Binomial[t[i]+j-1, j], {j, 0, Min[n/i, p]}]]]]; a[n_, k_] := b[n, n, k]; Table[a[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Mar 13 2014, after _Alois P. Heinz_ *)
%Y Cf. A000081, A005197, A106240, A181360, A027852 (2nd column), A000226 (3rd column), A029855 (4th column), A336087.
%K nonn,tabl
%O 1,4
%A _Christian G. Bower_
|
