|
%I #48 Oct 02 2017 02:11:37
%S 1,1,1,1,1,1,2,2,1,1,3,3,2,1,1,6,6,4,2,1,1,11,11,7,4,2,1,1,23,23,14,8,
%T 4,2,1,1,47,46,29,15,8,4,2,1,1,106,99,60,32,16,8,4,2,1,1,235,216,128,
%U 66,33,16,8,4,2,1,1,551,488,284,143,69,34,16,8,4,2,1,1,1301,1121,636,315,149,70,34,16,8,4,2,1,1
%N Triangle of numbers of forests on n nodes containing k trees.
%C Row sums are A005195.
%C For k > n/2, T(n,k) = T(n-1,k-1). - _Geoffrey Critzer_, Oct 13 2012
%H Alois P. Heinz, <a href="/A095133/b095133.txt">Rows n = 1..141, flattened</a>
%H Peter Steinbach, <a href="/A000055/a000055_12.pdf">Field Guide to Simple Graphs, Volume 3</a>, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H Peter Steinbach, <a href="/A000664/a000664_6.pdf">Field Guide to Simple Graphs, Volume 4</a>, Part 6 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Forest.html">Forest</a>
%F T(n, k) = sum over the partitions of n, 1M1 + 2M2 + ... + nMn, with exactly k parts, of Product_{i=1..n} binomial(A000055(i) + Mi - 1, Mi). - _Washington Bomfim_, May 12 2005
%e Triangle begins:
%e 1;
%e 1, 1;
%e 1, 1, 1;
%e 2, 2, 1, 1;
%e 3, 3, 2, 1, 1;
%e 6, 6, 4, 2, 1, 1;
%e 11, 11, 7, 4, 2, 1, 1;
%e 23, 23, 14, 8, 4, 2, 1, 1;
%e 47, 46, 29, 15, 8, 4, 2, 1, 1;
%e 106, 99, 60, 32, 16, 8, 4, 2, 1, 1;
%e ...
%p with(numtheory):
%p b:= proc(n) option remember; local d, j; `if` (n<=1, n,
%p (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/(n-1))
%p end:
%p t:= proc(n) option remember; local k; `if` (n=0, 1,
%p b(n)-(add(b(k)*b(n-k), k=0..n)-`if`(irem(n, 2)=0, b(n/2), 0))/2)
%p end:
%p g:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
%p `if`(min(i, p)<1, 0, add(g(n-i*j, i-1, p-j) *
%p binomial(t(i)+j-1, j), j=0..min(n/i, p)))))
%p end:
%p a:= (n, k)-> g(n, n, k):
%p seq(seq(a(n, k), k=1..n), n=1..14); # _Alois P. Heinz_, Aug 20 2012
%t nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);ft=Table[a[i]-Sum[a[j]a[i-j],{j,1,i/2}]+If[OddQ[i],0,a[i/2](a[i/2]+1)/2],{i,1,nn}];CoefficientList[Series[Product[1/(1-y x^i)^ft[[i]],{i,1,nn}],{x,0,20}],{x,y}]//Grid (* _Geoffrey Critzer_, Oct 13 2012, after code given by _Robert A. Russell_ in A000055 *)
%Y Cf. A005195 (row sums), A005196, A106240, A000055 (first column), A274937 (2nd column), A105821.
%Y Limiting sequence of reversed rows gives A215930.
%Y Reflected table is A136605. - _Alois P. Heinz_, Apr 11 2014
%K nonn,tabl
%O 1,7
%A _Eric W. Weisstein_, May 29 2004
%E More terms from _Vladeta Jovovic_, Jun 03 2004
|
