A101401 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges in which the leftmost child of the root has degree k.

1, 1, 2, 3, 6, 3, 12, 24, 15, 4, 55, 110, 75, 28, 5, 273, 546, 390, 168, 45, 6, 1428, 2856, 2100, 980, 315, 66, 7, 7752, 15504, 11628, 5712, 2040, 528, 91, 8, 43263, 86526, 65835, 33516, 12825, 3762, 819, 120, 9, 246675, 493350, 379500, 198352, 79695, 25410, 6370, 1200, 153, 10

Offset

1,3

Comments

Row n contains n terms. Column k=0 and row sums yield the ternary numbers (A001764).

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Formula

T(n, k) = ((k+1)(2k+1)/(3n-k-2)) binomial(3n-k-2, 2n-1).

G.f.: zg/(1-tzg^2)^2, where g = 1+zg^3 is the g.f. of the ternary numbers (A001764).

Example

T(2,0)=1 and T(2,1)=2 because the noncrossing trees with 2 edges are /\, |_ and _|.
Triangle starts:
    1;
    1,   2;
    3,   6,   3;
   12,  24,  15,  4;
   55, 110,  75,  28,  5;
  273, 546, 390, 168, 45, 6;
  ...

Maple

T:=proc(n, k) if n=1 and k=1 then 0 elif k<=n then (k+1)*(2*k+1)*binomial(3*n-k-2, 2*n-1)/(3*n-k-2) else 0 fi end: for n from 1 to 10 do seq(T(n, k), k=0..n-1) od; # yields sequence in triangular form

Mathematica

T[n_, k_] := ((k + 1)(2k + 1)/(3n - k - 2)) Binomial[3n - k - 2, 2n - 1];
Table[T[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, Apr 10 2020 *)

Prog

(PARI)
T(n, k) = if(k<n, (k+1)*(2*k+1)*binomial(3*n-k-2, 2*n-1)/(3*n-k-2));
for(n=1, 10, for(k=0, n-1, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 06 2017

Crossrefs

Cf. A001764.

Column k=1 is A046646.

Sequence in context: A350728 A109536 A267352 * A106834 A191658 A021427

Adjacent sequences: A101398 A101399 A101400 * A101402 A101403 A101404

Keyword

nonn,tabl

Author

Emeric Deutsch, Jan 15 2005

Status

approved