A248890 Number of rooted trees with n nodes such that for each inner node no more than k subtrees corresponding to its children have exactly k nodes.

0, 1, 1, 1, 2, 4, 8, 16, 34, 75, 166, 374, 849, 1952, 4522, 10566, 24840, 58760, 139693, 333702, 800412, 1927207, 4655997, 11283835, 27423930, 66825194, 163227234, 399587270, 980222058, 2409181633, 5931839530, 14629639579, 36137308192, 89395224033

Offset

0,5

Links

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

Example

:  o  :  o  :  o  :    o   o  :    o     o     o   o  :
:     :  |  :  |  :   / \  |  :    |    / \   / \  |  :
:     :  o  :  o  :  o   o o  :    o   o   o o   o o  :
:     :     :  |  :  |     |  :   / \  |     |   | |  :
:     :     :  o  :  o     o  :  o   o o     o   o o  :
:     :     :     :        |  :  |     |           |  :
:     :     :     :        o  :  o     o           o  :
:     :     :     :           :                    |  :
: n=1 : n=2 : n=3 :  n=4      :  n=5               o  :
:.....:.....:.....:...........:.......................:

Maple

g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=0..min(i, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=0..40);

Mathematica

g[n_, i_] := g[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[g[i-1, i-1]+j-1, j]*g[n-i*j, i-1], {j, 0, Min[i, n/i]}]]]; a[n_] := g[n-1, n-1]; Table[ a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 28 2017, translated from Maple *)

Crossrefs

Cf. A000081, A032305, A045648, A213920.

Sequence in context: A003427 A333647 A045648 * A308245 A209971 A308031

Adjacent sequences: A248887 A248888 A248889 * A248891 A248892 A248893

Keyword

nonn

Author

Alois P. Heinz, Mar 05 2015

Status

approved