|
|
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
|
|
|
FORMULA
|
|
|
EXAMPLE
|
a(2) = 5, because there are 5 forests of trees on 2 or fewer 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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|