cp's OEIS Frontend

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

%I A094021 #15 Jul 06 2018 03:02:31
%S A094021 1,1,1,3,3,1,12,14,6,1,55,75,40,10,1,273,429,275,90,15,1,1428,2548,
%T A094021 1911,770,175,21,1,7752,15504,13328,6370,1820,308,28,1,43263,95931,
%U A094021 93024,51408,17640,3822,504,36,1,246675,600875,648945,406980,162792,42840
%N A094021 Triangle read by rows: T(n,k) is the number of noncrossing forests with n vertices and k components (1<=k<=n).
%H A094021 Andrew Howroyd, <a href="/A094021/b094021.txt">Table of n, a(n) for n = 1..1275</a>
%H A094021 P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of noncrossing configurations</a>, Discrete Math. 204 (1999), 203-229.
%F A094021 T(n, k) = binomial(n, k-1)*binomial(3n-2k-1, n-k)/(2n-k).
%F A094021 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.
%F A094021 From _Peter Bala_, Nov 07 2015: (Start)
%F A094021 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.
%F A094021 Row sums are A054727. (End)
%e A094021 From _Andrew Howroyd_, Nov 17 2017: (Start)
%e A094021 Triangle begins:
%e A094021      1;
%e A094021      1,     1;
%e A094021      3,     3,     1;
%e A094021     12,    14,     6,    1;
%e A094021     55,    75,    40,   10,    1;
%e A094021    273,   429,   275,   90,   15,   1;
%e A094021   1428,  2548,  1911,  770,  175,  21,  1;
%e A094021   7752, 15504, 13328, 6370, 1820, 308, 28, 1;
%e A094021 (End)
%e A094021 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).
%p A094021 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);
%t A094021 T[n_, k_] := If[k <= n, Binomial[n, k-1]*Binomial[3n-2k-1, n-k]/(2n-k), 0];
%t A094021 Table[T[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jul 06 2018 *)
%o A094021 (PARI)
%o A094021 T(n,k)=binomial(n, k-1)*binomial(3*n-2*k-1, n-k)/(2*n-k);
%o A094021 for(n=1, 10, for(k=1, n, print1(T(n, k), ", ")); print); \\ _Andrew Howroyd_, Nov 17 2017
%Y A094021 Columns k=1..2 are A001764, A026004.
%Y A094021 Row sums are A054727.
%Y A094021 Cf. A000108.
%K A094021 nonn,tabl,easy
%O A094021 1,4
%A A094021 _Emeric Deutsch_, May 31 2004