login
Triangle read by rows: T(n,k) = Catalan(k)*Catalan(n-k).
2

%I #68 Aug 26 2024 12:12:40

%S 1,1,1,2,1,2,5,2,2,5,14,5,4,5,14,42,14,10,10,14,42,132,42,28,25,28,42,

%T 132,429,132,84,70,70,84,132,429,1430,429,264,210,196,210,264,429,

%U 1430,4862,1430,858,660,588,588,660,858,1430,4862,16796,4862,2860,2145,1848

%N Triangle read by rows: T(n,k) = Catalan(k)*Catalan(n-k).

%C T(n,k) is the number of Dyck paths of semilength n+1 whose first return point to the axis have abscissa 2k+2. - _Emeric Deutsch_, Mar 01 2004

%C With offset = 1, T(n,k) is the number of binary trees with n internal nodes that have exactly k internal nodes in the left subtree, n>=1, 0<=k<=n-1. - _Geoffrey Critzer_, Feb 24 2013

%C T(n-1,k) is also the number of tilings of a triangular shape T_n (row k has length k for k=1, 2, ..., n) with n rectangular tiles (including squares) with contain a rectangular tile (n-k,k+1) for k = 0, 1, ... ,n-1, n >= 1. Let the number of tilings of T_n with n rectangular tiles (including squares) be A(n) and take A(0) = 1. Decompose these n-tilings of T_n into n disjoint and exhaustive classes C(n, k), for k = 0, 1, ..., n-1, n >= 1. In class C(n, k) one takes a fixed rectangular tile (n-k,k+1) leaving triangles T_(n-1-k) and T_k to be tiled (but for the k=0 class T_0 is not shown). Then A(n) = A(n-1)*A(0) + A(n-2)*A(1) + ... + A(0)*A(n-1) = sum(A(n-1-k)*A(k), k=0..n-1), n >= 1, with A(0)=1. But this is the recurrence for the Catalan numbers, hence A(n) = C(n). See the link with examples n = 1..7. - _Wolfdieter Lang_ and _Kival Ngaokrajang_, Dec 27 2014

%C T(n,k) is the number of triangulations of an (n+3)-polygon using a (0,1,k+2)-triangle. - _Yuchun Ji_, Jan 21 2021

%C Alternating sum of even index 2n is A079489(n). - _F. Chapoton_, Aug 26 2024

%D R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, first edition, page 225.

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000026">The position of the first return of a Dyck path.</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000051">The size of the left subtree.</a>

%H Kival Ngaokrajang, <a href="/A078391/a078391_4.pdf">Illustration of C(n,k), for n = 1..7, k = 0..n-1</a>

%H Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/ec/catadd.pdf"> Catalan Addendum (k8)</a>

%F G.f.: C(z)*C(tz), where C(z) = (1-sqrt(1-4z))/(2z) is the g.f. of the Catalan numbers (A000108). - _Emeric Deutsch_, Mar 01 2004

%F T(n,k) = A118921(n+1,k+1)/(2*(n-k+1)). - _Philippe Deléham_, Dec 13 2006

%F When viewed as a square array, for n>0 and k>0, A(n,k) = Sum_{i=0..n-1,j=0..k-1} A[i,j]*A[n-i,k-j]. - _Gerald McGarvey_, Dec 30 2007

%e The triangle T(n,k) begins:

%e n\k 0 1 2 3 4 5 6 7 8 9 10 ...

%e 0: 1

%e 1: 1 1

%e 2: 2 1 2

%e 3: 5 2 2 5

%e 4: 14 5 4 5 14

%e 5: 42 14 10 10 14 42

%e 6: 132 42 28 25 28 42 132

%e 7: 429 132 84 70 70 84 132 429

%e 8: 1430 429 264 210 196 210 264 429 1430

%e 9: 4862 1430 858 660 588 588 660 858 1430 4862

%e 10: 16796 4862 2860 2145 1848 1764 1848 2145 2860 4862 16796

%e ... Reformatted - _Wolfdieter Lang_, Dec 27 2014

%e ----------------------------------------------------------------

%t nn=10;r=(1-(1-4x)^(1/2))/(2x);l=(1-(1-4x y)^(1/2))/(2x y);f[list_]:=Select[list,#>0&];Map[f,Drop[CoefficientList[Series[1+x l r,{x,0,nn}],{x,y}],1]]//Grid (* _Geoffrey Critzer_, Feb 24 2013 *)

%t Table[CatalanNumber[k]CatalanNumber[n-k],{n,0,10},{k,0,n}]//Flatten (* _Harvey P. Dale_, Nov 14 2019 *)

%Y Row sums are Catalan numbers A000108(n+1). T(2*k,k) = A001246(k), k >= 0. T(n,0) = T(n,n) = A000108(n).

%Y Cf. A067804, A079489.

%K nonn,tabl

%O 0,4

%A _Henry Bottomley_, Dec 24 2002