A151880 -id:A151880 - cp's OEIS frontend

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

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

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

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

Cf. A151880.

# 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)];

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

A213262 Triangle read by rows: R(n,k) (n>=2, k from 2 to n-1 or to 2 if n = 2), where R(n,k) = number of trees with n nodes and k unlabeled end-nodes.

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 1, 12, 9, 3, 1, 60, 52, 18, 4, 1, 360, 360, 136, 30, 5, 1, 2520, 2880, 1205, 280, 45, 6, 1, 20160, 26040, 12090, 3025, 500, 63, 7, 1, 181440, 262080, 134610, 36546, 6375, 812, 84, 8, 1, 1814400, 2903040, 1641360, 484260, 90126, 11935, 1232, 108, 9, 1, 19958400, 35078400, 21712320, 6951840, 1386217, 193326, 20510, 1776, 135, 10, 1

Offset: 2

N. J. A. Sloane, Jun 07 2012

All nodes are labeled except for the end-nodes.

			Triangle begins:
[1],
[1],
[1, 1],
[3, 2, 1],
[12, 9, 3, 1],
[60, 52, 18, 4, 1],
[360, 360, 136, 30, 5, 1],
[2520, 2880, 1205, 280, 45, 6, 1],
[20160, 26040, 12090, 3025, 500, 63, 7, 1],
[181440, 262080, 134610, 36546, 6375, 812, 84, 8, 1],
[1814400, 2903040, 1641360, 484260, 90126, 11935, 1232, 108, 9, 1],
...

F. Harary, A. Mowshowitz and J. Riordan, Labeled trees with unlabeled end-points, J. Combin. Theory, 6 (1969), 60-64.

Row sums give A001258. This is an improved version of A151880.

# This is for n >= 3:
with(combinat);
R:=proc(n,k) # This is for A151880
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)
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;
g:=n->[seq(Rstar(n,k),k=2..n-1)];
[seq(g(n),n=3..16)];

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]; g[n_] := Table[rstar[n, k], {k, 2, n-1}]; Join[{1}, Table[g[n], {n, 3, 13}] // Flatten] (* Jean-François Alcover, Oct 05 2012, translated from Maple *)

cp's OEIS Frontend

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

A213262 Triangle read by rows: R(n,k) (n>=2, k from 2 to n-1 or to 2 if n = 2), where R(n,k) = number of trees with n nodes and k unlabeled end-nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

cp's OEIS Frontend

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

A213262 Triangle read by rows: R*(n,k) (n>=2, k from 2 to n-1 or to 2 if n = 2), where R*(n,k) = number of trees with n nodes and k unlabeled end-nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A213262 Triangle read by rows: R(n,k) (n>=2, k from 2 to n-1 or to 2 if n = 2), where R(n,k) = number of trees with n nodes and k unlabeled end-nodes.