login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; table; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 8 20:14 EST 2021. Contains 341953 sequences. (Running on oeis4.)