login
This site is supported by donations 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. 15
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

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

W. Bomfim, Bijection between rooted forests and multigraphs without cycles except one loop in each connected component.

R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 (2016), Table 2.

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

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).

Sequence in context: A092056 A103574 A112682 * A217781 A204849 A105632

Adjacent sequences:  A033182 A033183 A033184 * A033186 A033187 A033188

KEYWORD

nonn,tabl

AUTHOR

Christian G. Bower

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified May 3 23:41 EDT 2016. Contains 272384 sequences.