login
A094021
Triangle read by rows: T(n,k) is the number of noncrossing forests with n vertices and k components (1<=k<=n).
3
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
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
KEYWORD
nonn,tabl,easy
AUTHOR
Emeric Deutsch, May 31 2004
STATUS
approved