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

Author

Emeric Deutsch, Jan 24 2007

Keywords

• nonn
• tabf

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).

Examples

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

Links

• 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.

Crossrefs

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

Programs

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 *)

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.

Extensions

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