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

0, 1, 1, 1, 3, 5, 9, 20, 42, 87, 189, 419, 926, 2080, 4724, 10783, 24785, 57374, 133454, 311882, 732084, 1725019, 4078661, 9674563, 23014591, 54894296, 131254246, 314544591, 755369735, 1817530413, 4381176005, 10578753769, 25583847608, 61964393295, 150288117481

Offset

0,5

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) = 5:
:     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

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, `if`(n=v, 1, add(binomial(j-1+
       A(i, h), 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=0..n-1))
    end:
a:= n-> A(n, n):
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, If[n==v, 1, Sum[Binomial[j-1+A[i, h], 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, 0, n-1}]]; a[n_] := A[n, n]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 21 2017, translated from Maple *)

Crossrefs

Cf. A000081, A259863, A260403, A257654, A253244.

Sequence in context: A146251 A281732 A066777 * A065901 A053662 A050355

Adjacent sequences: A260350 A260351 A260352 * A260354 A260355 A260356

Keyword

nonn

Author

Alois P. Heinz, Jul 23 2015

Status

approved