A144259 Number of forests of trees on n or fewer nodes using a subset of labels 1..n, also row sums of triangle A144258.
1, 2, 5, 17, 83, 577, 5425, 65221, 959145, 16703045, 336294539, 7687013743, 196668883339, 5568107204467, 172833125462925, 5836126964882633, 212987232417299345, 8353651173273885025, 350415859403143234243, 15654265239209850186247, 741991467954126579131811
Offset: 0
Keywords
Examples
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. ..... ..... ..... ..... .....
Links
Programs
-
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 *)
Formula
a(n) = Sum_{k=0..n} A144258(n,k).