|
Search: id:A089435
|
|
|
| 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,.... |
|
+0
1
|
|
| 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; 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)sum(binomial(n+k+i-2, i)binomial(3n-3-k-i, 2n-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)zG^2-2(t-2)z^2G+(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).
|
|
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: A096773 A118384 A133176 this_sequence A152474 A088814 A088729
Adjacent sequences: A089432 A089433 A089434 this_sequence A089436 A089437 A089438
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 28 2003
|
|
|
Search completed in 0.002 seconds
|
