cp's OEIS Frontend

A144289 Triangle T(n,k), n >= 0, 0 <= k <= n, read by rows: Number T(n,k) of forests of labeled rooted trees on n or fewer nodes using a subset of labels 1..n and k edges.

%I A144289 #30 Nov 01 2019 03:22:41
%S A144289 1,2,0,4,2,0,8,12,9,0,16,48,84,64,0,32,160,480,820,625,0,64,480,2160,
%T A144289 6120,10230,7776,0,128,1344,8400,34720,94500,155274,117649,0,256,3584,
%U A144289 29568,165760,647920,1712592,2776200,2097152,0,512,9216,96768,701568,3669120,13783392,35630784,57138120,43046721,0
%N A144289 Triangle T(n,k), n >= 0, 0 <= k <= n, read by rows: Number T(n,k) of forests of labeled rooted trees on n or fewer nodes using a subset of labels 1..n and k edges.
%H A144289 Alois P. Heinz, <a href="/A144289/b144289.txt">Rows n = 0..140, flattened</a>
%H A144289 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A144289 T(n,0) = 2^n, T(n,k) = 0 if k < 0 or n <= k, otherwise T(n,k) = n^(n-1) 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 A144289 T(3,1) = 12, because there are 12 forests of labeled rooted trees on 3 or fewer nodes using a subset of labels 1..3 and 1 edge:
%e A144289   .1<2. .2<1. .1<3. .3<1. .2<3. .3<2. .1<2. .2<1. .1<3. .3<1. .2<3. .3<2.
%e A144289   ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .....
%e A144289   ..... ..... ..... ..... ..... ..... .3... .3... .2... .2... .1... .1...
%e A144289 Triangle begins:
%e A144289    1;
%e A144289    2,   0;
%e A144289    4,   2,   0;
%e A144289    8,  12,   9,   0;
%e A144289   16,  48,  84,  64,   0;
%e A144289   32, 160, 480, 820, 625,  0;
%p A144289 T:= proc(n,k) option remember;
%p A144289       if k=0 then 2^n
%p A144289     elif k<0 or n<=k then 0
%p A144289     elif k=n-1 then n^(n-1)
%p A144289     else add(binomial(n-1, j) *T(j+1, j) *T(n-1-j, k-j), j=0..k)
%p A144289       fi
%p A144289     end:
%p A144289 seq(seq(T(n, k), k=0..n), n=0..11);
%t A144289 T[n_, k_] := T[n, k] = Which[k == 0, 2^n, k<0 || n <= k, 0, k == n-1, n^(n-1), True, Sum[Binomial[n-1, j]*T[j+1, j]*T[n-1-j, k-j], {j, 0, k}]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 11}] // Flatten (* _Jean-François Alcover_, Jan 21 2014, translated from _Alois P. Heinz_'s Maple code *)
%Y A144289 Columns 0, 1 give A000079, A001815.
%Y A144289 First lower diagonal gives A000169 with first term 2.
%Y A144289 Row sums give A088957.
%Y A144289 Cf. A007318, A000142.
%K A144289 nonn,tabl
%O A144289 0,2
%A A144289 _Alois P. Heinz_, Sep 17 2008