A319580 - OEIS

%I #12 Apr 10 2020 06:16:19

%S 1,3,18,215,3600,80136,2213036,73068543,2806959015,123002168300,

%T 6055381161852,330885794632536,19872950226273053,1301261803764756855,

%U 92259974680854975000,7041606755629152575055,575638367425376279620662,50180725346542105445190603

%N Number of binary rooted trees with n leaves of n colors and all non-leaf nodes having out-degree 2.

%C Not all of the n colors need to be used.

%H Alois P. Heinz, <a href="/A319580/b319580.txt">Table of n, a(n) for n = 1..352</a>

%H V. P. Johnson, <a href="http://people.math.sc.edu/czabarka/Theses/JohnsonThesis.pdf">Enumeration Results on Leaf Labeled Trees</a>, Ph. D. Dissertation, Univ. Southern Calif., 2012.

%p A:= proc(n, k) option remember; `if`(n<2, k*n, `if`(n::odd, 0,

%p       (t-> t*(1-t)/2)(A(n/2, k)))+add(A(i, k)*A(n-i, k), i=1..n/2))

%p     end:

%p a:= n-> A(n$2):

%p seq(a(n), n=1..20);  # _Alois P. Heinz_, Sep 23 2018

%t A[n_, k_] := A[n, k] = If[n < 2, k n, If[OddQ[n], 0, Function[t, t(1-t) / 2][A[n/2, k]]] + Sum[A[i, k] A[n - i, k], {i, 1, n/2}]];

%t a[n_] := A[n, n];

%t Array[a, 20] (* _Jean-François Alcover_, Apr 10 2020, after _Alois P. Heinz_ *)

%o (PARI) a(n)={my(v=vector(n)); v[1]=n; for(n=2, n, v[n]=sum(j=1, (n-1)\2, v[j]*v[n-j]) + if(n%2, 0, binomial(v[n/2]+1, 2))); v[n]} \\ _Andrew Howroyd_, Sep 23 2018

%Y Main diagonal of A319539.

%Y Cf. A319369, A319541.

%K nonn

%O 1,2

%A _Andrew Howroyd_, Sep 23 2018