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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 92
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, 1, 10, 54, 208, 637, 1638, 3640, 7072, 11934 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

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

The entries in this triangle (in its many forms) are often called ballot numbers.

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, 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, Jan 18 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-sqrt(1-4*x))/(2*x). - Anthony C Robin, Jul 12 2007

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))). - Abdullahi Umar, Aug 25 2008

Formatted as an upper right triangle (see tables) a(c,r) is the number of different triangulated planar polygons with c+2 vertices, with triangle degree c-r+1 for the same vertex X (c=column number, r=row number, with c>=r>=1). - Patrick Labarque, Jul 28 2010

The triangle sums, see A180662 for their definitions, link Catalan's triangle, its mirror is A033184, with several sequences, see the crossrefs. - Johannes W. Meijer, Sep 22 2010

The m-th row of Catalan's triangle consists of the unique non-negative differences of the form binomial(m+k,m)-binomial(m+k,m+1) with 0<=k<=m (See Links). - R. J. Cano, Jul 22 2014

REFERENCES

Bacher, Axel; Bernini, Antonio; Ferrari, Luca; Gunby, Benjamin; Pinzani, Renzo; West, Julian. The Dyck pattern poset. Discrete Math. 321 (2014), 12--23. MR3154009.

Barcucci, Elena; Del Lungo, Alberto; Pergola, Elisa; Pinzani, Renzo. A methodology for plane tree enumeration. Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995). Discrete Math. 180 (1998), no. 1-3, 45--64. MR1603693 (98m:05090)

Italo J. Dejter, A numeral system for the middle levels, Preprint 2014; http://home.coqui.net/dejterij/anumeral.pdf. [See Section 2. - N. J. A. Sloane, Apr 06 2014]

Eplett, W. J. R. A note about the Catalan triangle. Discrete Math. 25(1979), no. 3, 289--291. MR0534947 (80i:05007)

William Feller,  "Introduction to Probability Theory and its Applications", vol. I, ed. 2, chap.3, sect.1,2.

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

Ki Hang Kim, Douglas G. Rogers, and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013).

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

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

G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41.

A. Laradji and A. Umar, On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2004), 184-200 - Abdullahi Umar, Aug 25 2008

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

Andrzej Proskurowski and Ekaputra Laiman, Fast enumeration, ranking, and unranking of binary trees. Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982). Congr. Numer. 35 (1982), 401-413.MR0725898 (85a:68152).

Yidong Sun, A simple bijection between binary trees and colored ternary trees, El. J. Combinat. 17 (2010) #N20

LINKS

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.

Jean-Christophe Aval, Multivariate Fuss-Catalan numbers, arXiv:0711.0906.

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

E. Barcucci and Verri, Some more properties of Catalan numbers, Discrete Math., 102 (1992), 229-237.

Paul Barry, On the Inverses of a Family of Pascal-Like Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.6.

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

A. Bernini, L. Ferrari, R. Pinzani and J. West, The Dyck pattern poset, arXiv preprint arXiv:1303.3785, 2013

N. Borie, Combinatorics of simple marked mesh patterns in 132-avoiding permutations, arXiv preprint arXiv:1311.6292, 2013

M. Bousquet-M\'{e}lou 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 and a new method for the Riordan array proof of combinatorial identities, 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.

L. Carlitz, Sequences, paths, ballot numbers

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.

R. Ehrenborg, S. Kitaev, E. Steingrimsson, Number of cycles in the graph of 312-avoiding permutations, arXiv preprint arXiv:1310.1520, 2013

G. Feinberg, K.-H. Lee, Homogeneous representations of KLR-algebras and fully commutative elements, arXiv preprint arXiv:1401.0845, 2014

D. Foata, G-N. Han, The doubloon polynomial triangle, Ram. J. 23 (2010), 107-126

Dominique Foata and Guo-Niu Han, Doubloons and new q-tangent numbers, Quart. J. Math. 62 (2) (2011) 417-432

C. A. Francisco, J. Mermin, J. Schweig, Catalan numbers, binary trees, and pointed pseudotriangulations, 2013.

Ira Gessel, Super ballot numbers.

Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

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, arXiv:math.CO/0512570

M. A. A. Obaid, S. K. Nauman, W. M. Fakieh, C. M. Ringel, The numbers of support-tilting modules for a Dynkin algebra, 2014.

P. Pagacz, M. Wojtylak, On the spectral properties of a class of H-selfadjoint random matrices and the underlying combinatorics, arXiv preprint arXiv:1310.2122, 2013

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

Planet Math, Lattice Paths and ballot numbers.

L. Pudwell, Avoiding an Ordered Partition of Length 3, 2013.

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

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

T. Sillke, Catalan's numbers

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

Eric Weisstein's World of Mathematics, Catalan's Triangle

Eric Weisstein's World of Mathematics, Nonnegative Partial Sum

R. J. Cano, Catalan's books

FORMULA

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

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(t*x)/(1-x*C(t*x)) = 1+(1+t)*x+(1+2*t+2*t^2)*x^2+..., where C(x) = (1-sqrt(1-4*x))/(2*x) is the Catalan function. - Emeric Deutsch, 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 Deléham, Feb 16 2005

O.g.f. (with offset 1) is the series reversion of x*(1+x*(1-t))/(1+x)^2 = x - x^2*(1+t) + x^3*(1+2*t) - x^4*(1+3*t) + .... - Peter Bala, Jul 15 2012

sum(T(n-k+p-1, k+p-1), k=0..floor(n/2)) = A001405(n+2*p-2) - C(n+2*p-2, p-2), p >= 1. - Johannes W. Meijer, Oct 03 2013

EXAMPLE

Triangle begins in row n=0 with 0<=k<=n:

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

MAPLE

A009766 := proc(n, k) binomial(n+k, n)*(n-k+1)/(n+1) ; end proc:

seq(seq( A009766(n, k), k=0..n), n=0..10) ; # R. J. Mathar, Dec 03 2010

MATHEMATICA

Flatten[NestList[Append[Accumulate[#], Last[Accumulate[#]]] &, {1}, 9]] (* Birkas Gyorgy, May 19 2012 *)

PROG

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

(Haskell)

a009766 n k = a009766_tabl !! n !! k

a009766_row n = a009766_tabl !! n

a009766_tabl = iterate (\row -> scanl1 (+) (row ++ [0])) [1]

-- Reinhard Zumkeller, Jul 12 2012

(Sage)

@CachedFunction

def ballot(p, q):

    if p == 0 and q == 0: return 1

    if p < 0 or p > q: return 0

    S = ballot(p-2, q) + ballot(p, q-2)

    if q % 2 == 1: S += ballot(p-1, q-1)

    return S

A009766 = lambda n, k: ballot(2*k, 2*n)

for n in (0..7): [A009766(n, k) for k in (0..n)]  # Peter Luschny, Mar 05 2014

(PARI) b009766=(n1=0, n2=100)->{my(q=if(!n1, 0, binomial(n1+1, 2))); for(w=n1, n2, for(k=0, w, write("b009766.txt", 1*q" "1*(binomial(w+k, w)-binomial(w+k, w+1))); q++))} \\ R. J. Cano, Jul 22 2014

CROSSREFS

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

Cf. A062745, A214292.

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.

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

Triangle sums (see the comments): A000108 (Row1), A000957 (Row2), A001405 (Kn11), A014495 (Kn12), A194124 (Kn13), A030238 (Kn21), A000984 (Kn4), A000958 (Fi2), A165407 (Ca1), A026726 (Ca4), A081696 (Ze2).

Sequence in context: A188181 A064581 A064580 * A059718 A076038 A095788

Adjacent sequences:  A009763 A009764 A009765 * A009767 A009768 A009769

KEYWORD

nonn,tabl,nice,changed

AUTHOR

Wouter Meeussen.

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 20 00:14 EDT 2014. Contains 248320 sequences.