A006965 Number of directed trees with n nodes. (Formerly M1677)

1, 2, 6, 25, 114, 591, 3298, 19532, 120687, 771373, 5061741, 33943662, 231751331, 1606587482, 11283944502, 80157645245, 575105238243, 4162624144308, 30365913761136, 223075674659696, 1649166676341180, 12262121068089094, 91649977839972636, 688288656744067230

Offset

1,2

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1093

P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Quebec, 1992, Vol. 16, No. 1, 53-80.

P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)

Index entries for sequences related to trees

Maple

with(combstruct):B:=x->add(3*count([S, {B = Set(S), S = Prod(B, B, B, Z)}, unlabeled], size=i)*x^i, i=1..50); seq(coeff(B(x)-B(x)^2/2+B(x^2)/2, x, n)/3, n=1..30); # with Algolib (Pab Ter)
# second Maple program:
b:= proc(n) option remember; `if`(n<2, 3*n, (add(add(b(d)
      *d, d=numtheory[divisors](j))*b(n-j), j=1..n-1))/(n-1))
    end:
a:= n-> `if`(n=0, 1, b(n)-(add(b(k) *b(n-k), k=0..n)-
        `if`(irem(n, 2)=0, b(n/2), 0))/2)/3:
seq(a(n), n=1..30);  # Alois P. Heinz, Jun 03 2020

Mathematica

b[n_] := b[n] = If[n < 2, 3 n, (Sum[Sum[b[d] d, {d, Divisors[j]}] b[n - j], {j, 1, n - 1}])/(n - 1)];
a[n_] := If[n == 0, 1, b[n] - (Sum[b[k] b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]/3;
Array[a, 30] (* Jean-François Alcover, Nov 01 2020, after Alois P. Heinz *)

Crossrefs

Equals (1/3) A038060(n).

Row sums of A335362.

Sequence in context: A229042 A269484 A014277 * A202705 A058801 A321720

Adjacent sequences: A006962 A006963 A006964 * A006966 A006967 A006968

Keyword

nonn

Author

Simon Plouffe

Status

approved