cp's OEIS Frontend

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

%I A001258 M1678 N0660 #32 May 14 2017 04:36:14
%S A001258 1,1,2,6,25,135,892,6937,61886,621956,6946471,85302935,1141820808,
%T A001258 16540534553,257745010762,4298050731298,76356627952069,
%U A001258 1439506369337319,28699241994332940,603229325513240569,13330768181611378558,308967866671489907656,7493481669479297191451,189793402599733802743015,5010686896406348299630712
%N A001258 Number of labeled n-node trees with unlabeled end-points.
%D A001258 J.W. Moon, Counting Labelled Trees, Issue 1 of Canadian mathematical monographs, Canadian Mathematical Congress, 1970, Sec. 3.9.
%D A001258 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001258 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001258 N. J. A. Sloane, <a href="/A001258/b001258.txt">Table of n, a(n) for n = 2..100</a>
%H A001258 F. Harary, A. Mowshowitz and J. Riordan, <a href="https://doi.org/10.1016/S0021-9800(69)80106-7">Labeled trees with unlabeled end-points</a>, J. Combin. Theory, 6 (1969), 60-64.
%H A001258 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%p A001258 # This gives the sequence but without the initial 1:
%p A001258 with(combinat);
%p A001258 R:=proc(n,k) # this gives A055314
%p A001258 if n=1 then if k=1 then RETURN(1) else RETURN(0); fi
%p A001258     elif (n=2 and k=2) then RETURN(1)
%p A001258     elif (n=2 and k>2) then RETURN(0)
%p A001258     else stirling2(n-2,n-k)*n!/k!;
%p A001258     fi;
%p A001258 end;
%p A001258 Rstar:=proc(n,k) # this gives A213262
%p A001258 if k=2 then
%p A001258      if n <=4 then RETURN(1); else RETURN((n-2)!/2); fi;
%p A001258 else
%p A001258    if k <= n-2 then add(binomial(n-i-1,k-i)*R(n-k,i), i=2..n-1);
%p A001258    elif k=n-1 then 1;
%p A001258    else 0;
%p A001258    fi;
%p A001258 fi;
%p A001258 end;
%p A001258 [seq(add(Rstar(n,k),k=2..n-1),n=3..20)];
%t A001258 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 *)
%t A001258 tStar[2] = 1;
%t A001258 tStar[n_] :=
%t A001258   Sum[(-1)^j Binomial[n - k, j] Binomial[n - 1 - j,
%t A001258      k] (n - k - j)^(n - k - 2), {k, 2, n - 1}, {j, 0, n - k - 1}];
%t A001258 Table[tStar[n], {n, 2, 20}] (* _David Callan_, Jul 18 2014, after Moon reference *)
%Y A001258 Cf. A151880.
%K A001258 nonn,nice
%O A001258 2,3
%A A001258 _N. J. A. Sloane_. More terms from _N. J. A. Sloane_, Jun 07 2012