login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
1, 2, 0, 4, 2, 0, 8, 12, 9, 0, 16, 48, 84, 64, 0, 32, 160, 480, 820, 625, 0, 64, 480, 2160, 6120, 10230, 7776, 0, 128, 1344, 8400, 34720, 94500, 155274, 117649, 0, 256, 3584, 29568, 165760, 647920, 1712592, 2776200, 2097152, 0, 512, 9216, 96768, 701568, 3669120, 13783392, 35630784, 57138120, 43046721, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

Alois P. Heinz, Rows n = 0..140, flattened

Index entries for sequences related to rooted trees

FORMULA

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

EXAMPLE

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:

  .1<2. .2<1. .1<3. .3<1. .2<3. .3<2. .1<2. .2<1. .1<3. .3<1. .2<3. .3<2.

  ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .....

  ..... ..... ..... ..... ..... ..... .3... .3... .2... .2... .1... .1...

Triangle begins:

   1;

   2,   0;

   4,   2,   0;

   8,  12,   9,   0;

  16,  48,  84,  64,   0;

  32, 160, 480, 820, 625,  0;

MAPLE

T:= proc(n, k) option remember;

      if k=0 then 2^n

    elif k<0 or n<=k then 0

    elif k=n-1 then n^(n-1)

    else add(binomial(n-1, j) *T(j+1, j) *T(n-1-j, k-j), j=0..k)

      fi

    end:

seq(seq(T(n, k), k=0..n), n=0..11);

MATHEMATICA

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

CROSSREFS

Columns 0, 1 give A000079, A001815.

First lower diagonal gives A000169 with first term 2.

Row sums give A088957.

Cf. A007318, A000142.

Sequence in context: A319690 A185879 A081880 * A293815 A211318 A324239

Adjacent sequences:  A144286 A144287 A144288 * A144290 A144291 A144292

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Sep 17 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 27 12:45 EST 2020. Contains 332306 sequences. (Running on oeis4.)