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.

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

Author

N. J. A. Sloane, Jun 07 2012

Keywords

• nonn
• tabf

Comments

All nodes are labeled except for the end-nodes.

Examples

			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],
...
		

Links

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

Crossrefs

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

Programs

Maple

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

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