|
| |
|
|
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
|
|
|
|
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;
|
|
|
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]]
|
|
|
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.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
