login
Number of labeled n-node trees with unlabeled end-points.
(Formerly M1678 N0660)
3

%I M1678 N0660 #32 May 14 2017 04:36:14

%S 1,1,2,6,25,135,892,6937,61886,621956,6946471,85302935,1141820808,

%T 16540534553,257745010762,4298050731298,76356627952069,

%U 1439506369337319,28699241994332940,603229325513240569,13330768181611378558,308967866671489907656,7493481669479297191451,189793402599733802743015,5010686896406348299630712

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

%D J.W. Moon, Counting Labelled Trees, Issue 1 of Canadian mathematical monographs, Canadian Mathematical Congress, 1970, Sec. 3.9.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H N. J. A. Sloane, <a href="/A001258/b001258.txt">Table of n, a(n) for n = 2..100</a>

%H 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 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%p # This gives the sequence but without the initial 1:

%p with(combinat);

%p R:=proc(n,k) # this gives A055314

%p if n=1 then if k=1 then RETURN(1) else RETURN(0); fi

%p elif (n=2 and k=2) then RETURN(1)

%p elif (n=2 and k>2) then RETURN(0)

%p else stirling2(n-2,n-k)*n!/k!;

%p fi;

%p end;

%p Rstar:=proc(n,k) # this gives A213262

%p if k=2 then

%p if n <=4 then RETURN(1); else RETURN((n-2)!/2); fi;

%p else

%p if k <= n-2 then add(binomial(n-i-1,k-i)*R(n-k,i), i=2..n-1);

%p elif k=n-1 then 1;

%p else 0;

%p fi;

%p fi;

%p end;

%p [seq(add(Rstar(n,k),k=2..n-1),n=3..20)];

%t 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 tStar[2] = 1;

%t tStar[n_] :=

%t Sum[(-1)^j Binomial[n - k, j] Binomial[n - 1 - j,

%t k] (n - k - j)^(n - k - 2), {k, 2, n - 1}, {j, 0, n - k - 1}];

%t Table[tStar[n], {n, 2, 20}] (* _David Callan_, Jul 18 2014, after Moon reference *)

%Y Cf. A151880.

%K nonn,nice

%O 2,3

%A _N. J. A. Sloane_. More terms from _N. J. A. Sloane_, Jun 07 2012