login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001258 Number of labeled n-node trees with unlabeled end-points.
(Formerly M1678 N0660)
3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,3

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

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 *)

CROSSREFS

Cf. A151880.

Sequence in context: A317022 A143917 A009326 * A247499 A124373 A010787

Adjacent sequences:  A001255 A001256 A001257 * A001259 A001260 A001261

KEYWORD

nonn,nice

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 13 10:50 EST 2019. Contains 329093 sequences. (Running on oeis4.)