|
Search: id:A089434
|
|
|
| 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,.... |
|
+0
2
|
|
| 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; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
REFERENCES
|
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math. 204 (1999), 203-229.
|
|
FORMULA
|
T(n, k)=binomial(n+k-2, k)binomial(3n-3, n-2-k)/(n-1), 0 <= k <= n-2. G.f. G(t, z) satisfies G^3+tG^2-(1+2t)zG+(1+t)z^2 = 0.
|
|
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).
|
|
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.
Cf. A007297, A000108, A001764, A003408.
Sequence in context: A039811 A046089 A113360 this_sequence A019232 A016479 A134768
Adjacent sequences: A089431 A089432 A089433 this_sequence A089435 A089436 A089437
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 28 2003
|
|
|
Search completed in 0.002 seconds
|
