cp's OEIS Frontend

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,....

%I A089434 #32 Nov 28 2018 05:37:46
%S A089434 1,3,1,12,9,2,55,66,30,5,273,455,315,105,14,1428,3060,2856,1428,378,
%T A089434 42,7752,20349,23940,15960,6300,1386,132,43263,134596,191268,159390,
%U A089434 83490,27324,5148,429,246675,888030,1480050,1480050,965250,418275,117117
%N 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,....
%H A089434 Andrew Howroyd, <a href="/A089434/b089434.txt">Table of n, a(n) for n = 2..1276</a>
%H A089434 P. Flajolet and M. Noy, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00372-0">Analytic combinatorics of non-crossing configurations</a>, Discrete Math., 204, 203-229, 1999.
%H A089434 V. Pilaud, J. Rue, <a href="https://doi.org/10.1016/j.aam.2014.04.001">Analytic combinatorics of chord and hyperchord diagrams with k crossings</a>, Adv. Appl. Math. 57 (2014) 60-100, equation (3).
%F A089434 T(n, k) = binomial(n+k-2, k)*binomial(3*n-3, n-2-k)/(n-1), 0 <= k <= n-2.
%F A089434 G.f.: G(t, z) satisfies G^3 + t*G^2 - (1+2*t)*z*G+(1+t)*z^2 = 0.
%F A089434 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
%e A089434 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).
%e A089434 Triangle starts:
%e A089434    1;
%e A089434    3,  1;
%e A089434   12,  9,  2;
%e A089434   55, 66, 30, 5;
%e A089434   ... - _Michel Marcus_, Apr 09 2013
%t A089434 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]]
%t A089434 (* _Jean-François Alcover_, Jun 30 2011 *)
%o A089434 (PARI)
%o A089434 T(n, k)={binomial(n+k-2, k)*binomial(3*n-3, n-2-k)/(n-1)}
%o A089434 for(n=2, 10, for(k=0, n-2, print1(T(n, k), ", ")); print); \\ _Andrew Howroyd_, Nov 17 2017
%Y A089434 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.
%Y A089434 Columns k=0..2 are A001764, A003408, A089433.
%Y A089434 Cf. A007297, A000108, A108410.
%K A089434 nonn,tabl
%O A089434 2,2
%A A089434 _Emeric Deutsch_, Dec 28 2003
%E A089434 Keyword tabl added by _Michel Marcus_, Apr 09 2013
%E A089434 Offset corrected by _Andrew Howroyd_, Nov 17 2017