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

0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 2, 2, 0, 1, 3, 3, 1, 2, 6, 6, 3, 6, 11, 11, 9, 15, 23, 24, 25, 39, 48, 52, 67, 96, 107, 122, 174, 242, 247, 295, 448, 598, 598, 744, 1141, 1493, 1493, 1913, 2898, 3730, 3826, 5003, 7362, 9396, 9980, 13201, 18757, 23840

Offset

0,14

Comments

These trees are also counted by A260353 and A260403.

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) = 1:     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(`if`(j=k, 0,
      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..60);

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[If[j==k, 0, 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, 60}] (* Jean-François Alcover, Feb 21 2017, translated from Maple *)

Crossrefs

Cf. A000081, A259863, A260353, A260403, A253244.

Sequence in context: A185287 A276554 A297323 * A167637 A343489 A360742

Adjacent sequences: A257651 A257652 A257653 * A257655 A257656 A257657

Keyword

nonn

Author

Alois P. Heinz, Jul 25 2015

Status

approved