login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033185 Rooted tree triangle read by rows: a(n,k) = number of forests with n nodes and k rooted trees. 27
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, 44, 19, 7, 3, 1, 1, 286, 239, 117, 46, 19, 7, 3, 1, 1, 719, 622, 299, 124, 47, 19, 7, 3, 1, 1, 1842, 1607, 793, 320, 126, 47, 19, 7, 3, 1, 1, 4766, 4235, 2095, 858, 327, 127, 47, 19, 7, 3, 1, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
1,4
COMMENTS
Leading column: A000081, rows sums: A000081 shifted.
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
Number of rooted trees with n+1 nodes and degree of the root is k.- Michael Somos, Aug 20 2018
LINKS
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 [math.CO] (2016), Table 2.
FORMULA
G.f.: 1/Product_{i>=1} (1-x*y^i)^A000081(i). - Vladeta Jovovic, Apr 28 2005
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
EXAMPLE
Triangle begins:
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, 44, 19, 7, 3, 1, 1;
286, 239, 117, 46, 19, 7, 3, 1, 1;
719, 622, 299, 124, 47, 19, 7, 3, 1, 1;
1842, 1607, 793, 320, 126, 47, 19, 7, 3, 1, 1;
MAPLE
with(numtheory):
t:= proc(n) option remember; local d, j; `if` (n<=1, n,
(add(add(d*t(d), d=divisors(j))*t(n-j), j=1..n-1))/(n-1))
end:
b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
`if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j) *
binomial(t(i)+j-1, j), j=0..min(n/i, p)))))
end:
a:= (n, k)-> b(n, n, k):
seq(seq(a(n, k), k=1..n), n=1..14); # Alois P. Heinz, Aug 20 2012
MATHEMATICA
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[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 *)
CROSSREFS
Cf. A000081, A005197, A106240, A181360, A027852 (2nd column), A000226 (3rd column), A029855 (4th column), A336087.
Sequence in context: A362903 A103574 A112682 * A217781 A339428 A204849
KEYWORD
nonn,tabl
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)