cp's OEIS Frontend

A095133 Triangle of numbers of forests on n nodes containing k trees.

%I A095133 #49 Feb 16 2025 08:32:53
%S A095133 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 A095133 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 A095133 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 A095133 Triangle of numbers of forests on n nodes containing k trees.
%C A095133 Row sums are A005195.
%C A095133 For k > n/2, T(n,k) = T(n-1,k-1). - _Geoffrey Critzer_, Oct 13 2012
%H A095133 Alois P. Heinz, <a href="/A095133/b095133.txt">Rows n = 1..141, flattened</a>
%H A095133 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 A095133 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 A095133 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Forest.html">Forest</a>
%F A095133 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 A095133 Triangle begins:
%e A095133     1;
%e A095133     1,  1;
%e A095133     1,  1,  1;
%e A095133     2,  2,  1,  1;
%e A095133     3,  3,  2,  1,  1;
%e A095133     6,  6,  4,  2,  1, 1;
%e A095133    11, 11,  7,  4,  2, 1, 1;
%e A095133    23, 23, 14,  8,  4, 2, 1, 1;
%e A095133    47, 46, 29, 15,  8, 4, 2, 1, 1;
%e A095133   106, 99, 60, 32, 16, 8, 4, 2, 1, 1;
%e A095133   ...
%p A095133 with(numtheory):
%p A095133 b:= proc(n) option remember; local d, j; `if` (n<=1, n,
%p A095133       (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/(n-1))
%p A095133     end:
%p A095133 t:= proc(n) option remember; local k; `if` (n=0, 1,
%p A095133       b(n)-(add(b(k)*b(n-k), k=0..n)-`if`(irem(n, 2)=0, b(n/2), 0))/2)
%p A095133     end:
%p A095133 g:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
%p A095133       `if`(min(i, p)<1, 0, add(g(n-i*j, i-1, p-j) *
%p A095133        binomial(t(i)+j-1, j), j=0..min(n/i, p)))))
%p A095133     end:
%p A095133 a:= (n, k)-> g(n, n, k):
%p A095133 seq(seq(a(n, k), k=1..n), n=1..14);  # _Alois P. Heinz_, Aug 20 2012
%t A095133 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 A095133 Cf. A005195 (row sums), A005196, A106240, A000055 (first column), A274937 (2nd column), A105821.
%Y A095133 Limiting sequence of reversed rows gives A215930.
%Y A095133 Reflected table is A136605. - _Alois P. Heinz_, Apr 11 2014
%K A095133 nonn,tabl
%O A095133 1,7
%A A095133 _Eric W. Weisstein_, May 29 2004
%E A095133 More terms from _Vladeta Jovovic_, Jun 03 2004