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,7

Comments

Row sums are A005195.

For k > n/2, T(n,k) = T(n-1,k-1). - Geoffrey Critzer, Oct 13 2012

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

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

Example

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;
  ...

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 *)

Crossrefs

Cf. A005195 (row sums), A005196, A106240, A000055 (first column), A274937 (2nd column), A105821.

Limiting sequence of reversed rows gives A215930.

Reflected table is A136605. - Alois P. Heinz, Apr 11 2014

Sequence in context: A352685 A191781 A155092 * A334572 A126081 A268507

Adjacent sequences: A095130 A095131 A095132 * A095134 A095135 A095136

Keyword

nonn,tabl

Author

Eric W. Weisstein, May 29 2004

Extensions

More terms from Vladeta Jovovic, Jun 03 2004

Status

approved