A033185 -id:A033185 - cp's OEIS frontend

A280786 Number of topologically distinct sets of n circles with one pair intersecting.

1, 4, 15, 50, 162, 506, 1558, 4727, 14227, 42521, 126506, 374969, 1108476, 3269902, 9630631, 28328999, 83251569, 244471484, 717486860, 2104777227, 6172357873, 18096097750, 53044095421, 155464365080, 455601800970, 1335107222743, 3912330438784, 11464463809180, 33595343643160

Offset: 2

N. J. A. Sloane, Jan 20 2017

nonn

R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016, row sums Table 7.

Row sums of A280787.

Column k=1 of A261070.

A280786 := proc(N)
    if N < 2 then
        0;
    else
        add(A280787(N,f),f=1..N-1) ;
    end if;
end proc:
A280787 := proc(N,f)
    option remember ;
    local Npr,ct ;
    if f = N then
        return 0;
    elif f = N-1 then
        return 1;
    elif f = 1 then
        A280786(N-1)+A280788(N-2) ;
    else
        ct := 0 ;
        for Npr from 1 to N-1 do
            ct := ct+procname(Npr,1)*A033185(N-Npr,f-1) ;
        end do:
        ct ;
    end if;
end proc:
seq(A280786(n),n=2..30) ; # R. J. Mathar, Mar 06 2017

a81[n_] := a81[n] = If[n <= 1, n, Sum[a81[n - j]*DivisorSum[j, #1*a81[#1] &], {j, n - 1}]/(n - 1)];
A027852[n_] := Module[{dh = 0, np}, For[np = 0, np <= n, np++, dh = a81[np]*a81[n - np] + dh]; If[EvenQ[n], dh = a81[n/2] + dh]; dh/2];
A280788[n_] := If[n == 0, 1, Sum[a81[np + 1]*A027852[n - np + 2], {np, 0, n}]];
t[n_] := t[n] = Module[{d, j}, If[n == 1, 1, 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]}]]]]; A033185[n_, k_] := b[n, n, k];
A280786[n_] := If[n < 2, 0, Sum[A280787[n, f], {f, 1, n - 1}]];
A280787[n_, f_] := A280787[n, f] = Module[{ct}, Which[f == n, Return[0], f == n - 1, Return[1], f == 1, Return[A280786[n - 1] + A280788[n - 2]], True, ct = 0; Do[ct += A280787[np, 1]*A033185[n - np, f - 1], {np, 1, n - 1}]]; ct];
Table[A280786[n], {n, 2, 30}] (* Jean-François Alcover, Nov 23 2017, after R. J. Mathar and Alois P. Heinz *)

A291336 Number F(n,h,t) of forests of t unlabeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 0, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 2, 1, 0, 4, 3, 1, 0, 3, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3, 3, 2, 1, 0, 6, 8, 3, 1, 0, 8, 4, 1, 0, 4, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3, 4, 3, 2, 1, 0, 10, 15, 9, 3, 1, 0, 18, 13, 4, 1, 0, 13, 5, 1, 0, 5, 1, 0, 1, 0

Offset: 0

Alois P. Heinz, Aug 22 2017

Elements in rows h=0 give A023531.
Positive elements in rows h=1 give A008284.
Positive row sums per layer (and - with a different offset - positive elements in column t=1) give A034781.
Positive column sums per layer give A033185.

			n h\t: 0 1 2 3 4 5 : A034781 : A033185   : A000081
-----+-------------+---------+-----------+--------
0 0  : 1           :         :           : 1
-----+-------------+---------+-----------+--------
1 0  : 0 1         :       1 : .         :
1 1  : 0           :         : 1         : 1
-----+-------------+---------+-----------+--------
2 0  : 0 0 1       :       1 : . .       :
2 1  : 0 1         :       1 : .         :
2 2  : 0           :         : 1 1       : 2
-----+-------------+---------+-----------+--------
3 0  : 0 0 0 1     :       1 : . . .     :
3 1  : 0 1 1       :       2 : . .       :
3 2  : 0 1         :       1 : .         :
3 3  : 0           :         : 2 1 1     : 4
-----+-------------+---------+-----------+--------
4 0  : 0 0 0 0 1   :       1 : . . . .   :
4 1  : 0 1 2 1     :       4 : . . .     :
4 2  : 0 2 1       :       3 : . .       :
4 3  : 0 1         :       1 : .         :
4 4  : 0           :         : 4 3 1 1   : 9
-----+-------------+---------+-----------+--------
5 0  : 0 0 0 0 0 1 :       1 : . . . . . :
5 1  : 0 1 2 2 1   :       6 : . . . .   :
5 2  : 0 4 3 1     :       8 : . . .     :
5 3  : 0 3 1       :       4 : . .       :
5 4  : 0 1         :       1 : .         :
5 5  : 0           :         : 9 6 3 1 1 : 20
-----+-------------+---------+-----------+--------

Alois P. Heinz, Layers n = 0..48, flattened

Cf. A000007, A000041, A000065, A000081, A001853, A005197, A008284, A023531, A033185, A034781, A291203, A291204, A291529.

b:= proc(n, i, t, h) option remember; expand(`if`(n=0 or h=0
       or i=1, x^(t*n), b(n, i-1, t, h)+add(x^(t*j)*binomial(
       b(i-1$2, 0, h-1)+j-1, j)*b(n-i*j, i-1, t, h), j=1..n/i)))
    end:
g:= (n, h)-> b(n$2, 1, h)-`if`(h=0, 0, b(n$2, 1, h-1)):
F:= (n, h, t)-> coeff(g(n, h), x, t):
seq(seq(seq(F(n, h, t), t=0..n-h), h=0..n), n=0..9);

b[n_, i_, t_, h_] := b[n, i, t, h] = Expand[If[n == 0 || h == 0
     || i == 1, x^(t*n), b[n, i-1, t, h] + Sum[x^(t*j)*Binomial[
     b[i-1, i-1, 0, h-1]+j-1, j]*b[n - i*j, i-1, t, h], {j, 1, n/i}]]];
g[n_, h_] := b[n, n, 1, h] - If[h == 0, 0, b[n, n, 1, h-1]];
F[n_, h_, t_] := Coefficient[g[n, h], x, t];
Table[Table[Table[F[n, h, t], {t, 0, n-h}], {h, 0, n}], {n, 0, 9}] //
Flatten (* Jean-François Alcover, Mar 10 2022, after Alois P. Heinz *)

Sum_{d=0..n} Sum_{i=0..d} F(n,i,d-i) = A000081(n+1).
Sum_{h=0..n} Sum_{t=0..n-h} t * F(n,h,t) = A005197(n).
Sum_{h=0..n} Sum_{t=0..n-h} (h+1) * F(n,h,t) = A001853(n+1) for n>0.
Sum_{t=0..n-1} F(n,1,t) = A000065(n) = A000041(n) - 1.
F(n,1,1) = 1 for n>1.
F(n,0,0) = A000007(n).

A331233 Number of unlabeled rooted trees with n vertices and more than two branches of the root.

Original entry on oeis.org

0, 0, 0, 1, 2, 5, 12, 30, 75, 194, 501, 1317, 3485, 9302, 24976, 67500, 183290, 500094, 1369939, 3766831, 10391722, 28756022, 79794407, 221987348, 619019808, 1729924110, 4844242273, 13590663071, 38195831829, 107523305566, 303148601795, 855922155734, 2419923253795

Offset: 1

Gus Wiseman, Jan 21 2020

nonn

			The a(4) = 1 through a(7) = 12 rooted trees:
  (ooo)  (oooo)   (ooooo)    (oooooo)
         (oo(o))  (oo(oo))   (oo(ooo))
                  (ooo(o))   (ooo(oo))
                  (o(o)(o))  (oooo(o))
                  (oo((o)))  (o(o)(oo))
                             (oo((oo)))
                             (oo(o)(o))
                             (oo(o(o)))
                             (ooo((o)))
                             ((o)(o)(o))
                             (o(o)((o)))
                             (oo(((o))))

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 500 terms from Andrew Howroyd)

The Matula-Goebel numbers of these trees are given by A033942.
The series-reduced case is A331488.
The lone-child-avoiding case is (also) A331488.
The labeled version is A331577.
Unlabeled rooted trees are counted by A000081.
Cf. A001678, A001679, A004111, A033185, A060313, A206429, A331490, A331578.

g:= proc(n, i, t) option remember; `if`(n=0, `if`(t=0, 1, 0),
      `if`(i<1, 0, add(binomial(g(i-1$2, 0)+j-1, j)*
         g(n-i*j, i-1, max(0, t-j)), j=0..n/i)))
    end:
a:= n-> g(n-1$2, 3):
seq(a(n), n=1..40);  # Alois P. Heinz, Jan 22 2020

urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[urt[n],Length[#]>2&]],{n,10}]
(* Second program: *)
g[n_, i_, t_] := g[n, i, t] = If[n == 0, If[t == 0, 1, 0],
     If[i < 1, 0, Sum[Binomial[g[i - 1, i - 1, 0] + j - 1, j]*
     g[n - i*j, i - 1, Max[0, t - j]], {j, 0, n/i}]]];
a[n_] := g[n-1, n-1, 3];
Array[a, 40] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={my(g=TreeGf(n)); Vec(g - x*(1 + g + (g^2 + subst(g, x, x^2))/2), -n)} \\ Andrew Howroyd, Jan 22 2020

For n > 1, a(n) = Sum_{k > 2} A033185(n - 1, k).

G.f.: f(x) - x*(1 + f(x) + (f(x)^2 + f(x^2))/2) where f(x) is the g.f. of A000081. - Andrew Howroyd, Jan 22 2020

A105820 Triangle giving the numbers of different forests of m trees of smallest order 2, i.e., without isolated vertices.

Original entry on oeis.org

0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 3, 1, 0, 0, 0, 6, 3, 1, 0, 0, 0, 11, 5, 1, 0, 0, 0, 0, 23, 12, 3, 1, 0, 0, 0, 0, 47, 23, 6, 1, 0, 0, 0, 0, 0, 106, 52, 14, 3, 1, 0, 0, 0, 0, 0, 235, 110, 29, 6, 1, 0, 0, 0, 0, 0, 0, 551, 253, 68, 15, 3, 1, 0, 0, 0, 0, 0, 0, 1301, 570, 148, 31, 6, 1, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Washington Bomfim, Apr 25 2005

Forests of order N with m components, m > floor(N/2) must contain an isolated vertex since it is impossible to partition N vertices in floor(N/2) + 1 or more trees without giving only one vertex to a tree.

			a(12) = 1 because 5 nodes can be partitioned into two trees only in one way: one tree gets 3 nodes and the other tree gets 2. Since A000055(3) = A000055(2) = 1, there is only one forest. (The forests of order less than or equal to 5 are depicted in the Weisstein link.)

Alois P. Heinz, Rows n = 1..141, flattened
Eric Weisstein's World of Mathematics, Forest

Cf. A033185, A095133, A105786, A105821.

a(n) = sum over the partitions of N: 1K1 + 2K2 + ... + NKN, with exactly m parts and no part equal to 1, of Product_{i=1..N} binomial(A000055(i)+Ki-1, Ki).

G.f.: 1/Product_{i>=2}(1 - x*y^i)^A000055(i). - Vladeta Jovovic, Apr 27 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).

A181360 Number of forests of rooted trees containing n nodes not counting the root nodes.

Original entry on oeis.org

1, 1, 3, 7, 19, 47, 127, 330, 889, 2378, 6450, 17510, 47907, 131388, 362081, 1000665, 2774857, 7714695, 21505455, 60084062, 168234804, 471977022, 1326558625, 3734804268, 10531738149, 29742332548, 84111212892, 238176473946, 675269414372, 1916715819186

Offset: 0

Peter A. Lawrence, Oct 15 2010

nonn

Every tree in the forest must have at least 2 nodes, i.e. at least one more node besides the root. - N. J. A. Sloane, Nov 26 2010
First, T(n), the number of rooted trees with n+1 nodes A000081(n+1) can be computed using partitions of n as follows: let n = (q1*1 + q2*2 + q3*3 + ... + qn*n) be a nonnegative integer partition of n (the "q"s are the multiplicities of the part sizes), and define a^b to be (a+b-1)! / (a-1)! / b! (the number of ways to color b identical items with a colors), then compute the sum of T(0)^q1 * T(1)^q2 * ... * T(n-1)^qn over all such partitions of n.
Then F(n), the number of forests of rooted trees containing N nodes not counting the roots, can be similarly computed as the sum of T(1)^q1 * T(2)^q2 * ... * T(n)^qn over all such partitions of n.
These are the diagonal sums of the triangle in A174135. - N. J. A. Sloane, Nov 26 2010.

			Trees for example (leaving out the "^0" factors for clarity):
T(0) = 1, T(1) = 1
T(2) = T(1)^1 + T(0)^2 = 2,
T(3) = T(2)^1 + T(1)^1*T(0)^1 + T(0)^3 = 4,
T(4) = T(3)^1 + T(2)^1*T(0)^1 + T(1)^2 + T(1)^1*T(0)^2 +T(0)^4 = 9,
T(5) = T(4)^1 + T(3)^1*T(0)^1 + T(2)^1*T(1)^1 + T(2)^1*T(0)^2 + T(1)^2*T(0)^1 + T(1)^1*T(0)^3 + T(0)^5 = 20.
Forests for example (leaving out the "^0" factors for clarity):
F(2) = T(2)^1 + T(1)^2 = 3,
F(3) = T(3)^1 + T(2)^1*T(1)^1 + T(1)^3 = 7,
F(4) = T(4)^1 + T(3)^1*T(1)^1 + T(2)^2 + T(2)*T(1)^2 + T(1)^4 = 19,
F(5) = T(5)^1 + T(4)^1*T(1)^1 + T(3)^1*T(2)^1 + T(3)^1*T(1)^2 + T(2)^2*T(1)^1 + T(2)^1*T(1)^3 + T(1)^5 = 47.
{Examples of this a^b definition:
2^1 = 2, 2^2 = 3, 2^3 = 4, 2^4 = 5,
3^1 = 3, 3^2 = 6, 3^3 = 10, 3^4 = 15, (triangular numbers)
4^1 = 4, 4^2 = 10, 4^3 = 20, 4^4 = 35, (tetrahedral numbers)
equivalently a^b = (b == 0 ? 1 : (a == 1 || b == 1 ? a : (a * (a+1)^(b-1) / b))) }

N. J. A. Sloane and Alois P. Heinz, Table of n, a(n) for n = 0..2133
A. Mansuy, Preordered forests, packed words and contraction algebras, J. Algebra 411 (2014) 259-311, section 4.1
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.

Cf. A000081 (rooted trees).
Cf. A093637 (products of partition numbers).
Cf. A174135, A033185.

(From N. J. A. Sloane, Nov 26 2010) First read 110 terms of A000081 into array b1
M:=100;
t1:=1/mul((1-x*y^i)^b1[i+1],i=2..M):
t2:=series(t1,y,M):
t3:=series(t2,x,M):
a:=(n,k)->coeff(coeff(t3,x,k),y,n);
g:=n->add(a(n-1+i,i),i=1..n-1);
[seq(g(n),n=1..48)];
# second Maple program:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(T(i-1)+j-1, j) *g(n-i*j, i-1), j=0..n/i)))
    end:
T:= n-> g(n, n):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(T(i)+j-1, j) *b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 20 2012
# third Maple program:
g:= proc(n) option remember; `if`(n<=1, n, (add(add(d*
      g(d), d=numtheory[divisors](j))*g(n-j), j=1..n-1))/(n-1))
    end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*
      g(d+1), d=numtheory[divisors](j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Sep 19 2017

g[n_, i_] := g[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[T[i-1]+j-1, j]*g[n-i*j, i-1], {j, 0, n/i}]]]; T[n_] := g[n, n]; b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[T[i]+j-1, j]*b[n-i*j, i-1], {j, 0, n/i}]]]; a[n_] := b[n, n] // FullSimplify; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)

a(n) ~ c * d^n / n^(3/2), where d = 2.955765285651994974714817524... is the Otter's rooted tree constant (see A051491), and c = 10.088029891871277227771831767... . - Vaclav Kotesovec, May 09 2014
a(n) = A033185(2n, n). - Alois P. Heinz, Feb 15 2016
a(n) = A033185(2n+k, n+k) for all n, k >= 0. - Michael Somos, Aug 20 2018

a(0)=1 prepended by Alois P. Heinz, Sep 19 2017

A271878 Triangle T(n,t) read by rows: number of rooted forests with n 2-colored nodes and t rooted trees.

Original entry on oeis.org

2, 4, 3, 14, 8, 4, 52, 38, 12, 5, 214, 160, 62, 16, 6, 916, 741, 288, 86, 20, 7, 4116, 3416, 1408, 416, 110, 24, 8, 18996, 16270, 6856, 2110, 544, 134, 28, 9, 89894, 78408, 34036, 10576, 2812, 672, 158, 32, 10, 433196, 384033, 169936, 53892, 14352

Offset: 1

R. J. Mathar, Apr 16 2016

See eq. (27) of the reference for a recurrence.

			T(4,2)=28+10=38: That forest has t=2 trees with either n=1+3 or n=2+2 nodes. The splitting 1+3 contributes T(1,1)*T(3,1) = 2*14 = 28; the splitting 2+2 contributes binomial(5,2) = 10 because there are T(2,1)=4 selectable trees and the choice of pairs is A000217(T(2,1)).
2 ;
4 3;
14 8 4;
52 38 12 5;
214 160 62 16 6;
916 741 288 86 20 7 ;
4116 3416 1408 416 110 24 8;
18996 16270 6856 2110 544 134 28 9 ;
89894 78408 34036 10576 2812 672 158 32 10;
433196 384033 169936 53892 14352 3514 800 182 36 11;
2119904 1901968 856902 275264 74238 18128 4216 928 206 40 12;
10503612 9519710 4350520 1416051 384512 94668 21904 4918 1056 230 44 13;
52594476 48061472 22238446 7317080 2002850 494544 115098 25680 5620 1184 254 48 14 ;

Alois P. Heinz, Rows n = 1..141, flattened
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603:00077 [math.CO] (2016), Table 3.

Cf. A033185 (1-colored nodes), A038055 (column k=1), A000151 (row sums), A271879 (3-colored nodes)

g:= proc(n) option remember; `if`(n<2, 2*n, (add(add(d*g(d),
       d=numtheory[divisors](j))*g(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(g(i)+j-1, j), j=0..min(n/i, p)))))
    end:
T:= (n, k)-> b(n$2, k):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Apr 13 2017

g[n_] := g[n] = If[n < 2, 2*n, (Sum[Sum[d*g[d], {d, Divisors[j]}]*g[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[Min[i, p] < 1, 0, Sum[b[n - i*j, i - 1, p - j]*Binomial[g[i] + j - 1, j], {j, 0, Min[n/i, p]}]]]];
T[n_, k_] := b[n, n, k];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)

A271879 Triangle T(n,t) by rows: The number of rooted forests with n 3-colored nodes and t rooted trees.

Original entry on oeis.org

3, 9, 6, 45, 27, 10, 246, 180, 54, 15, 1485, 1143, 405, 90, 21, 9432, 7704, 2856, 720, 135, 28, 62625, 52731, 20682, 5385, 1125, 189, 36, 428319, 369969, 150282, 40914, 8730, 1620, 252, 45, 3000393, 2638332, 1104702, 309510, 68400, 12891, 2205, 324, 55

Offset: 1

R. J. Mathar, Apr 16 2016

See eq. (27) of the reference for a recurrence.

			3 ;
9 6 ;
45 27 10;
246 180 54 15;
1485 1143 405 90 21;
9432 7704 2856 720 135 28;
62625 52731 20682 5385 1125 189 36;
428319 369969 150282 40914 8730 1620 252 45;
3000393 2638332 1104702 309510 68400 12891 2205 324 55;
21410436 19097802 8183943 2353989 531702 103140 17868 2880 405 66;
155106693 139921470 61122222 17954262 4140105 816858 145134 23661 3645 495 78;
1137703869 1035882315 459695791 137490273 32241834 6466053 1164978 194382 30270 4500 594 91 ;
8432624850 7737370857 3479520051 1056731244 251493255 51104574 9331833 1576062 250884 37695 5445 702 105 ;

Alois P. Heinz, Rows n = 1..141, flattened
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603:00077 [math.CO] (2016), Table 4.

Cf. A033185 (1-colored nodes), A038059 (column k=1), A006964 (row sums), A271878 (2-colored nodes).

g:= proc(n) option remember; `if`(n<2, 3*n, (add(add(d*g(d),
       d=numtheory[divisors](j))*g(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(g(i)+j-1, j), j=0..min(n/i, p)))))
    end:
T:= (n, k)-> b(n$2, k):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Apr 13 2017

g[n_] := g[n] = If[n < 2, 3*n, (Sum[Sum[d*g[d], {d, Divisors[j]}]*g[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[Min[i, p] < 1, 0, Sum[b[n - i*j, i - 1, p - j]*Binomial[g[i] + j - 1, j], {j, 0, Min[n/i, p]}]]]];
T[n_, k_] :=  b[n, n, k];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)

A280787 Triangle read by rows: number of topologically distinct sets of n circles with one pair intersecting, by number of factors.

Original entry on oeis.org

1, 3, 1, 10, 4, 1, 30, 15, 4, 1, 91, 50, 16, 4, 1, 268, 162, 55, 16, 4, 1, 790, 506, 185, 56, 16, 4, 1, 2308, 1558, 594, 190, 56, 16, 4, 1, 6737, 4727, 1878, 617, 191, 56, 16, 4, 1, 19609, 14227, 5825, 1970, 622, 191, 56, 16, 4, 1

Offset: 2

N. J. A. Sloane, Jan 20 2017

			Triangle begins:
     1;
     3,    1;
    10,    4,   1;
    30,   15,   4,   1;
    91,   50,  16,   4,  1;
   268,  162,  55,  16,  4,  1;
   790,  506, 185,  56, 16,  4, 1;
  2308, 1558, 594, 190, 56, 16, 4, 1;
...

R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.

Row sums give A280786.

a81[n_] := a81[n] = If[n <= 1, n, Sum[a81[n - j]*DivisorSum[j, #1*a81[#1] &], {j, n - 1}]/(n - 1)];
A027852[n_] := Module[{dh = 0, np}, For[np = 0, np <= n, np++, dh = a81[np]*a81[n - np] + dh]; If[EvenQ[n], dh = a81[n/2] + dh]; dh/2];
A280788[n_] := If[n == 0, 1, Sum[a81[np+1]*A027852[n-np+2], {np, 0, n}]];
t[n_] := t[n] = Module[{d, j}, If[n == 1, 1, 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]}]]]]; A033185[n_, k_] := b[n, n, k];
A280786[n_] := If[n < 2, 0, Sum[A280787[n, f], {f, 1, n - 1}]];
A280787[n_, f_] := A280787[n, f] = Module[{ct}, Which[f == n, Return[0], f == n - 1, Return[1], f == 1, Return[A280786[n - 1] + A280788[n - 2]], True, ct = 0; Do[ct += A280787[np, 1]*A033185[n - np, f - 1], {np, 1, n - 1}]]; ct];
Table[A280787[n, f], {n, 2, 11}, {f, 1, n - 1}] // Flatten (* Jean-François Alcover, Nov 23 2017, after R. J. Mathar and Alois P. Heinz *)

A331577 Number of labeled rooted trees with n vertices and more than two branches of the root.

Original entry on oeis.org

0, 0, 0, 4, 65, 1026, 17857, 349224, 7657281, 186895270, 5037424601, 148805552556, 4784793219505, 166458635341194, 6231891513395745, 249886992888096976, 10686839817678846209, 485632267141865950926, 23370062118676064101801, 1187393725239246382405140

Offset: 1

Gus Wiseman, Jan 21 2020

nonn

			Non-isomorphic representatives of the a(6) = 1026 trees (in the format root[branches]) are:
  1[2,3,4[5[6]]]
  1[2,3[4],5[6]]
  1[2,3,4[5,6]]
  1[2,3,4,5[6]]
  1[2,3,4,5,6]

Andrew Howroyd, Table of n, a(n) for n = 1..200

The series-reduced version is A331578.
The unlabeled version is A331233.
Labeled rooted trees are counted by A000169.
Cf. A000081, A033185, A060313, A060356, A206429, A331488, A331490.

lrt[set_]:=If[Length[set]==0,{},Join@@Table[Apply[root,#]&/@Join@@Table[Tuples[lrt/@stn],{stn,sps[DeleteCases[set,root]]}],{root,set}]];
Table[Length[Select[lrt[Range[n]],Length[#]>2&]],{n,6}]

seq(n)={my(f=serreverse(x*exp(O(x^n) -x ))); Vec(serlaplace(f - x*(1 + f + f^2/2)), -n)} \\ Andrew Howroyd, Jan 23 2020

For n > 1, a(n) = Sum_{k > 2} A206429(n, k).

E.g.f.: f(x) - x*(1 + f(x) + f(x)^2/2), where f(x) is the e.g.f. of A000169. - Andrew Howroyd, Jan 23 2020

cp's OEIS Frontend

A280786 Number of topologically distinct sets of n circles with one pair intersecting.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A291336 Number F(n,h,t) of forests of t unlabeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A331233 Number of unlabeled rooted trees with n vertices and more than two branches of the root.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A105820 Triangle giving the numbers of different forests of m trees of smallest order 2, i.e., without isolated vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A181360 Number of forests of rooted trees containing n nodes not counting the root nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A271878 Triangle T(n,t) read by rows: number of rooted forests with n 2-colored nodes and t rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A271879 Triangle T(n,t) by rows: The number of rooted forests with n 3-colored nodes and t rooted trees.