A181360 -id:A181360 - cp's OEIS frontend

A033185 Rooted tree triangle read by rows: a(n,k) = number of forests with n nodes and k rooted trees.

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

Offset: 1

Christian G. Bower

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

			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;

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 [math.CO] (2016), Table 2.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000081, A005197, A106240, A181360, A027852 (2nd column), A000226 (3rd column), A029855 (4th column), A336087.

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

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

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

A174135 Irregular triangle read by rows: T(n,k), n >= 2, 1 <= k <= n/2, = number of rooted forests with n nodes and k trees, with at least two nodes in each tree.

Original entry on oeis.org

1, 2, 4, 1, 9, 2, 20, 7, 1, 48, 17, 2, 115, 48, 7, 1, 286, 124, 21, 2, 719, 336, 60, 7, 1, 1842, 888, 171, 21, 2, 4766, 2393, 488, 65, 7, 1, 12486, 6419, 1372, 187, 21, 2, 32973, 17376, 3862, 554, 65, 7, 1, 87811, 47097, 10846, 1600, 193, 21, 2, 235381, 128365, 30429, 4644, 574, 65, 7, 1, 634847, 350837, 85365, 13362, 1685, 193, 21, 2

Offset: 2

N. J. A. Sloane, Nov 26 2010

In other words, components consisting of just a root node are forbidden. If this condition is removed, we get A033185.
First column is a version of A000081. Row sums give A174145.
Diagonal sums give A181360 (e.g., 9+7+2+1 = 19).

			Triangle begins:
1,
2,
4, 1,
9, 2,
20, 7, 1,
48, 17, 2,
115, 48, 7, 1,
286, 124, 21, 2,
719, 336, 60, 7, 1,
1842, 888, 171, 21, 2,
4766, 2393, 488, 65, 7, 1,
12486, 6419, 1372, 187, 21, 2,
32973, 17376, 3862, 554, 65, 7, 1,
87811, 47097, 10846, 1600, 193, 21, 2,
235381, 128365, 30429, 4644, 574, 65, 7, 1,
634847, 350837, 85365, 13362, 1685, 193, 21, 2,
1721159, 962731, 239566, 38459, 4948, 581, 65, 7, 1,
...

Alois P. Heinz, Rows n = 2..200, flattened

Cf. A000081, A033185, A174145, A181360.

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`(p<1 or i<2, 0, add(b(n-i*j, i-1, p-j) *
       binomial(t(i)+j-1, j), j=0..min(n/i, p) ))))
    end:
T:= (n, k)-> b(n, n, k):
seq(seq(T(n, k), k=1..iquo(n, 2)), n=2..18);  # Alois P. Heinz, May 17 2013

t[n_] := t[n] = Module[{d, j}, If[n <= 1, n, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n-j], {j, 1, n-1}]/(n-1)]]; b[n_, i_, p_] := b[n, i, p] = If[p > n, 0, If[n == 0, 1, If[p < 1 || i < 2, 0, Sum[b[n-i*j, i-1, p-j]* Binomial[t[i]+j-1, j], {j, 0, Min[n/i, p]}]]]]; T[n_, k_] := b[n, n, k]; Table[Table[T[n, k], {k, 1, Quotient[n, 2]}], {n, 2, 18}] // Flatten (* Jean-François Alcover, Mar 05 2014, after Alois P. Heinz *)

G.f.: 1/Product((1-x*y^i)^A000081(i), i=2..infinity).

cp's OEIS Frontend

A033185 Rooted tree triangle read by rows: a(n,k) = number of forests with n nodes and k rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula