login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A144258 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of forests of trees on n or fewer nodes using a subset of labels 1..n and k edges. 2
1, 2, 0, 4, 1, 0, 8, 6, 3, 0, 16, 24, 27, 16, 0, 32, 80, 150, 190, 125, 0, 64, 240, 660, 1335, 1830, 1296, 0, 128, 672, 2520, 7210, 15435, 22449, 16807, 0, 256, 1792, 8736, 33040, 98105, 219912, 335160, 262144, 0, 512, 4608, 28224, 135072, 521010, 1600452, 3727962, 5902236, 4782969, 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 trees

FORMULA

T(n,0) = 2^n, T(n,k) = 0 if k<0 or n<=k, else T(n,k) = n^(n-2) if k=n-1, else 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) = 6, because there are 6 forests of trees on 3 or less nodes using a subset of labels 1,2,3 and 1 edge:

.1-2. .1... ...2. .1-2. .1.2. .1.2.

..... .|... ../.. ..... .|... ../..

..... .3... .3... .3... .3... .3...

Triangle begins:

1;

2,   0;

4,   1,   0;

8,   6,   3,   0;

16, 24,  27,  16,   0;

32, 80, 150, 190, 125,  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-2)

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

CROSSREFS

Columns k=0, 1 give: A000079, A001788. First lower diagonal gives A000272(k+1) with initial term 2. Row sums give: A144259. Cf. A007318, A000142.

Sequence in context: A153345 A140648 A153342 * A056859 A272098 A291929

Adjacent sequences:  A144255 A144256 A144257 * A144259 A144260 A144261

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Sep 16 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 17 23:47 EST 2018. Contains 299297 sequences. (Running on oeis4.)