login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A319539 Array read by antidiagonals: T(n,k) is the number of binary rooted trees with n leaves of k colors and all non-leaf nodes having out-degree 2. 9

%I

%S 1,2,1,3,3,1,4,6,6,2,5,10,18,18,3,6,15,40,75,54,6,7,21,75,215,333,183,

%T 11,8,28,126,495,1260,1620,636,23,9,36,196,987,3600,8010,8208,2316,46,

%U 10,45,288,1778,8568,28275,53240,43188,8610,98,11,55,405,2970,17934,80136,232500,366680,232947,32763,207

%N Array read by antidiagonals: T(n,k) is the number of binary rooted trees with n leaves of k colors and all non-leaf nodes having out-degree 2.

%C Not all k colors need to be used. The total number of nodes will be 2n-1.

%C See table 2.1 in the Johnson reference.

%H Andrew Howroyd, <a href="/A319539/b319539.txt">Table of n, a(n) for n = 1..1275</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.

%F T(1,k) = k.

%F T(n,k) = (1/2)*([n mod 2 == 0]*T(n/2,k) + Sum_{j=1..n-1} T(j,k)*T(n-j,k)).

%F G.f. of k-th column R(x) satisfies R(k) = k*x + (R(x)^2 + R(x^2))/2.

%e Array begins:

%e ===========================================================

%e n\k| 1 2 3 4 5 6 7

%e ---+-------------------------------------------------------

%e 1 | 1 2 3 4 5 6 7 ...

%e 2 | 1 3 6 10 15 21 28 ...

%e 3 | 1 6 18 40 75 126 196 ...

%e 4 | 2 18 75 215 495 987 1778 ...

%e 5 | 3 54 333 1260 3600 8568 17934 ...

%e 6 | 6 183 1620 8010 28275 80136 194628 ...

%e 7 | 11 636 8208 53240 232500 785106 2213036 ...

%e 8 | 23 2316 43188 366680 1979385 7960638 26037431 ...

%e 9 | 46 8610 232947 2590420 17287050 82804806 314260765 ...

%e ...

%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 seq(seq(A(n, 1+d-n), n=1..d), d=1..12); # _Alois P. Heinz_, Sep 23 2018

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

%t Table[A[n, d-n+1], {d, 1, 12}, {n, 1, d}] // Flatten (* _Jean-Fran├žois Alcover_, Sep 02 2019, after _Alois P. Heinz_ *)

%o (PARI) \\ here R(n,k) gives k-th column as a vector.

%o R(n,k)={my(v=vector(n)); v[1]=k; 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}

%o {my(T=Mat(vector(8, k, R(8, k)~))); for(n=1, #T~, print(T[n,]))}

%Y Columns 1..5 are A001190, A083563, A220816, A220817, A220818.

%Y Main diagonal is A319580.

%Y Cf. A241555, A319254, A319541.

%K nonn,tabl,look

%O 1,2

%A _Andrew Howroyd_, Sep 22 2018

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 22 08:33 EST 2019. Contains 329389 sequences. (Running on oeis4.)