login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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. 12
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 (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. [From 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. [From Washington Bomfim, Sep 04 2010]

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

FORMULA

G.f.: 1/Product((1-x*y^i)^A000081(i), i=1..infinity). - Vladeta Jovovic, Apr 28 2005

a(n, k)= sum over the partitions of n, 1M1+2M2+...+nMn, with exactly k parts, of product_{1=<i<=n}C(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.

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.

Content is available under The OEIS End-User License Agreement .

Last modified July 28 14:46 EDT 2014. Contains 245001 sequences.