login
Number of forests of exactly n (unlabeled) ordered rooted trees with a total of 2n non-root nodes.
3

%I #13 Dec 21 2020 07:16:44

%S 1,2,8,28,105,384,1442,5388,20317,76712,290790,1104538,4205909,

%T 16044994,61322356,234739140,899911685,3454630372,13278582906,

%U 51098682962,196853475135,759139115962,2930340545406,11321631496180,43779660235746,169429224658130

%N Number of forests of exactly n (unlabeled) ordered rooted trees with a total of 2n non-root nodes.

%C Each tree has at least 1 non-root node.

%H Alois P. Heinz, <a href="/A292668/b292668.txt">Table of n, a(n) for n = 0..1666</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F G.f.: Product_{j>=1} 1/(1-x^j)^A000108(j+1).

%F a(n) = A275431(2n,n).

%F a(n) ~ c * 4^n / n^(3/2), where c = 49.48222899350915021666300344559315... - _Vaclav Kotesovec_, Sep 27 2017

%e : a(2) = 8: (2 trees in each forest having 4 non-root nodes)

%e :

%e : o o . o o . o o . o o . o o . o o . o o . o o .

%e : | | . | | . | | . ( ) | . ( ) | . | ( ) . /|\ | . ( ) ( ) .

%e : o o . o o . o o . o o o . o o o . o o o . o o o o . o o o o .

%e : | . | | . ( ) . | . | . | . . .

%e : o . o o . o o . o . o . o . . .

%e : | . . . . . . . .

%e : o . . . . . . . .

%e :

%p C:= proc(n) option remember; binomial(2*n, n)/(n+1) end:

%p a:= proc(n) option remember; `if`(n=0, 1, add(add(C(d+1)

%p *d, d=numtheory[divisors](j))*a(n-j), j=1..n)/n)

%p end:

%p seq(a(n), n=0..30);

%t c[n_] := c[n] = Binomial[2n, n]/(n+1);

%t a[n_] := a[n] = If[n == 0, 1, Sum[Sum[c[d+1] d, {d, Divisors[j]}] a[n-j], {j, 1, n}]/n];

%t a /@ Range[0, 30] (* _Jean-François Alcover_, Dec 21 2020, after _Alois P. Heinz_ *)

%Y Cf. A000108, A275431.

%K nonn

%O 0,2

%A _Alois P. Heinz_, Sep 20 2017