|
%I
%S 1,1,1,1,4,10,20,47,128,340,868,2275,6188,16922,46112,126613,351568,
%T 981622,2747876,7723250,21811856,61828886,175752728,500984606,
%U 1432111244,4104175970,11787811340,33926475162,97837209036,282662156478,818022923184,2371103693427
%N Number of 4-ary search trees on n keys.
%H J. A. Fill and R. P. Dobrow, <a href="http://journals.cambridge.org/article_S0963548397003118">The number of m-ary search trees on n keys</a>, Combin. Probab. Comput. 6 (1997), 435-453.
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%p A:= proc(n) option remember; if n=0 then 1 else convert(series(sum(x^i, i=0..2)+ x^3*A(n-1)^4, x=0,n+1), polynom) fi end: a:= n-> coeff(A(n), x,n): seq(a(n), n=0..40); # _Alois P. Heinz_, Aug 22 2008
%t A[n_] := A[n] = If[n==0, 1, Series[1 + x + x^2 + x^3*A[n-1]^4, {x, 0, n+1}] // Normal]; a[n_] := Coefficient[A[n], x, n]; Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Feb 19 2016, after _Alois P. Heinz_ *)
%K nonn
%O 0,5
%A James Fill (jimfill(AT)jhu.edu)
%E More terms from _Alois P. Heinz_, Aug 22 2008
|
