cp's OEIS Frontend

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

%I A106235 #15 Dec 24 2015 02:45:50
%S A106235 0,1,0,2,0,0,4,1,0,0,9,2,0,0,0,20,7,1,0,0,0,48,17,2,0,0,0,0,115,48,7,
%T A106235 1,0,0,0,0,286,124,21,2,0,0,0,0,0,719,336,60,7,1,0,0,0,0,0,1842,888,
%U A106235 171,21,2,0,0,0,0,0,0,4766,2393,488,65,7,1,0,0,0,0,0,0
%N A106235 Triangle of the numbers of different forests of m rooted trees of smallest order 2, i.e., without isolated vertices.
%C A106235 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. A033185(n) = A106235(n) + A106234(n).
%H A106235 Alois P. Heinz, <a href="/A106235/b106235.txt">Rows n = 1..141, flattened</a>
%F A106235 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(A000081(i)+Ki-1, Ki).
%e A106235 a(12)=2 because 5 nodes can be partitioned in two trees only in a way: one tree gets 3 nodes and the other tree gets 2. Since A000081(3) = 2 and A000081(2)=1, there are two forests.
%e A106235 Triangle T(n,k) begins:
%e A106235     0;
%e A106235     1,   0;
%e A106235     2,   0,  0;
%e A106235     4,   1,  0, 0;
%e A106235     9,   2,  0, 0, 0;
%e A106235    20,   7,  1, 0, 0, 0;
%e A106235    48,  17,  2, 0, 0, 0, 0;
%e A106235   115,  48,  7, 1, 0, 0, 0, 0;
%e A106235   286, 124, 21, 2, 0, 0, 0, 0, 0;
%e A106235   719, 336, 60, 7, 1, 0, 0, 0, 0, 0;
%p A106235 with(numtheory):
%p A106235 g:= proc(n) option remember; `if`(n<=1, n, (add(add(
%p A106235       d*g(d), d=divisors(j))*g(n-j), j=1..n-1))/(n-1))
%p A106235     end:
%p A106235 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i=1,
%p A106235       0, expand(add(x^j*b(n-i*j, i-1)*
%p A106235       binomial(g(i)+j-1, j), j=0..n/i))))
%p A106235     end:
%p A106235 T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
%p A106235 seq(T(n), n=1..14);  # _Alois P. Heinz_, Jun 25 2014
%t A106235 g[n_] := g[n] = If[n <= 1, n, (Sum[Sum[d*g[d], {d, Divisors[j]}]*g[n-j], {j, 1, n-1}])/(n-1)]; b[n_, i_] := b[n, i] = If[n == 0, 1, If[i == 1, 0, Expand[Sum[x^j*b[n-i*j, i-1]*Binomial[g[i]+j-1, j], {j, 0, n/i}]]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, n]]; Table[T[n], {n, 1, 14}] // Flatten (* _Jean-François Alcover_, Nov 05 2015, after _Alois P. Heinz_ *)
%Y A106235 Cf. A033185, A106234.
%K A106235 nonn,tabl
%O A106235 1,4
%A A106235 _Washington Bomfim_, Apr 26 2005