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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A144259 Number of forests of trees on n or fewer nodes using a subset of labels 1..n, also row sums of triangle A144258. 2
1, 2, 5, 17, 83, 577, 5425, 65221, 959145, 16703045, 336294539, 7687013743, 196668883339, 5568107204467, 172833125462925, 5836126964882633, 212987232417299345, 8353651173273885025, 350415859403143234243, 15654265239209850186247, 741991467954126579131811 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..150

Index entries for sequences related to trees

FORMULA

a(n) = Sum_{k=0..n} A144258(n,k).

EXAMPLE

a(2) = 5, because there are 5 forests of trees on 2 or less nodes using a subset of labels 1,2:

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

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

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

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: a:= n-> add(T(n, k), k=0..n): seq(a(n), n=0..20);

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}]]; a[n_] := Sum[T[n, k], {k, 0, n}]; Table[a[n], {n, 0, 20}] (* Jean-Fran├žois Alcover, Feb 25 2017, translated from Maple *)

CROSSREFS

Cf. A144258, A007318, A000142.

Sequence in context: A098540 A079574 A032262 * A191799 A079805 A162038

Adjacent sequences:  A144256 A144257 A144258 * A144260 A144261 A144262

KEYWORD

nonn

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 23 13:38 EST 2018. Contains 299581 sequences. (Running on oeis4.)