A127537 Triangle read by rows: T(n,k) (n >= 2, 1 <= k <= 2n-3) is the number of non-crossing connected graphs on n nodes on a circle, having k edges. Rows are indexed 2,3,4,...; columns are indexed 0,1,2,....

1, 0, 3, 1, 0, 0, 12, 9, 2, 0, 0, 0, 55, 66, 30, 5, 0, 0, 0, 0, 273, 455, 315, 105, 14, 0, 0, 0, 0, 0, 1428, 3060, 2856, 1428, 378, 42, 0, 0, 0, 0, 0, 0, 7752, 20349, 23940, 15960, 6300, 1386, 132, 0, 0, 0, 0, 0, 0, 0, 43263, 134596, 191268, 159390, 83490, 27324, 5148, 429

Offset

2,3

Comments

Row n contains 2n-3 terms, the first n-2 of which are equal to 0.

T(n,n-1) = A001764(n-1). T(n,2n-3) = A000108(n-2) (the Catalan numbers).

T(n,k) = A089434(n,k+1-n).

Sum_{k=n-1..2n-3} k*T(n,k) = A045741(n).

Sum_{n=k..2k-2} T(n,k) = A065065(k).

Links

Table of n, a(n) for n=2..65.

C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358.

C. Domb & A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358. (Annotated scanned copy)

C. Domb & A. J. Barrett, Notes on Table 2 in "Enumeration of ladder graphs", Discrete Math. 9 (1974), 55. (Annotated scanned copy)

P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.

Formula

T(n,k) = C(3n-3,n+k)C(k-1,k-n+1)/(n-1) (n >= 2, 0 <= k <= 2n-3).

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

Example

Triangle starts:
  1;
  0,  3,  1;
  0,  0, 12,  9,  2;
  0,  0,  0, 55, 66, 30,  5;

Maple

T:=(n, k)->binomial(3*n-3, n+k)*binomial(k-1, k-n+1)/(n-1): for n from 2 to 10 do seq(T(n, k), k=1..2*n-3) od; # yields sequence in triangular form

Mathematica

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

Crossrefs

Cf. A000108, A001764, A045741, A065065, A089434.

Sequence in context: A144402 A264429 A324163 * A265314 A364207 A307791

Adjacent sequences: A127534 A127535 A127536 * A127538 A127539 A127540

Keyword

nonn,tabf

Author

Emeric Deutsch, Jan 24 2007

Extensions

Keyword tabl changed to tabf by Michel Marcus, Apr 09 2013

Status

approved