A336524 Triangular array read by rows. T(n,k) is the number of unlabeled binary trees with n internal nodes and exactly k distinguished external nodes (leaves) for 0 <= k <= n+1 and n >= 0.

1, 1, 1, 2, 1, 2, 6, 6, 2, 5, 20, 30, 20, 5, 14, 70, 140, 140, 70, 14, 42, 252, 630, 840, 630, 252, 42, 132, 924, 2772, 4620, 4620, 2772, 924, 132, 429, 3432, 12012, 24024, 30030, 24024, 12012, 3432, 429

Offset

0,4

Links

Table of n, a(n) for n=0..43.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 213.

Formula

O.g.f. for column k: 1/k!*(d/dy)^k y*B(y*x)|y=1 where B(x) is the o.g.f. for A000108.

From Vladimir Kruchinin, Oct 16 2020: (Start)

O.g.f.: (1-sqrt(-4*x*y-4*x+1))/(2*x).

T(n,m) = C(n+m,n)*C(2*n+1,n+m)/(2*n+1).

(End)

Example

Taylor series starts: (y + 1) + x*(y + 1)^2 + 2*x^2*(y + 1)^3 + 5*x^3*(y + 1)^4 + 14*x^4*(y + 1)^5 + ...
Triangle T(n, k) begins:
   1,   1;
   1,   2,   1;
   2,   6,   6,   2;
   5,  20,  30,  20,   5;
  14,  70, 140, 140,  70,  14;
  42, 252, 630, 840, 630, 252, 42;
  ...

Mathematica

nn = 5; b[z_] := (1 - Sqrt[1 - 4 z])/(2 z); Map[Select[#, # > 0 &] &, Transpose[Table[CoefficientList[Series[D[v b[v z], {v, k}]/k! /. v -> 1, {z, 0, nn}], z], {k, 0, nn + 1}]]] // Grid

Prog

(Maxima)
T(n, m):=(binomial(n+m, n)*binomial(2*n+1, n+m))/(2*n+1); /* Vladimir Kruchinin, Oct 16 2020 */
(PARI) for(n=1, 8, for(k=0, n, print1(binomial(n, k)*binomial(2*n-2, n-1)/n, ", ")); print()) \\ Hugo Pfoertner, Oct 16 2020

Crossrefs

Cf. A025225 (row sums), A000108 (column k=0), A000984 (column k=1), A002457 (column k=2).

Cf. A007318.

Sequence in context: A300639 A301361 A267864 * A219570 A285030 A281781

Adjacent sequences: A336521 A336522 A336523 * A336525 A336526 A336527

Keyword

nonn,tabf

Author

Geoffrey Critzer, Jul 24 2020

Status

approved