login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A078391 Triangle read by rows: T(n,k) = Catalan(k)*Catalan(n-k). 2
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, 132, 429, 132, 84, 70, 70, 84, 132, 429, 1430, 429, 264, 210, 196, 210, 264, 429, 1430, 4862, 1430, 858, 660, 588, 588, 660, 858, 1430, 4862, 16796, 4862, 2860, 2145, 1848 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

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

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

REFERENCES

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

LINKS

Table of n, a(n) for n=0..59.

FindStat - Combinatorial Statistic Finder, The position of the first return of a Dyck path., The size of the left subtree.

Kival Ngaokrajang, Illustration of C(n,k), for n = 1..7, k = 0..n-1

Richard P. Stanley, Catalan Addendum (k8)

FORMULA

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

T(n,k) = A118921(n+1,k+1)/(2*(n-k+1)). - Philippe Deléham, Dec 13 2006

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

EXAMPLE

The triangle T(n,k) begins:

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

0:      1

1:      1    1

2:      2    1    2

3:      5    2    2    5

4:     14    5    4    5   14

5:     42   14   10   10   14   42

6:    132   42   28   25   28   42  132

7:    429  132   84   70   70   84  132  429

8:   1430  429  264  210  196  210  264  429 1430

9:   4862 1430  858  660  588  588  660  858 1430 4862

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

...  Reformatted - Wolfdieter Lang, Dec 27 2014

----------------------------------------------------------------

MATHEMATICA

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 *)

CROSSREFS

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

Cf. A067804.

Sequence in context: A057031 A230219 A147292 * A153206 A144155 A109631

Adjacent sequences:  A078388 A078389 A078390 * A078392 A078393 A078394

KEYWORD

nonn,tabl

AUTHOR

Henry Bottomley, Dec 24 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 24 00:59 EDT 2017. Contains 285338 sequences.