login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089434 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 interior faces. Rows are indexed 2,3,4,...; columns are indexed 0,1,2,.... 8
1, 3, 1, 12, 9, 2, 55, 66, 30, 5, 273, 455, 315, 105, 14, 1428, 3060, 2856, 1428, 378, 42, 7752, 20349, 23940, 15960, 6300, 1386, 132, 43263, 134596, 191268, 159390, 83490, 27324, 5148, 429, 246675, 888030, 1480050, 1480050, 965250, 418275, 117117 (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.

V. Pilaud, J. Rue, Analytic combinatorics of chord and hyperchord diagrams with k crossings, Adv. Appl. Math. 57 (2014) 60-100, equation (3).

FORMULA

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

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

O.g.f. equals the series reversion w.r.t. x of x*(1-x*t)/(1+x)^3. If R(n,t) is the n-th row polynomial of this triangle then R(n,t-1) is the n-th row polynomial of A108410. - Peter Bala, Jul 15 2012

EXAMPLE

T(4,1)=9 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 interior face, by deleting either both diagonals AC and BD (1 case) or deleting one of the two diagonals and one of the four sides (8 cases).

Triangle starts:

   1;

   3,  1;

  12,  9,  2;

  55, 66, 30, 5;

  ... - Michel Marcus, Apr 09 2013

MATHEMATICA

t[n_, k_] = Binomial[n + k - 2, k] Binomial[3 n - 3, n - 2 - k]/(n - 1) ; Flatten[Table[t[n, k], {n, 2, 10}, {k, 0, n - 2}]][[;; 43]]

(* Jean-Fran├žois Alcover, Jun 30 2011 *)

PROG

(PARI)

T(n, k)={binomial(n+k-2, k)*binomial(3*n-3, n-2-k)/(n-1)}

for(n=2, 10, for(k=0, n-2, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 17 2017

CROSSREFS

T(n, n-2) yields the Catalan numbers (A000108) corresponding to triangulations, T(n, 0) yields the ternary numbers (A001764) corresponding to noncrossing trees, T(n, 1) yields A003408, row sums yield A007297. Sum(kT(n, k), k=0..n-2) yields A045742.

Columns k=0..2 are A001764, A003408, A089433.

Cf. A007297, A000108, A108410.

Sequence in context: A039811 A046089 A113360 * A268298 A291418 A219512

Adjacent sequences:  A089431 A089432 A089433 * A089435 A089436 A089437

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Dec 28 2003

EXTENSIONS

Keyword tabl added by Michel Marcus, Apr 09 2013

Offset corrected by Andrew Howroyd, Nov 17 2017

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 24 06:56 EDT 2019. Contains 321444 sequences. (Running on oeis4.)