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

 

Logo


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

%I

%S 1,1,1,1,4,3,2,14,27,15,3,48,180,240,105,6,171,1089,2604,2625,945,11,

%T 614,6333,24180,42075,34020,10395,23,2270,36309,207732,554820,755370,

%U 509355,135135,46,8518,207255,1710108,6578550,13408740,14963130,8648640,2027025

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

%C See table 2.2 in the Johnson reference.

%H Alois P. Heinz, <a href="/A319541/b319541.txt">Rows n = 1..141, flattened</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(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319539(n,i).

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 4, 3;

%e 2, 14, 27, 15;

%e 3, 48, 180, 240, 105;

%e 6, 171, 1089, 2604, 2625, 945;

%e 11, 614, 6333, 24180, 42075, 34020, 10395;

%e 23, 2270, 36309, 207732, 554820, 755370, 509355, 135135;

%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 T:= (n, k)-> add((-1)^i*binomial(k, i)*A(n, k-i), i=0..k):

%p seq(seq(T(n, k), k=1..n), n=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 T[n_, k_] := Sum[(-1)^i Binomial[k, i] A[n, k - i], {i, 0, k}];

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

%o (PARI) \\ here R(n,k) is k-th column of A319539 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 M(n)={my(v=vector(n, k, R(n,k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*v[i])))}

%o {my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}

%Y Columns 1..5 are A001190, A220819, A220820, A220821, A220822.

%Y Main diagonal is A001147.

%Y Row sums give A319590.

%Y Cf. A241555, A319376, A319539.

%K nonn,tabl

%O 1,5

%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 21 06:00 EST 2019. Contains 329350 sequences. (Running on oeis4.)