A001258 Number of labeled n-node trees with unlabeled end-points.

1, 1, 2, 6, 25, 135, 892, 6937, 61886, 621956, 6946471, 85302935, 1141820808, 16540534553, 257745010762, 4298050731298, 76356627952069, 1439506369337319, 28699241994332940, 603229325513240569, 13330768181611378558, 308967866671489907656, 7493481669479297191451, 189793402599733802743015, 5010686896406348299630712

Offset: 2

Author

N. J. A. Sloane. More terms from N. J. A. Sloane, Jun 07 2012

Keywords

• nonn
• nice

References

• J.W. Moon, Counting Labelled Trees, Issue 1 of Canadian mathematical monographs, Canadian Mathematical Congress, 1970, Sec. 3.9.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• N. J. A. Sloane, Table of n, a(n) for n = 2..100
• F. Harary, A. Mowshowitz and J. Riordan, Labeled trees with unlabeled end-points, J. Combin. Theory, 6 (1969), 60-64.
• Index entries for sequences related to trees

Crossrefs

Cf. A151880.

Programs

Maple

# This gives the sequence but without the initial 1:
with(combinat);
R:=proc(n,k) # this gives A055314
if n=1 then if k=1 then RETURN(1) else RETURN(0); fi
    elif (n=2 and k=2) then RETURN(1)
    elif (n=2 and k>2) then RETURN(0)
    else stirling2(n-2,n-k)*n!/k!;
    fi;
end;
Rstar:=proc(n,k) # this gives A213262
if k=2 then
     if n <=4 then RETURN(1); else RETURN((n-2)!/2); fi;
else
   if k <= n-2 then add(binomial(n-i-1,k-i)*R(n-k,i), i=2..n-1);
   elif k=n-1 then 1;
   else 0;
   fi;
fi;
end;
[seq(add(Rstar(n,k),k=2..n-1),n=3..20)];

Mathematica

r[n_, k_] := Which[n == 1, If[k == 1, Return[1], Return[0]], n == 2 && k == 2, Return[1], n == 2 && k > 2, Return[0], n > k > 0, StirlingS2[n-2, n-k]*n!/k!, True, 0]; rstar[n_, k_] := Which[k == 2, If[n <= 4, Return[1], Return[(n-2)!/2]], k <= n-2, Sum[Binomial[n-i-1, k-i]*r[n-k, i], {i, 2, n-1}], k == n-1, 1, True, 0]; Join[{1}, Table[Sum[rstar[n, k], {k, 2, n-1}], {n, 3, 26}]] (* Jean-François Alcover, Oct 08 2012, translated from Maple *)
tStar[2] = 1;
tStar[n_] :=
  Sum[(-1)^j Binomial[n - k, j] Binomial[n - 1 - j,
     k] (n - k - j)^(n - k - 2), {k, 2, n - 1}, {j, 0, n - k - 1}];
Table[tStar[n], {n, 2, 20}] (* David Callan, Jul 18 2014, after Moon reference *)