The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001263 Triangle of Narayana numbers T(n,k) = C(n-1,k-1)*C(n,k-1)/k with 1 <= k <= n, read by rows. Also called the Catalan triangle. 282
1, 1, 1, 1, 3, 1, 1, 6, 6, 1, 1, 10, 20, 10, 1, 1, 15, 50, 50, 15, 1, 1, 21, 105, 175, 105, 21, 1, 1, 28, 196, 490, 490, 196, 28, 1, 1, 36, 336, 1176, 1764, 1176, 336, 36, 1, 1, 45, 540, 2520, 5292, 5292, 2520, 540, 45, 1, 1, 55, 825, 4950, 13860, 19404, 13860, 4950, 825 (list; table; graph; refs; listen; history; text; internal format)



Number of antichains (or order ideals) in the poset 2*(k-1)*(n-k) or plane partitions with rows <= k-1, columns <= n-k and entries <= 2. - Mitch Harris, Jul 15 2000

a(n,k) = number of Dyck n-paths with exactly k peaks. a(n,k) = number of pairs (P,Q) of lattice paths from (0,0) to (k,n+1-k), each consisting of unit steps East or North, such that P lies strictly above Q except at the endpoints. - David Callan, Mar 23 2004

Number of permutations of [n] which avoid-132 and have k-1 descents. - Mike Zabrocki, Aug 26 2004

a(n,k) is the number of paths through n panes of glass, entering and leaving from one side, of length 2n with k reflections (where traversing one pane of glass is the unit length). - Mitch Harris, Jul 06 2006

Antidiagonal sums given by A004148 (without first term).

T(n,k) is the number of full binary trees with n internal nodes and k-1 jumps. 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. - Emeric Deutsch, Jan 18 2007

From Gary W. Adamson, Oct 22 2007: (Start)

The n-th row can be generated by the following operation using an ascending row of (n-1) triangular terms, (A) and a descending row, (B); e.g., row 6:

A: 1....3....6....10....15

B: 15...10....6.....3.....1

C: 1...15...50....50....15....1 = row 6.

Leftmost column of A,B -> first two terms of C; then followed by the operation B*C/A of current column = next term of row C, (e.g., 10*15/3 = 50). Continuing with the operation, we get row 6: (1, 15, 50, 50, 15, 1). (End)

The previous comment can be upgraded to: The ConvOffsStoT transform of the triangular series; and by rows, row 6 is the ConvOffs transform of (1, 3, 6, 10, 15). Refer to triangle A117401 as another example of the ConvOffsStoT transform, and OEIS under Maple Transforms. - Gary W. Adamson, Jul 09 2012

From the Kostov-Shapiro paper: "In the present paper we find a new interpretation of Narayana polynomials N_n(x) which are the generating polynomials for the Narayana numbers N_{n,k} counting Dyck paths of length n and with exactly k peaks. Strangely enough Narayana polynomials also occur as limits as n->oo of the sequences of eigenpolynomials of the Schur-Szego composition map sending (n-1)-tuples of polynomials of the form (x+1)^{n-1}(x+a) to their Schur-Szego product, see below. As a corollary we obtain that every N_n(x) has all roots real and non-positive. Additionally, we present an explicit formula for the density and the distribution function of the asymptotic root-counting measure of the polynomial sequence {N_n(x)}." - Jonathan Vos Post, Apr 08 2008

For a connection to Lagrange inversion, see A134264. - Tom Copeland, Aug 15 2008

T(n,k) is also the number of order-decreasing and order-preserving mappings (of an n-element set) of height k (height of a mapping is the cardinal of its image set). - Abdullahi Umar, Aug 21 2008

Row n of this triangle is the h-vector of the simplicial complex dual to an associahedron of type A_n [Fomin & Reading, p.60]. See A033282 for the corresponding array of f-vectors for associahedra of type A_n. See A008459 and A145903 for the h-vectors for associahedra of type B and type D respectively. The Hilbert transform of this triangle (see A145905 for the definition of this transform) is A145904. - Peter Bala, Oct 27 2008

T(n,k) is also the number of noncrossing set partitions of [n] into k blocks. Given a partition P of the set {1,2,...,n}, a crossing in P are four integers [a, b, c, d] with 1 <= a < b < c < d <= n for which a, c are together in a block, and b, d are together in a different block. A noncrossing partition is a partition with no crossings. - Peter Luschny, Apr 29 2011

Diagonals of A089732 are rows of A001263. - Tom Copeland, May 14 2012

From Peter Bala, Aug 07 2013: (Start)

Let E(y) = Sum_{n >= 0} y^n/(n!*(n+1)!) = 1/sqrt(y)*BesselI(1,2*sqrt(y)). Then this triangle is the generalized Riordan array (E(y), y) with respect to the sequence n!*(n+1)! as defined in Wang and Wang.

Generating function E(y)*E(x*y) = 1 + (1 + x)*y/(1!*2!) + (1 + 3*x + x^2)*y^2/(2!*3!) + (1 + 6*x + 6*x^2 + x^3)*y^3/(3!*4!) + .... Cf. A105278 with a generating function exp(y)*E(x*y).

The n-th power of this array has a generating function E(y)^n*E(x*y). In particular, the matrix inverse A103364 has a generating function E(x*y)/E(y). (End)

A166360(n-k) = T(n,k) mod 2. - Reinhard Zumkeller, Oct 10 2013

T(n,k) is the number of nonintersecting n arches above the x axis, starting and ending on vertices 1 to 2n, with k being the number of arches starting on an odd vertice and ending on a higher even vertice. Example: T(3,2)=3  [16,25,34] [14,23,56] [12,36,45]. - Roger Ford, Jun 14 2014

Fomin and Reading on p. 31 state that the rows of the Narayana matrix are the h-vectors of the associahedra as well as its dual. - Tom Copeland, Jun 27 2017

The row polynomials P(n, x) = Sum_{k=1..n} T(n, k)*x^(k-1), together with P(0, x) = 1, multiplied by (n+1) are the numerator polynomials of the o.g.f.s of the diagonal sequences of the triangle A103371: G(n, x) = (n+1)*P(n, x)/(1 - x)^{2*n+1}, for n >= 0. This is proved with Lagrange's theorem applied to the Riordan triangle A135278 = (1/(1 - x)^2, x/(1 - x)). See an example below. - Wolfdieter Lang, Jul 31 2017

T(n,k) is the number of Dyck paths of semilength n with k-1 uu-blocks (pairs of consecutive up-steps). - Alexander Burstein, Jun 22 2020

In case you were searching for Narayama numbers, the correct spelling is Narayana. - N. J. A. Sloane, Nov 11 2020


Berman and Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), pp. 103-124.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 196.

Ricky X. F. Chen and Christian M. Reidys, A Combinatorial Identity Concerning Plane Colored Trees and its Applications, Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.7.

P. A. MacMahon, Combinatory Analysis, Sect. 495, 1916.

T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100-101.

A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.

T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Chapter 2.

J. Riordan, Combinatorial Identities, Wiley, 1968, p. 17.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.36(a) and (b).

R. A. Sulanke, Catalan path statistics having the Narayana distribution, Discrete Math., vol. 180 (1998), 369--389. [Gives additional contexts where Narayana numbers appear. - N. J. A. Sloane, Nov 11 2020]


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

M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.

Per Alexandersson, Svante Linusson, Samu Potka, and Joakim Uhlin, Refined Catalan and Narayana cyclic sieving, arXiv:2010.11157 [math.CO], 2020.

N. Alexeev, A. Tikhomirov, Singular Values Distribution of Squares of Elliptic Random Matrices and type-B Narayana Polynomials, arXiv preprint arXiv:1501.04615 [math.PR], 2015.

Jarod Alper, Rowan Rowlands, Syzygies of the apolar ideals of the determinant and permanent, arXiv:1709.09286 [math.AC], 2017.

C. Athanasiadis and C. Savvidou, The local h-vector of the cluster subdivision of a simplex, arXiv:1204.0362 [math.CO], 2012, p. 8, Lemma 2.4 A_n. [Tom Copeland, Oct 19 2014]

Arvind Ayyer, Matthieu Josuat-Vergès, Sanjay Ramassamy, Extensions of partial cyclic orders and consecutive coordinate polytopes, arXiv:1803.10351 [math.CO], 2018.

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

J. L. Baril, S. Kirgizov, The pure descent statistic on permutations, Preprint, 2016.

M. Barnabei, F. Bonetti, M. Silmbani, Two Permutation Classes Enumerated by the Central Binomial Coefficients, J. Int. Seq. 16 (2013) #13.3.8.

Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

P. Barry, On a Generalization of the Narayana Triangle, J. Int. Seq. 14 (2011) # 11.4.5.

Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.

Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.

Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.

Paul Barry, The Gamma-Vectors of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1804.05027 [math.CO], 2018.

Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.

Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.

P. Barry, A. Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations , J. Int. Seq. 14 (2011) # 11.3.8.

Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8.

C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015.

S. Benchekroun, P. Moszkowski, A bijective proof of an enumerative property of legal bracketings Discrete Math. 176 (1997), no. 1-3, 273-277.

Carl M. Bender and Gerald V. Dunne, Polynomials and operator orderings, J. Math. Phys. 29 (1988), 1727-1731.

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]

A. Bernini, L. Ferrari, R. Pinzani and J. West, The Dyck pattern poset, arXiv:1303.3785 [math.CO], 2013.

Aubrey Blecher, Charlotte Brennan, Arnold Knopfmacher, and Toufik Mansour, The perimeter of words, Discrete Mathematics, 340, no. 10 (2017): 2456-2465.

M. Bona and B. E. Sagan, On divisibility of Narayana numbers by primes, arXiv:math/0505382 [math.CO], 2005.

M. Bona and B. E. Sagan, On Divisibility of Narayana Numbers by Primes, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.4.

N. Borie, Combinatorics of simple marked mesh patterns in 132-avoiding permutations, arXiv:1311.6292 [math.CO], 2013.

J. M. Borwein, A short walk can be beautiful, 2015.

Jonathan M. Borwein, Armin Straub and Christophe Vignat, Densities of short uniform random walks, Part II: Higher dimensions, Preprint, 2015.

Kevin Buchin, Man-Kwun Chiu, Stefan Felsner, Günter Rote, André Schulz, The Number of Convex Polyominoes with Given Height and Width, arXiv:1903.01095 [math.CO], 2019.

Michael Bukata, Ryan Kulwicki, Nicholas Lewandowski, Lara Pudwell, Jacob Roth, Teresa Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv:1812.07112 [math.CO], 2018.

Alexander Burstein, Distribution of peak heights modulo k and double descents on k-Dyck paths, arXiv:2009.00760 [math.CO], 2020.

D. Callan, T. Mansour, M. Shattuck, Restricted ascent sequences and Catalan numbers, arXiv:1403.6933 [math.CO], 2014.

L. Carlitz, and John Riordan, Enumeration of some two-line arrays by extent. J. Combinatorial Theory Ser. A 10 1971 271--283. MR0274301(43 #66). (Coefficients of the polynomials A_n(z) defined in (3.9)).

Xi Chen, H. Liang, Y. Wang, Total positivity of recursive matrices, Linear Algebra and its Applications, Volume 471, 15 April 2015, Pages 383-393.

Xi Chen, H. Liang, Y. Wang, Total positivity of recursive matrices, arXiv:1601.05645 [math.CO], 2016.

Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015-2016.

T. Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms, 2015.

R. Cori, G. Hetyei, Counting genus one partitions and permutations, arXiv:1306.4628 [math.CO], 2013.

R. Cori, G. Hetyei, How to count genus one partitions, FPSAC 2014, Chicago, Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France, 2014, 333-344.

R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv:1310.2449 [cs.DM], 2013.

Colin Defant, Counting 3-Stack-Sortable Permutations, arXiv:1903.09138 [math.CO], 2019.

Yun Ding and Rosena R. X. Du, Counting Humps in Motzkin paths, arXiv:1109.2661 [math.CO], 2011.

T. Doslic, Handshakes across a (round) table, JIS 13 (2010) #10.2.7.

T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 67-82.

D. Drake, Bijections from Weighted Dyck Paths to Schröder Paths</a, J. Int. Seq. 13 (2010) # 10.9.2.

L. Ferrari, E. Munarini, Enumeration of Edges in Some Lattices of Paths, J. Int. Seq. 17 (2014) #14.1.5.

FindStat - Combinatorial Statistic Finder, The number of peaks of a Dyck path, The number of double rises of a Dyck path, The number of valleys of a Dyck path, The number of left oriented leafs except the first one of a binary tree, The number of left tunnels of a Dyck path.

T. A. Fisher, A Caldero-Chapoton map depending on a torsion class, arXiv:1510.07484 [math.RT], 2015-2016.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 182.

S. Fomin, N. Reading, Root systems and generalized associahedra, Lecture notes for IAS/Park-City 2004.

Alessandra Frabetti, Simplicial properties of the set of planar binary trees.

A. Frabetti, Simplicial properties of the set of planar binary trees, J. Algebraic Combin., 13 (2001), 41-65.

S. Giraudo, Intervals of balanced binary trees in the Tamari lattice, arXiv:1107.3472 [math.CO], 2011.

Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.

R. L. Graham and J. Riordan, The solution of a certain recurrence, Amer. Math. Monthly 73, 1966, pp. 604-608.

R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Kevin G. Hare, Ghislain McKay, Some properties of even moments of uniform random walks, arXiv:1506.01313 [math.CO], 2015.

F. Hivert, J.-C. Novelli and J.-Y. Thibon, Commutative combinatorial Hopf algebras, arXiv:math/0605262 [math.CO], 2006.

H. E. Hoggatt, Jr., Triangular Numbers, Fibonacci Quarterly 12 (Oct. 1974), 221-230.

F. K. Hwang and C. L. Mallows, Enumerating nested and consecutive partitions, J. Combin. Theory Ser. A 70 (1995), no. 2, 323-333.

M. Hyatt and J. Remmel, The classification of 231-avoiding permutations by descents and maximum drop, arXiv:1208.1052 [math.CO], 2012.

Matthieu Josuat-Verges, A q-analog of Schläfli and Gould identities on Stirling numbers, Preprint, 2016.

S. Kamioka, Laurent biorthogonal polynomials, q-Narayana polynomials and domino tilings of the Aztec diamonds, arXiv:1309.0268 [math.CO], 2013.

Thomas Koshy, Illustration of triangle with dark color for odd number, light for even number [Although the illustration says "Applet", this is simply a plain jpeg file]

Vladimir Kostov and Boris Shapiro, Narayana numbers and Schur-Szego composition, arXiv:0804.1028 [math.CA], 2008.

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. [Annotated scanned copy]

G. Kreweras, Traitement simultané du "Problème de Young" et du "Problème de Simon Newcomb", Cahiers du Bureau Universitaire de Recherche Opérationnelle. Institut de Statistique, Université de Paris, 10 (1967), 23-31.

G. Kreweras, Traitement simultané du "Problème de Young" et du "Problème de Simon Newcomb", Cahiers du Bureau Universitaire de Recherche Opérationnelle. Institut de Statistique, Université de Paris, 10 (1967), 23-31. [Annotated scanned copy]

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.

G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.

G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)

G. Kreweras, and P. Moszkowski, A new enumerative property of the Narayana numbers, Journal of statistical planning and inference 14.1 (1986): 63-67.

Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.

A. Laradji and A. Umar, Combinatorial Results for Semigroups of Order-Decreasing Partial Transformations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.8.

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

Elżbieta Liszewska, Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.

P. A. MacMahon, Combinatory analysis.

K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Nonleft peaks in Dyck paths: a combinatorial approach, Discrete Math., 337 (2014), 97-105.

Toufik Mansour, Reza Rastegar, On typical triangulations of a convex n-gon, arXiv:1911.04025 [math.CO], 2019.

Toufik Mansour, Reza Rastegar, Alexander Roitershtein, Gökhan Yıldırım, The longest increasing subsequence in involutions avoiding 3412 and another pattern, arXiv:2001.10030 [math.CO], 2020.

Toufik Mansour and Mark Shattuck, Pattern-avoiding set partitions and Catalan numbers, Electronic Journal of Combinatorics, 18(2) (2012), #P34.

Toufik Mansour, Gökhan Yıldırım, Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences, arXiv:1808.05430 [math.CO], 2018.

A. Marco and J.-J. Martinez, A total positivity property of the Marchenko-Pastur Law, Electronic Journal of Linear Algebra, Volume 30 (2015), #7, pp. 106-117.

MathOverflow, Narayana polynomials as numerator polynomials for Ehrhart series rational functions?, a MO question posed by Tom Copeland and answered by Richard Stanley, 2017.

D. Merlini, R. Sprugnoli and M. C. Verri, Waiting patterns for a printer, FUN with algorithm'01, Isola d'Elba, 2001.

A. Micheli and D. Rossin, Edit distance between unlabeled ordered trees, arXiv:math/0506538 [math.CO], 2005.

J.-C. Novelli and J.-Y. Thibon, Polynomial realizations of some trialgebras, arXiv:math/0605061 [math.CO], 2006; Proc. Formal Power Series and Algebraic Combinatorics 2006 (San-Diego, 2006).

J.-C. Novelli and J.-Y. Thibon, Hopf algebras and dendriform structures arising from parking functions, Fundamenta Mathematicae 193 (2007), pp. 189-241; arXiv version, 0511200 [math.CO], 2005.

J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv:1403.5962 [math.CO], 2014. See Fig. 4.

Judy-anne Osborn, Bi-banded paths, a bijection and the Narayana numbers, Australasian Journal of Combinatorics, Volume 48 (2010), Pages 243-252.

T. K. Petersen, Chapter 2. Narayana numbers. In: Eulerian Numbers. Birkhäuser Basel, 2015. doi:10.1007/978-1-4939-3091-3.

Vincent Pilaud, V Pons, Permutrees, arXiv:1606.09643 [math.CO], 2016-2017.

Lara Pudwell, On the distribution of peaks (and other statistics), 16th International Conference on Permutation Patterns, Dartmouth College, 2018.

Dun Qiu, Jeffery Remmel, Patterns in words of ordered set partitions, arXiv:1804.07087 [math.CO], 2018.

Marko Riedel, Math Stackexchange, Narayana numbers count unlabeled ordered rooted trees on n nodes having k leaves, proof.

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Paul R. F. Schumacher, Descents in Parking Functions, J. Int. Seq. 21 (2018), #18.2.3.

M. Sheppeard, Constructive motives and scattering 2013 (p. 41). [Tom Copeland, Oct 03 2014]

R. P. Stanley, Theory and application of plane partitions, II. Studies in Appl. Math. 50 (1971), p. 259-279. DOI:10.1002/sapm1971503259. Thm. 18.1.

R. A. Sulanke, Moments, Narayana numbers and the cut and paste for lattice paths

R. A. Sulanke, Three-dimensional Narayana and Schröder numbers

A. Umar, Some combinatorial problems in the theory of symmetric ..., Algebra Disc. Math. 9 (2010) 115-126.

W. Wang and T. Wang, Generalized Riordan arrays, Discrete Mathematics, Vol. 308, No. 24, 6466-6500.

Yi Wang and Arthur L.B. Yang, Total positivity of Narayana matrices, arXiv:1702.07822 [math.CO], 2017.

Wikipedia, Noncrossing partition

L. K. Williams, Enumeration of totally positive Grassmann cells, arXiv:math/0307271 [math.CO], 2003-2004.

Anthony James Wood, Nonequilibrium steady states from a random-walk perspective, Ph. D. Thesis, The University of Edinburgh (Scotland, UK 2019), 44-46.

Anthony J. Wood, Richard A. Blythe, Martin R. Evans, Combinatorial mappings of exclusion processes, arXiv:1908.00942 [cond-mat.stat-mech], 2019.

J. Wuttke, The zig-zag walk with scattering and absorption on the real half line and in a lattice model, J. Phys. A 47 (2014), 215203, 1-9.

F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.


a(n, k) = C(n-1, k-1)*C(n, k-1)/k for k!=0; a(n, 0)=0.

Triangle equals [0, 1, 0, 1, 0, 1, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...] where DELTA is Deléham's operator defined in A084938.

0<n, 1<=k<=n a(n, 1) = a(n, n) = 1 a(n, k) = sum(i=1..n-1, sum(r=1..k-1, a(n-1-i, k-r) a(i, r))) + a(n-1, k) a(n, k) = sum(i=1..k-1, binomial(n+i-1, 2k-2)*a(k-1, i)) - Mike Zabrocki, Aug 26 2004

T(n, k) = C(n, k)*C(n-1, k-1) - C(n, k-1)*C(n-1, k) (determinant of a 2 X 2 subarray of Pascal's triangle A007318). - Gerald McGarvey, Feb 24 2005

T(n, k) = binomial(n-1, k-1)^2 - binomial(n-1, k)*binomial(n-1, k-2). - David Callan, Nov 02 2005

a(n,k) = C(n,2) (a(n-1,k)/((n-k)*(n-k+1)) + a(n-1,k-1)/(k*(k-1))) a(n,k) = C(n,k)*C(n,k-1)/n. - Mitch Harris, Jul 06 2006

Central column = A000891, (2n)!*(2n+1)! / (n!*(n+1)!)^2. - Zerinvary Lajos, Oct 29 2006

G.f.: (1-x*(1+y)-sqrt((1-x*(1+y))^2-4*y*x^2))/(2*x) = Sum_{n>0, k>0} a(n, k)*x^n*y^k.

From Peter Bala, Oct 22 2008: (Start)

Relation with Jacobi polynomials of parameter (1,1):

Row n+1 generating polynomial equals 1/(n+1)*x*(1-x)^n*Jacobi_P(n,1,1,(1+x)/(1-x)). It follows that the zeros of the Narayana polynomials are all real and nonpositive, as noted above. O.g.f for column k+2: 1/(k+1) * y^(k+2)/(1-y)^(k+3) * Jacobi_P(k,1,1,(1+y)/(1-y)). Cf. A008459.

T(n+1,k) is the number of walks of n unit steps on the square lattice (i.e., each step in the direction either up (U), down (D), right (R) or left (L)) starting from the origin and finishing at lattice points on the x axis and which remain in the upper half-plane y >= 0 [Guy]. For example, T(4,3) = 6 counts the six walks RRL, LRR, RLR, UDL, URD and RUD, from the origin to the lattice point (1,0), each of 3 steps. Compare with tables A145596 - A145599.

Define a functional I on formal power series of the form f(x) = 1 + ax + bx^2 + ... by the following iterative process. Define inductively f^(1)(x) = f(x) and f^(n+1)(x) = f(x*f^(n)(x)) for n >= 1. Then set I(f(x)) = lim n -> infinity f^(n)(x) in the x-adic topology on the ring of formal power series; the operator I may also be defined by I(f(x)) := 1/x*series reversion of x/f(x).

The o.g.f. for this array is I(1 + t*x + t*x^2 + t*x^3 + ...) = 1 + t*x + (t + t^2)*x^2 + (t + 3*t^2 + t^3)*x^3 + ... = 1/(1 - x*t/(1 - x/(1 - x*t/(1 - x/(1 - ...))))) (as a continued fraction). Cf. A108767, A132081 and A141618. (End)

G.f.: 1/(1-x-xy-x^2y/(1-x-xy-x^2y/(1-... (continued fraction). - Paul Barry, Sep 28 2010

E.g.f.: exp((1+y)x)*Bessel_I(1,2*sqrt(y)x)/(sqrt(y)*x). - Paul Barry, Sep 28 2010

G.f.: A(x,y) = exp( Sum_{n>=1} [Sum_{k=0..n} C(n,k)^2*y^k] * x^n/n ). - Paul D. Hanna, Oct 13 2010

With F(x,t) = (1-(1+t)*x-sqrt(1-2*(1+t)*x+((t-1)*x)^2))/(2*x) an o.g.f. in x for the Narayana polynomials in t, G(x,t) = x/(t+(1+t)*x+x^2) is the compositional inverse in x. Consequently, with H(x,t) = 1/ (dG(x,t)/dx) = (t+(1+t)*x+x^2)^2 / (t-x^2), the n-th Narayana polynomial in t is given by (1/n!)*((H(x,t)*D_x)^n)x evaluated at x=0, i.e., F(x,t) = exp(x*H(u,t)*D_u)u, evaluated at u = 0. Also, dF(x,t)/dx = H(F(x,t),t). - Tom Copeland, Sep 04 2011

With offset 0, A001263 = Sum_{j>=0} A132710^j / A010790(j), a normalized Bessel fct. May be represented as the Pascal matrix A007318, n!/[(n-k)!*k!], umbralized with b(n)=A002378(n) for n>0 and b(0)=1: A001263(n,k)= b.(n!)/{b.[(n-k)!]*b.(k!)} where b.(n!) = b(n)*b(n-1)...*b(0), a generalized factorial (see example). - Tom Copeland, Sep 21 2011

With F(x,t) = {1-(1-t)*x-sqrt[1-2*(1+t)*x+[(t-1)*x]^2]}/2 a shifted o.g.f. in x for the Narayana polynomials in t, G(x,t)= x/[t-1+1/(1-x)] is the compositional inverse in x. Therefore, with H(x,t)=1/(dG(x,t)/dx)=[t-1+1/(1-x)]^2/{t-[x/(1-x)]^2}, (see A119900), the (n-1)-th Narayana polynomial in t is given by (1/n!)*((H(x,t)*d/dx)^n)x evaluated at x=0, i.e., F(x,t) = exp(x*H(u,t)*d/du) u, evaluated at u = 0. Also, dF(x,t)/dx = H(F(x,t),t). - Tom Copeland, Sep 30 2011

T(n,k) = binomial(n-1,k-1)*binomial(n+1,k)-binomial(n,k-1)*binomial(n,k). - Philippe Deléham, Nov 05 2011

Damped sum of a column, in leading order: Lim_{d->0} d^(2k-1) Sum_{N>=k} T(N,k)(1-d)^N=Catalan(n). - Joachim Wuttke, Sep 11 2014

Multiplying the n-th column by n! generates the revert of the unsigned Lah numbers, A089231. - Tom Copeland, Jan 07 2016

Row polynomials: (x - 1)^(n+1)*(P(n+1,(1 + x)/(x - 1)) - P(n-1,(1 + x)/(x - 1)))/((4*n + 2)), n = 1,2,... and where P(n,x) denotes the n-th Legendre polynomial. - Peter Bala, Mar 03 2017

The coefficients of the row polynomials R(n, x) = hypergeom([-n,-n-1], [2], x) generate the triangle based in (0,0). - Peter Luschny, Mar 19 2018

Multiplying the n-th diagonal by n!, with the main diagonal n=1, generates the Lah matrix A105278. With G equal to the infinitesimal generator of A132710, the Narayana triangle equals Sum_{n >= 0} G^n/((n+1)!*n!) = (sqrt(G))^(-1) * I_1(2*sqrt(G)), where G^0 is the identity matrix and I_1(x) is the modified Bessel function of the first kind of order 1. (cf. Sep 21 2011 formula also.) - Tom Copeland, Sep 23 2020

T(n,k) = T(n,k-1)*C(n-k+2,2)/C(k,2). - Yuchun Ji, Dec 21 2020


For all n, 12...n (1 block) and 1|2|3|...|n (n blocks) are noncrossing set partitions.

[1] 1

[2] 1,  1

[3] 1,  3,   1

[4] 1,  6,   6,    1

[5] 1, 10,  20,   10,    1

[6] 1, 15,  50,   50,   15,    1

[7] 1, 21, 105,  175,  105,   21,   1

[8] 1, 28, 196,  490,  490,  196,  28,  1

[9] 1, 36, 336, 1176, 1764, 1176, 336, 36, 1; etc.

Example of umbral representation:


  so A001263(5,k)={1,b(5)/b(1),b(5)*b(4)/[b(2)*b(1)],...,1}

  = [1,30/2,30*20/(6*2),...,1]=(1,15,50,50,15,1).

  First = last term = b.(5!)/[b.(0!)*b.(5!)]= 1. - Tom Copeland, Sep 21 2011

Row polynomials and diagonal sequences of A103371: n = 4,  P(4, x) = 1 + 6*x + 6*x^2 + x^3, and the o.g.f. of fifth diagonal is G(4, x) = 5* P(4, x)/(1 - x)^9, namely [5, 75, 525, ...]. See a comment above. - Wolfdieter Lang, Jul 31 2017


A001263 := (n, k)->binomial(n-1, k-1)*binomial(n, k-1)/k;

a:=proc(n, k) option remember; local i; if k=1 or k=n then 1 else add(binomial(n+i-1, 2*k-2)*a(k-1, i), i=1..k-1); fi; end:

# Alternatively, as a (0, 0)-based triangle:

R := n -> simplify(hypergeom([-n, -n-1], [2], x)): Trow := n -> seq(coeff(R(n, x), x, j), j=0..n): seq(Trow(n), n=0..9); # Peter Luschny, Mar 19 2018


T[n_, k_] := If[k==0, 0, Binomial[n-1, k-1] Binomial[n, k-1] / k];

Flatten[Table[Binomial[n-1, k-1] Binomial[n, k-1]/k, {n, 15}, {k, n}]] (* Harvey P. Dale, Feb 29 2012 *)

TRow[n_] := CoefficientList[Hypergeometric2F1[1 - n, -n, 2, x], x];

Table[TRow[n], {n, 1, 11}] // Flatten (* Peter Luschny, Mar 19 2018 *)


(PARI) {a(n, k) = if(k==0, 0, binomial(n-1, k-1) * binomial(n, k-1) / k)};

(PARI) {T(n, k)=polcoeff(polcoeff(exp(sum(m=1, n, sum(j=0, m, binomial(m, j)^2*y^j)*x^m/m) +O(x^(n+1))), n, x), k, y)} \\ Paul D. Hanna, Oct 13 2010


a001263 n k = a001263_tabl !! (n-1) !! (k-1)

a001263_row n = a001263_tabl !! (n-1)

a001263_tabl = zipWith dt a007318_tabl (tail a007318_tabl) where

   dt us vs = zipWith (-) (zipWith (*) us (tail vs))

                          (zipWith (*) (tail us ++ [0]) (init vs))

-- Reinhard Zumkeller, Oct 10 2013

(MAGMA) /* triangle */ [[Binomial(n-1, k-1)*Binomial(n, k-1)/k : k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, Oct 19 2014



def T(n, k):

    if k == n or k == 1: return 1

    if k <= 0 or k > n: return 0

    return binomial(n, 2) * (T(n-1, k)/((n-k)*(n-k+1)) + T(n-1, k-1)/(k*(k-1)))

for n in (1..9): print([T(n, k) for k in (1..n)])  # Peter Luschny, Oct 28 2014

(GAP) Flat(List([1..11], n->List([1..n], k->Binomial(n-1, k-1)*Binomial(n, k-1)/k))); # Muniru A Asiru, Jul 12 2018


Other versions are in A090181 and A131198. - Philippe Deléham, Nov 18 2007

Cf. variants: A181143, A181144. - Paul D. Hanna, Oct 13 2010

Row sums give A000108 (Catalan numbers), n>0.

Columns give A000217, A002415, A006542, A006857, A108679. A084938.

Cf. A000372, A002083, A056932, A056939, A056940, A056941, A065329, A073345.

A145596, A145597, A145598, A145599. - Peter Bala, Oct 22 2008

A008459 (h-vectors type B associahedra), A033282 (f-vectors type A associahedra), A145903 (h-vectors type D associahedra), A145904 (Hilbert transform). - Peter Bala, Oct 27 2008

Cf. A016098 and A189232 for numbers of crossing set partitions.

Cf. A243752.

Cf. A089231, A103371, A135278.

Cf. A002378, A007318, A010790, A089231, A089732, A105278, A119900, A132710, A134264.

Sequence in context: A114176 A056241 A162745 * A162747 A107105 A088925

Adjacent sequences:  A001260 A001261 A001262 * A001264 A001265 A001266




N. J. A. Sloane


Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 4 10:48 EST 2021. Contains 341791 sequences. (Running on oeis4.)