A245748 Number of identity trees with n nodes where the maximal outdegree (branching factor) equals 3.

1, 3, 9, 25, 66, 170, 431, 1076, 2665, 6560, 16067, 39219, 95476, 231970, 562736, 1363640, 3301586, 7988916, 19322585, 46722160, 112955614, 273063236, 660116215, 1595906490, 3858740567, 9331539319, 22570697689, 54605064084, 132137719127, 319841444030

Offset

7,2

Links

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

Formula

a(n) = A116379(n) - A063895(n+1).

Maple

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b(i-1$2, k$2), j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> b(n-1$2, 3$2) -b(n-1$2, 2$2):
seq(a(n), n=7..60);

Mathematica

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i<1, 0, Sum[Binomial[ b[i-1, i-1, k, k], j]*b[n - i*j, i-1, t - j, k], {j, 0, Min[t, n/i]}]]];
a[n_] := b[n-1, n-1, 3, 3] - b[n-1, n-1, 2, 2];
Table[a[n], {n, 7, 60}] (* Jean-François Alcover, Aug 28 2021, after Maple code *)

Crossrefs

Column k=3 of A244523.

Sequence in context: A058396 A006809 A081663 * A181383 A106514 A325915

Adjacent sequences: A245745 A245746 A245747 * A245749 A245750 A245751

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Jul 31 2014

Status

approved