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!)
A089435 Triangle read by rows: T(n,k) (n >= 2, k >= 0) is the number of non-crossing connected graphs on n nodes on a circle, having k triangles. Rows are indexed 2,3,4,...; columns are indexed 0,1,2,.... 2
1, 3, 1, 13, 8, 2, 66, 60, 25, 5, 367, 442, 255, 84, 14, 2164, 3248, 2380, 1064, 294, 42, 13293, 23904, 21192, 11832, 4410, 1056, 132, 84157, 176397, 183303, 122115, 56430, 18216, 3861, 429, 545270, 1305480, 1554850, 1200320, 657195, 262262, 75075 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,2

LINKS

Andrew Howroyd, Table of n, a(n) for n = 2..1276

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

FORMULA

T(n, k) = binomial(n+k-2, k)*sum(binomial(n+k+i-2, i)*binomial(3*n-3-k-i, 2*n-1+i), i=0..floor((n-k-2)/2))/(n-1), n>=2, k>=0.

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

EXAMPLE

T(4,1)=8 because, considering the complete graph K_4 on the nodes A,B,C and D, we obtain a non-crossing connected graph on A,B,C,D, with exactly one triangle, by deleting one of the two diagonals and one of the four sides (8 possibilities).

Triangle starts:

    1;

    3,   1;

   13,   8,   2;

   66,  60,  25,   5;

  367, 442, 255,  84,  14;

  ...

MATHEMATICA

t[n_, k_] = Binomial[n+k-2, k]*Sum[Binomial[n+k+i-2, i]*Binomial[3n-3-k-i, 2n-1+i], {i, 0, Floor[(n-k-2)/2]}]/(n-1) ;

Flatten[Table[t[n, k], {n, 2, 10}, {k, 0, n-2}]][[1 ;; 43]] (* Jean-Fran├žois Alcover, Jun 20 2011 *)

PROG

(PARI) T(n, k) = binomial(n+k-2, k)*sum(i=0, floor((n-k-2)/2), binomial(n+k+i-2, i)*binomial(3*n-3-k-i, 2*n-1+i))/(n-1); \\ Michel Marcus, Oct 26 2015

CROSSREFS

T(n, n-2) yields the Catalan numbers (A000108) corresponding to triangulations, T(n, 0) yields A045743, row sums yield A007297.

Cf. A007297, A000108, A045743.

Sequence in context: A341725 A258239 A133176 * A152474 A088814 A088729

Adjacent sequences:  A089432 A089433 A089434 * A089436 A089437 A089438

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Dec 28 2003

EXTENSIONS

Keyword tabl added by Michel Marcus, Apr 09 2013

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 July 28 05:19 EDT 2021. Contains 346317 sequences. (Running on oeis4.)