%I A009766
%S A009766 1,1,1,1,2,2,1,3,5,5,1,4,9,14,14,1,5,14,28,42,42,1,6,20,48,90,132,132,
               1,
%T A009766 7,27,75,165,297,429,429,1,8,35,110,275,572,1001,1430,1430,1,9,44,154,
%U A009766 429,1001,2002,3432,4862,4862,1,10,54,208,637,1638,3640,7072,11934
%N A009766 Catalan's triangle T(n,k) (read by rows): each term is the sum of the 
               entries above and to the left, i.e. T(n,k)=sum(T(n-1,j),j=0..k).
%C A009766 There are several versions of a Catalan triangle: see A009766, A008315, 
               A028364, A033184, A053121, A059365, A062103.
%C A009766 T(n,k) = number of standard tableaux of shape (n,k) (n>0, 0< = k< = n). 
               Example: T(3,1) = 3 because we have 134/2, 124/3 and 123/4. - Emeric 
               Deutsch (deutsch(AT)duke.poly.edu), May 18 2004
%C A009766 T(n,k) is the number of full binary trees with n+1 internal nodes and 
               jump-length k. In the preorder traversal of a full binary tree, any 
               transition from a node at a deeper level to a node on a strictly 
               higher level is called a jump; the positive difference of the levels 
               is called the jump distance; the sum of the jump distances in a given 
               ordered tree is called the jump-length. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               Jan 18 2007
%C A009766 Comment from Anthony C Robin, Jul 12 2007: The k-th diagonal from the 
               right (k=1, 2, ...) gives the sequence obtained by asking in how 
               many ways can we toss a fair coin until we first get k more heads 
               than tails. The k-th diagonal has formula k(2m+k-1)!/(m!(m+k)!) and 
               g.f. (C(x))^k where C(x) is the generating function for the Catalan 
               numbers, (1-sq_root(1-4x))/(2x).
%C A009766 T(n,k) is also the number of order-decreasing and order-preserving full 
               transformations (of an n-element chain) of waist k (waist (alpha) 
               = max(Im(alpha))). [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]
%D A009766 E. Barcucci and Verri, Discrete Math., 102 (1992), 229-237.
%D A009766 F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 
               (1999) 73-112.
%D A009766 M. Bousquet-Melou and M. Petkovsek, Linear recurrences with constant 
               coefficients: the multivariate case, Discrete Math., 225 (2000), 
               51-75.
%D A009766 E. H. M. Brietzke, An identity of Andrews ..., Discrete Math., 308 (2008), 
               4246-4262.
%D A009766 S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem 
               for succession rules, Discr. Math., 298 (2005), 142-154.
%D A009766 B. Derrida, E. Domany and D. Mukamel, An exact solution of a one-dimensional 
               asymmetric exclusion model with open boundaries, J. Stat. Phys. 69, 
               1992, 667-687; eqs. (20), (21), p. 672. (Y_{N}(K) = A009766(N+1,K-1), 
               1 <= K <= N+1, N >=0 if alpha = 1 = beta).
%D A009766 E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 
               241 (2001), 241-265.
%D A009766 H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 
               1961, 199-201.
%D A009766 W. Krandick, Trees and jumps and real roots, J. Computational and Applied 
               Math., 162, 2004, 51-55.
%D A009766 D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.6, Eq. 22.
%D A009766 G. Kreweras, Sur les e'ventails de segments, {\em Cahiers du Bureau Universitaire 
               de Recherche Op\'{e}rationnelle}, Institut de Statistique, Universit\'{e} 
               de Paris, #15 (1970), 3-41.
%D A009766 D. Merlini et al., Underdiagonal lattice paths with unrestricted steps, 
               Discrete Appl. Math., 91 (1999), 197-213.
%D A009766 D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. 
               Combin. Theory, A 99 (2002), 307-344 (Table I).
%D A009766 L. W. Shapiro, A Catalan triangle, Discrete Math., 14, 83-90, 1976.
%D A009766 Laradji, A. and Umar, A. On certain finite semigroups of order-decreasing 
               transformations I, Semigroup Forum 69 (2004), 184-200 [From A. Umar 
               (aumarh(AT)squ.edu.om), Aug 25 2008]
%D A009766 Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906v1, 
               Discrete Math., 308 (2008), 4660-4669.
%D A009766 Dominique Foata and Guo-Niu Han, Dimers and new q-tangent numbers, Preprint, 
               2008.
%D A009766 Dominique Foata and Guo-Niu Han, The dimer polynomial triangle, Preprint, 
               2008.
%H A009766 T. D. Noe, <a href="b009766.txt">Rows n=0..100 of triangle, flattened</
               a>
%H A009766 J. L. Arregui, <a href="http://arXiv.org/abs/math.NT/0109108">Tangent 
               and Bernoulli numbers</a> related to Motzkin and Catalan numbers 
               by means of numerical triangles.
%H A009766 M. Bousquet-M\'{e}lou, <a href="http://www.labri.fr/Perso/~bousquet/Articles/
               Linrec/linrec.ps.gz">Linear recurrences with constant coefficients: 
               the multivariate case</a>
%H A009766 Ira Gessel, <a href="http://www.cs.brandeis.edu/~ira/">Super ballot numbers</
               a>.
%H A009766 F. Hivert, J.-C. Novelli and J.-Y. Thibon, <a href="http://arXiv.org/
               abs/math.CO/0401089">The Algebra of Binary Search Trees</a>, Theoretical 
               Computer Science, 339 (2005), 129-165.
%H A009766 A. Karttunen, <a href="http://www.iki.fi/~kartturi/matikka/tab9766.htm">
               Some notes on Catalan's Triangle</a>
%H A009766 D. Merlini et al., <a href="http://www.dsi.unifi.it/~merlini/under.ps">
               Underdiagonal lattice paths with unrestricted steps</a>, Discrete 
               Appl. Math., 91 (1999), 197-213.
%H A009766 J.-C. Novelli and J.-Y. Thibon, <a href="http://arXiv.org/abs/math.CO/
               0512570">Noncommutative Symmetric Functions and Lagrange Inversion</
               a>
%H A009766 R. Parviainen, <a href="http://arXiv.org/abs/math.CO/0607793">Permutations, 
               cycles and the pattern 2-13</a>
%H A009766 A. Robertson, D. Saracino and D. Zeilberger, <a href="http://arXiv.org/
               abs/math.CO/0203033">Refined restricted permutations</a>.
%H A009766 T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/
               series004">Catalan's numbers</a>
%H A009766 R. A. Sulanke, <a href="http://math.boisestate.edu/~sulanke/recentpapindex.html">
               Guessing, ballot numbers and refining Pascal's triangle</a>
%H A009766 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               CatalansTriangle.html">Link to a section of The World of Mathematics.</
               a>
%H A009766 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               NonnegativePartialSum.html">Nonnegative Partial Sum</a>
%F A009766 a(n, m)= binomial(n+m, n)*(n-m+1)/(n+1), n >= m >= 0.
%F A009766 G.f. for column m: (x^m)*N(2; m-1, x)/(1-x)^(m+1), m >= 0, with the row 
               polynomials from triangle A062991 and N(2; -1, x) := 1.
%F A009766 G.f.=C(tx)/[1-xC(tx)]=1+(1+t)x+(1+2t+2t^2)x^2+..., where C(x)=[1-sqrt(1-4x)]/
               (2x) is the Catalan function. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               May 18 2004
%F A009766 Another version of triangle T(n, k) given by [1, 0, 0, 0, 0, 0, ...] 
               DELTA [0, 1, 1, 1, 1, 1, 1, ...] = 1; 1, 0; 1, 1, 0; 1, 2, 2, 0; 
               1, 3, 5, 5, 0; 1, 4, 9, 14, 14, 0; ...where DELTA is the operator 
               defined in A084938. - Philippe Deleham (kolotoko(AT)wanadoo.fr) Feb 
               16 2005
%F A009766 T(n,k) = C(n+k-2,n-1)*(n-k+1)/n [From A. Umar (aumarh(AT)squ.edu.om), 
               Aug 25 2008]
%e A009766 Triangle begins:
%e A009766 1
%e A009766 1,1
%e A009766 1,2,2
%e A009766 1,3,5,5
%e A009766 1,4,9,14,14
%e A009766 1,5,14,28,42,42
%e A009766 1,6,20,48,90,132,132
%e A009766 1,7,27,75,165,297,429,429
%e A009766 1,8,35,110,275,572,1001,1430,1430
%e A009766 1,9,44,154,429,1001,2002,3432,4862,4862
%p A009766 for n from 1 to 12 do seq((n-m)/(m+n)* binomial(m+n,m), m = 0 .. n-1) 
               od; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 09 2007
%o A009766 (PARI) {T(n, k)= if(k<0|k>n, 0, binomial(n+1+k, k)* (n+1-k)/(n+1+k) )} 
               /* Michael Somos Oct 17 2006 */
%Y A009766 Cf. A008315, A028364, A059365, A062103, A062745. Diagonals give A000108, 
               A000245, A002057.
%Y A009766 Sums of the shallow diagonals give A001405, central binomial coefficients: 
               1=1, 1=1, 1+1=2, 1+2=3, 1+3+2=6, 1+4+5=10, 1+5+9+5=20, ...
%Y A009766 Row sums as well as the sums of the squares of the shallow diagonals 
               give Catalan numbers (A000108).
%Y A009766 Reflected version of A033184.
%Y A009766 The following are all versions of (essentially) the same Catalan triangle: 
               A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
%Y A009766 Diagonals give A000108 A000245 A002057 A000344 A003517 A000588 A003518 
               A003519 A001392, ...
%Y A009766 Sequence in context: A139687 A064581 A064580 this_sequence A059718 A076038 
               A095788
%Y A009766 Adjacent sequences: A009763 A009764 A009765 this_sequence A009767 A009768 
               A009769
%K A009766 nonn,tabl,nice
%O A009766 0,5
%A A009766 Wouter L. J. Meeussen (wouter.meeussen(AT)pandora.be).