cp's OEIS Frontend

A144258 Triangle T(n,k), n >= 0, 0 <= k <= n, read by rows: T(n,k) is the number of forests of trees on n or fewer nodes using a subset of labels 1..n and k edges.

%I A144258 #25 Nov 01 2019 03:22:32
%S A144258 1,2,0,4,1,0,8,6,3,0,16,24,27,16,0,32,80,150,190,125,0,64,240,660,
%T A144258 1335,1830,1296,0,128,672,2520,7210,15435,22449,16807,0,256,1792,8736,
%U A144258 33040,98105,219912,335160,262144,0,512,4608,28224,135072,521010,1600452,3727962,5902236,4782969,0
%N A144258 Triangle T(n,k), n >= 0, 0 <= k <= n, read by rows: T(n,k) is the number of forests of trees on n or fewer nodes using a subset of labels 1..n and k edges.
%H A144258 Alois P. Heinz, <a href="/A144258/b144258.txt">Rows n = 0..140, flattened</a>
%H A144258 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A144258 T(n,0) = 2^n, T(n,k) = 0 if k < 0 or n <= k, otherwise T(n,k) = n^(n-2) if k=n-1, otherwise T(n,k) = Sum_{j=0..k} C(n-1,j)*T(j+1,j)*T(n-1-j,k-j).
%e A144258 T(3,1) = 6, because there are 6 forests of trees on 3 or fewer nodes using a subset of labels 1,2,3 and 1 edge:
%e A144258   .1-2. .1... ...2. .1-2. .1.2. .1.2.
%e A144258   ..... .|... ../.. ..... .|... ../..
%e A144258   ..... .3... .3... .3... .3... .3...
%e A144258 Triangle begins:
%e A144258    1;
%e A144258    2,  0;
%e A144258    4,  1,   0;
%e A144258    8,  6,   3,   0;
%e A144258   16, 24,  27,  16,   0;
%e A144258   32, 80, 150, 190, 125,  0;
%p A144258 T:= proc(n, k) option remember;
%p A144258       if k=0 then 2^n
%p A144258     elif k<0 or n<=k then 0
%p A144258     elif k=n-1 then n^(n-2)
%p A144258     else add(binomial(n-1, j) *T(j+1, j) *T(n-1-j, k-j), j=0..k)
%p A144258       fi
%p A144258     end:
%p A144258 seq(seq(T(n, k), k=0..n), n=0..11);
%t A144258 T[n_, k_] := T[n, k] = Which[k == 0, 2^n, k < 0 || n <= k, 0, k == n-1, n^(n-2), True, Sum[Binomial[n-1, j]*T[j+1, j]*T[n-1-j, k-j], {j, 0, k}]]; Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Aug 29 2014, translated from Maple *)
%Y A144258 Columns k = 0, 1 give A000079, A001788.
%Y A144258 First lower diagonal gives A000272(k+1) with initial term 2.
%Y A144258 Row sums give A144259.
%Y A144258 Cf. A007318, A000142.
%K A144258 nonn,tabl
%O A144258 0,2
%A A144258 _Alois P. Heinz_, Sep 16 2008