0,5

There are several versions of a Catalan triangle: see A009766, A008315, A028364, A033184, A053121, A059365, A062103.

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

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

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

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]

E. Barcucci and Verri, Discrete Math., 102 (1992), 229-237.

F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.

M. Bousquet-Melou and M. Petkovsek, Linear recurrences with constant coefficients: the multivariate case, Discrete Math., 225 (2000), 51-75.

E. H. M. Brietzke, An identity of Andrews ..., Discrete Math., 308 (2008), 4246-4262.

S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.

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

E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 1961, 199-201.

W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.

D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.6, Eq. 22.

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. Merlini et al., Underdiagonal lattice paths with unrestricted steps, Discrete Appl. Math., 91 (1999), 197-213.

D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344 (Table I).

L. W. Shapiro, A Catalan triangle, Discrete Math., 14, 83-90, 1976.

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]

Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906v1, Discrete Math., 308 (2008), 4660-4669.

Dominique Foata and Guo-Niu Han, Dimers and new q-tangent numbers, Preprint, 2008.

Dominique Foata and Guo-Niu Han, The dimer polynomial triangle, Preprint, 2008.

T. D. Noe, Rows n=0..100 of triangle, flattened

J. L. Arregui, Tangent and Bernoulli numbers related to Motzkin and Catalan numbers by means of numerical triangles.

M. Bousquet-M\'{e}lou, Linear recurrences with constant coefficients: the multivariate case

Ira Gessel, Super ballot numbers.

F. Hivert, J.-C. Novelli and J.-Y. Thibon, The Algebra of Binary Search Trees, Theoretical Computer Science, 339 (2005), 129-165.

A. Karttunen, Some notes on Catalan's Triangle

D. Merlini et al., Underdiagonal lattice paths with unrestricted steps, Discrete Appl. Math., 91 (1999), 197-213.

J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion

R. Parviainen, Permutations, cycles and the pattern 2-13

A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations.

T. Sillke, Catalan's numbers

R. A. Sulanke, Guessing, ballot numbers and refining Pascal's triangle

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Nonnegative Partial Sum

a(n, m)= binomial(n+m, n)*(n-m+1)/(n+1), n >= m >= 0.

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.

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

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

T(n,k) = C(n+k-2,n-1)*(n-k+1)/n [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

Triangle begins:

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,7,27,75,165,297,429,429

1,8,35,110,275,572,1001,1430,1430

1,9,44,154,429,1001,2002,3432,4862,4862

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

(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 */

Cf. A008315, A028364, A059365, A062103, A062745. Diagonals give A000108, A000245, A002057.

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

Row sums as well as the sums of the squares of the shallow diagonals give Catalan numbers (A000108).

Reflected version of A033184.

The following are all versions of (essentially) the same Catalan triangle: A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.

Diagonals give A000108 A000245 A002057 A000344 A003517 A000588 A003518 A003519 A001392, ...

Sequence in context: A139687 A064581 A064580 this_sequence A059718 A076038 A095788

Adjacent sequences: A009763 A009764 A009765 this_sequence A009767 A009768 A009769

nonn,tabl,nice

Wouter L. J. Meeussen (wouter.meeussen(AT)pandora.be).