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
1, 1, 1, 1, 4, 3, 2, 14, 27, 15, 3, 48, 180, 240, 105, 6, 171, 1089, 2604, 2625, 945, 11, 614, 6333, 24180, 42075, 34020, 10395, 23, 2270, 36309, 207732, 554820, 755370, 509355, 135135, 46, 8518, 207255, 1710108, 6578550, 13408740, 14963130, 8648640, 2027025 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

See table 2.2 in the Johnson reference.

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.

FORMULA

T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319539(n,i).

EXAMPLE

Triangle begins:

   1;

   1,    1;

   1,    4,     3;

   2,   14,    27,     15;

   3,   48,   180,    240,    105;

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

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

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

  ...

MAPLE

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

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

    end:

T:= (n, k)-> add((-1)^i*binomial(k, i)*A(n, k-i), i=0..k):

seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Sep 23 2018

MATHEMATICA

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

Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-Fran├žois Alcover, Sep 02 2019, after Alois P. Heinz *)

PROG

(PARI) \\ here R(n, k) is k-th column of A319539 as a vector.

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}

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])))}

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

CROSSREFS

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

Main diagonal is A001147.

Row sums give A319590.

Cf. A241555, A319376, A319539.

Sequence in context: A099406 A274601 A202696 * A239020 A293211 A061312

Adjacent sequences:  A319538 A319539 A319540 * A319542 A319543 A319544

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Sep 22 2018

STATUS

approved

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 October 21 14:56 EDT 2019. Contains 328301 sequences. (Running on oeis4.)