A095133 Triangle of numbers of forests on n nodes containing k trees.
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, 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, 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
Offset: 1
Examples
Triangle begins:
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, 4, 2, 1, 1;
47, 46, 29, 15, 8, 4, 2, 1, 1;
106, 99, 60, 32, 16, 8, 4, 2, 1, 1;
...
Links
- Alois P. Heinz, Rows n = 1..141, flattened
- Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
- Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 6 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
- Eric Weisstein's World of Mathematics, Forest
Crossrefs
Programs
-
Maple
with(numtheory): b:= proc(n) option remember; local d, j; `if` (n<=1, n, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/(n-1)) end: t:= proc(n) option remember; local k; `if` (n=0, 1, b(n)-(add(b(k)*b(n-k), k=0..n)-`if`(irem(n, 2)=0, b(n/2), 0))/2) end: g:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1, `if`(min(i, p)<1, 0, add(g(n-i*j, i-1, p-j) * binomial(t(i)+j-1, j), j=0..min(n/i, p))))) end: a:= (n, k)-> g(n, n, k): seq(seq(a(n, k), k=1..n), n=1..14); # Alois P. Heinz, Aug 20 2012 -
Mathematica
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 *)
Formula
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
Extensions
More terms from Vladeta Jovovic, Jun 03 2004
Comments