A253014 a(n) = number of unlabeled rooted trees on n nodes with an odd number of endpoints.

1, 1, 1, 2, 4, 10, 24, 58, 142, 359, 919, 2384, 6240, 16487, 43894, 117689, 317400, 860585, 2344280, 6413109, 17610746, 48527584, 134141036, 371862499, 1033586232, 2879818131, 8041864259, 22503532974, 63093269641, 177213423131

Offset

1,4

Links

Table of n, a(n) for n=1..30.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973; see pp. 51-55.

Marko Riedel, Unlabled rooted trees with even and odd numbers of endpoints

Maple

T :=
proc(n)
    option remember;
    local k, s, A;
    if n=0 then return 0 fi;
    if n=1 then return u fi;
    A := n -> add(subs(u=u^l, T(n/l))/l,
                  l in divisors(n));
    s := (1-u)*A(n-1);
    s := s + 1/(n-1)*
    add((k+1)*A(k+1)*T(n-1-k), k=0..n-2);
    expand(s);
end;

Crossrefs

Cf. A000081, A253013.

Sequence in context: A163271 A178036 A191625 * A110236 A191828 A065161

Adjacent sequences: A253011 A253012 A253013 * A253015 A253016 A253017

Keyword

nonn

Author

Marko Riedel, Dec 25 2014

Status

approved