A094021 Triangle read by rows: T(n,k) is the number of noncrossing forests with n vertices and k components (1<=k<=n).

1, 1, 1, 3, 3, 1, 12, 14, 6, 1, 55, 75, 40, 10, 1, 273, 429, 275, 90, 15, 1, 1428, 2548, 1911, 770, 175, 21, 1, 7752, 15504, 13328, 6370, 1820, 308, 28, 1, 43263, 95931, 93024, 51408, 17640, 3822, 504, 36, 1, 246675, 600875, 648945, 406980, 162792, 42840

Offset

1,4

Links

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

P. Flajolet and M. Noy, Analytic combinatorics of noncrossing configurations, Discrete Math. 204 (1999), 203-229.

Formula

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

G.f.: G=G(t, z) satisfies G^3+(t^3*z^2-t^2*z-3)G^2+(t^2*z+3)G-1=0.

From Peter Bala, Nov 07 2015: (Start)

O.g.f. A(x,t) = revert( x/((1 + x*t)*C(x)) ) with respect to x, where C(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f for the Catalan numbers A000108.

Row sums are A054727. (End)

Example

From Andrew Howroyd, Nov 17 2017: (Start)
Triangle begins:
     1;
     1,     1;
     3,     3,     1;
    12,    14,     6,    1;
    55,    75,    40,   10,    1;
   273,   429,   275,   90,   15,   1;
  1428,  2548,  1911,  770,  175,  21,  1;
  7752, 15504, 13328, 6370, 1820, 308, 28, 1;
(End)
T(3,2)=3 because, with A,B,C denoting the vertices of a triangle, we have the 2-component forests (A,BC), (B,CA) and (C,AB).

Maple

T:=proc(n, k) if k<=n then binomial(n, k-1)*binomial(3*n-2*k-1, n-k)/(2*n-k) else 0 fi end: seq(seq(T(n, k), k=1..n), n=1..11);

Mathematica

T[n_, k_] := If[k <= n, Binomial[n, k-1]*Binomial[3n-2k-1, n-k]/(2n-k), 0];
Table[T[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 06 2018 *)

Prog

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

Crossrefs

Columns k=1..2 are A001764, A026004.

Row sums are A054727.

Cf. A000108.

Sequence in context: A120870 A010029 A143603 * A062746 A115193 A227343

Adjacent sequences: A094018 A094019 A094020 * A094022 A094023 A094024

Keyword

nonn,tabl,easy

Author

Emeric Deutsch, May 31 2004

Status

approved