cp's OEIS Frontend

A136605 Triangle read by rows: T(n,k) = number of forests on n unlabeled nodes with k edges (n>=1, 0<=k<=n-1).

%I A136605 #19 Nov 11 2014 04:56:11
%S A136605 1,1,1,1,1,1,1,1,2,2,1,1,2,3,3,1,1,2,4,6,6,1,1,2,4,7,11,11,1,1,2,4,8,
%T A136605 14,23,23,1,1,2,4,8,15,29,46,47,1,1,2,4,8,16,32,60,99,106,1,1,2,4,8,
%U A136605 16,33,66,128,216,235,1,1,2,4,8,16,34,69,143,284,488,551,1,1,2,4,8,16,34,70,149,315,636,1121,1301
%N A136605 Triangle read by rows: T(n,k) = number of forests on n unlabeled nodes with k edges (n>=1, 0<=k<=n-1).
%D A136605 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.
%H A136605 Alois P. Heinz, <a href="/A136605/b136605.txt">Rows n = 1..141, flattened</a>
%F A136605 G.f.: Product_{k>=1} 1/(1 - y^(k-1)*x^k)^A000055(k). - _Geoffrey Critzer_, Nov 10 2014
%e A136605 Triangle begins:
%e A136605 1
%e A136605 1,1
%e A136605 1,1,1
%e A136605 1,1,2,2
%e A136605 1,1,2,3,3
%e A136605 1,1,2,4,6,6 <- T(6,3) = 4 forests on 6 nodes with 3 edges.
%e A136605 1,1,2,4,7,11,11
%e A136605 1,1,2,4,8,14,23,23
%e A136605 1,1,2,4,8,15,29,46,47
%e A136605 1,1,2,4,8,16,32,60,99,106
%e A136605 1,1,2,4,8,16,33,66,128,216,235
%e A136605 1,1,2,4,8,16,34,69,143,284,488,551
%e A136605 1,1,2,4,8,16,34,70,149,315,636,1121,1301
%e A136605 1,1,2,4,8,16,34,71,152,330,710,1467,2644,3159
%p A136605 with(numtheory):
%p A136605 b:= proc(n) option remember; `if`(n<=1, n, (add(add(
%p A136605       d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1))
%p A136605     end:
%p A136605 t:= n-> `if`(n=0, 1, b(n)-(add(b(k)*b(n-k), k=0..n)-
%p A136605         `if`(irem(n, 2)=0, b(n/2), 0))/2):
%p A136605 g:= proc(n, i) option remember; `if`(n=0, 1,
%p A136605       `if`(i<1, 0, expand(add(binomial(t(i)+j-1, j)*
%p A136605        g(n-i*j, i-1)*x^j, j=0..n/i))))
%p A136605     end:
%p A136605 T:= n-> (p-> seq(coeff(p, x, n-i), i=0..n-1))(g(n$2)):
%p A136605 seq(T(n), n=1..14);  # _Alois P. Heinz_, Apr 11 2014
%t A136605 b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}])/(n-1)]; t[n_] := If[n == 0, 1, b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; g[n_, i_] := g[n, i] = If[n == 0, 1, If[i < 1, 0, Expand[Sum[Binomial[t[i] + j - 1, j]*g[n - i*j, i-1]*x^j, {j, 0, n/i}]]]]; T[n_] := CoefficientList[g[n, n], x] // Reverse // Most; Table[T[n], {n, 1, 14}] // Flatten (* _Jean-François Alcover_, Apr 16 2014, after _Alois P. Heinz_ *)
%Y A136605 Row sums give A005195. Rightmost diagonal gives A000055. Cf. A001858, A138464.
%Y A136605 Rows converge to A215930. Reflected table is A095133. - _Alois P. Heinz_, Apr 11 2014
%K A136605 nonn,tabl
%O A136605 1,9
%A A136605 _N. J. A. Sloane_, May 09 2008