login
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

%I #32 Nov 28 2018 05:37:46

%S 1,3,1,12,9,2,55,66,30,5,273,455,315,105,14,1428,3060,2856,1428,378,

%T 42,7752,20349,23940,15960,6300,1386,132,43263,134596,191268,159390,

%U 83490,27324,5148,429,246675,888030,1480050,1480050,965250,418275,117117

%N 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 Andrew Howroyd, <a href="/A089434/b089434.txt">Table of n, a(n) for n = 2..1276</a>

%H 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 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 T(n, k) = binomial(n+k-2, k)*binomial(3*n-3, n-2-k)/(n-1), 0 <= k <= n-2.

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

%F 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 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 Triangle starts:

%e 1;

%e 3, 1;

%e 12, 9, 2;

%e 55, 66, 30, 5;

%e ... - _Michel Marcus_, Apr 09 2013

%t 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 (* _Jean-François Alcover_, Jun 30 2011 *)

%o (PARI)

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

%o for(n=2, 10, for(k=0, n-2, print1(T(n, k), ", ")); print); \\ _Andrew Howroyd_, Nov 17 2017

%Y 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 Columns k=0..2 are A001764, A003408, A089433.

%Y Cf. A007297, A000108, A108410.

%K nonn,tabl

%O 2,2

%A _Emeric Deutsch_, Dec 28 2003

%E Keyword tabl added by _Michel Marcus_, Apr 09 2013

%E Offset corrected by _Andrew Howroyd_, Nov 17 2017