A260403 Number of unlabeled rooted trees with n nodes where the outdegrees (branching factors) of adjacent nodes differ by at most one.

0, 1, 1, 1, 1, 2, 3, 5, 8, 14, 24, 43, 76, 138, 250, 460, 848, 1576, 2939, 5516, 10382, 19629, 37221, 70820, 135097, 258426, 495460, 952083, 1833176, 3536502, 6834408, 13229829, 25649202, 49799891, 96821854, 188485968, 367375883, 716872030, 1400373358

Offset

0,6

Links

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

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

Example

a(5) = 2:
:    o      o
:    |     / \
:    o    o   o
:    |    |   |
:    o    o   o
:    |
:    o
:    |
:    o

Maple

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

Mathematica

b[n_, i_, h_, v_] := b[n, i, h, v] = If[n==0, If[v==0, 1, 0], If[i<1 || v<1 || n<v, 0, Sum[Binomial[A[i, h]+j-1, j]*b[n-i*j, i-1, h, v-j], {j, 0, Min[n/i, v]}]]]; A[n_, k_] := A[n, k] = If[n==0, 0, Sum[b[n-1, n-1, j, j], {j, Max[k-1, 0], Min[k+1, n-1]}]]; a[n_] := Sum[b[n-1, n-1, j, j], {j, 0, n-1}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 21 2017, translated from Maple *)

Crossrefs

Cf. A000081, A259863, A260353, A257654, A253244.

Sequence in context: A343161 A274110 A347018 * A127603 A108351 A038495

Adjacent sequences: A260400 A260401 A260402 * A260404 A260405 A260406

Keyword

nonn

Author

Alois P. Heinz, Jul 24 2015

Status

approved