A213262 - OEIS

%I #26 Dec 25 2023 18:10:40

%S 1,1,1,1,3,2,1,12,9,3,1,60,52,18,4,1,360,360,136,30,5,1,2520,2880,

%T 1205,280,45,6,1,20160,26040,12090,3025,500,63,7,1,181440,262080,

%U 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

%N 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.

%C All nodes are labeled except for the end-nodes.

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

%e Triangle begins:

%e [1],

%e [1],

%e [1, 1],

%e [3, 2, 1],

%e [12, 9, 3, 1],

%e [60, 52, 18, 4, 1],

%e [360, 360, 136, 30, 5, 1],

%e [2520, 2880, 1205, 280, 45, 6, 1],

%e [20160, 26040, 12090, 3025, 500, 63, 7, 1],

%e [181440, 262080, 134610, 36546, 6375, 812, 84, 8, 1],

%e [1814400, 2903040, 1641360, 484260, 90126, 11935, 1232, 108, 9, 1],

%e ...

%p # This is for n >= 3:

%p with(combinat);

%p R:=proc(n,k) # This is for A151880

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

%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 g:=n->[seq(Rstar(n,k),k=2..n-1)];

%p [seq(g(n),n=3..16)];

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

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

%K nonn,tabf

%O 2,5

%A _N. J. A. Sloane_, Jun 07 2012