login
Triangle read by rows: T(n,k) is the number of dissections of a convex n-gon by nonintersecting diagonals, having exactly k triangles (n >= 2, k >= 0).
0

%I #16 Nov 14 2019 09:13:49

%S 1,0,1,1,0,2,1,5,0,5,4,6,21,0,14,8,35,28,84,0,42,25,80,216,120,330,0,

%T 132,64,309,540,1155,495,1287,0,429,191,890,2475,3080,5720,2002,5005,

%U 0,1430,540,3058,7788,16302,16016,27027,8008,19448,0,4862,1616,9580,30108,54964,96005,78624,123760,31824,75582,0,16796

%N Triangle read by rows: T(n,k) is the number of dissections of a convex n-gon by nonintersecting diagonals, having exactly k triangles (n >= 2, k >= 0).

%C T(n,n-2) = [binomial(2n-4, n-2)]/(n-1) = Catalan(n-2) (A000108).

%C T(n,n-4) = binomial(2n-5, n-4) (A002054).

%C T(n,n-5) = binomial(2n-6, n-5) (A002694).

%C T(n,0) = A046736(n).

%C Row sums give the little Schroeder numbers (A001003).

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

%F T(n, k) = binomial(n+k-2, k)*(Sum_{i=0..floor((n-2-k)/2)} binomial(n-2+k+i, i)*binomial(n-3-k-i, i-1))/(n-1).

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

%e T(5,1)=5 because the dissections of a convex pentagon having exactly one triangle are obtained by the placement of a diagonal between any pair of non-adjacent vertices.

%e T(6,0)=4 because the dissections of a convex hexagon with no triangles are obtained by the null placement and by placing one diagonal between any of the 3 pairs of opposite vertices.

%e Triangle starts:

%e 1;

%e 0, 1;

%e 1, 0, 2;

%e 1, 5, 0, 5;

%e 4, 6, 21, 0, 14;

%e 8, 35, 28, 84, 0, 42;

%e ...

%p T := (n,k)->binomial(n+k-2,k)*sum(binomial(n-2+k+i,i)*binomial(n-3-k-i,i-1), i=0..floor((n-2-k)/2))/(n-1): seq(seq(T(n,k),k=0..n-2),n=2..14);

%t T [n_, k_] := Binomial[n+k-2, k] Sum[Binomial[n-2+k+i, i] Binomial[n-3-k-i, i-1], {i, 0, (n-2-k)/2}]/(n-1);

%t Table[T[n, k], {n, 2, 12}, {k, 0, n-2}] // Flatten (* _Jean-François Alcover_, Jul 29 2018 *)

%Y Cf. A000108, A002054, A002694, A046736.

%K nonn,tabl

%O 2,6

%A _Emeric Deutsch_, Feb 28 2004