

A001263


Triangle of Narayana numbers T(n,k) = C(n1,k1)C(n,k1)/k with 1<=k<=n, read by rows. Also called the Catalan triangle.


223



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)



OFFSET

1,5


COMMENTS

Antichains (or order ideals) in the poset 2*(k1)*(nk) or plane partitions with rows <= k1, columns <= nk and entries <= 2.  Mitch Harris, Jul 15 2000
a(n,k) = number of Dyck npaths with exactly k peaks. a(n,k) = number of pairs (P,Q) of lattice paths from (0,0) to (k,n+1k), 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 avoid132 and have k1 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 k1 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 nth row can be generated by the following operation using an ascending row of (n1) 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 KostovShapiro 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 SchurSzego composition map sending (n1)tuples of polynomials of the form (x+1)^{n1}(x+a) to their SchurSzego product, see below. As a corollary we obtain that every N_n(x) has all roots real and nonpositive. Additionally, we present an explicit formula for the density and the distribution function of the asymptotic rootcounting 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 orderdecreasing and orderpreserving mappings (of an nelement 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 hvector of the simplicial complex dual to an associahedron of type A_n [Fomin & Reading, p.60]. See A033282 for the corresponding array of fvectors for associahedra of type A_n. See A008459 and A145903 for the hvectors 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 nth 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(nk) = 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


REFERENCES

Bacher, Axel; Bernini, Antonio; Ferrari, Luca; Gunby, Benjamin; Pinzani, Renzo; West, Julian. The Dyck pattern poset. Discrete Math. 321 (2014), 1223. MR3154009.
Berman and Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), pp. 103124.
Jonathan M. Borwein, Armin Straub and Christophe Vignat, Densities of short uniform random walks, Part II: Higher dimensions, Preprint, 2015; http://www.carma.newcastle.edu.au/jon/dwalks.pdf
J. Cigler, Some remarks on lattice paths in strips along the xaxis; http://homepage.univie.ac.at/johann.cigler/preprints/latticepaths.pdf, 2014.
R. Cori, G. Hetyei, How to count genus one partitions, FPSAC 2014, Chicago, Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France, 2014, 333344; http://www.dmtcs.org/dmtcsojs/index.php/proceedings/article/viewFile/dmAT0130/4488
R. L. Graham and J. Riordan, The solution of a certain recurrence, Amer. Math. Monthly 73, 1966, pp. 604608.
H. E. Hoggatt, Jr., Triangular Numbers, Fibonacci Quarterly 12 (Oct. 1974), 221230.
Hwang, F. K.; Mallows, C. L.; Enumerating nested and consecutive partitions. J. Combin. Theory Ser. A 70 (1995), no. 2, 323333.
W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 5155.
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 341.
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel. Math. Sci. Humaines No. 53 (1976), 530.
Nate Kube and Frank Ruskey, Sequences that satisfy a(na(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
Laradji, A. and Umar, A. On certain finite semigroups of orderdecreasing transformations I, Semigroup Forum, 69 (2004), 184200.
P. A. MacMahon, Combinatory Analysis, Sect. 495, 1916.
Manes, K.; Sapounakis, A.; Tasoulas, I.; Tsikouras, P.; Nonleft peaks in Dyck paths: a combinatorial approach, Discrete Math., 337 (2014), 97105.
Toufik Mansour and Mark Shattuck, Patternavoiding set partitions and Catalan numbers, Electronic Journal of Combinatorics, 18(2) (2012), #P34.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100101.
A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137147.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 17.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 29092924.
R. P. Stanley, Theory and application of plane partitions. II. Studies in Appl. Math. 50 (1971), p. 259279. Thm. 18.1
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.36(a) and (b).
F. Yano and H. Yoshida, Some set partition statistics in noncrossing partitions and generating functions, Discr. Math., 307 (2007), 31473160.


LINKS

T. D. Noe, Rows n=1..100 of triangle, flattened
M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 25442563.
C. Athanasiadis and C. Savvidou, The local hvector of the cluster subdivision of a simplex, arXiv preprint arXiv:1204.0362, 2012, pg. 8, Lemma 2.4 A_n.  From Tom Copeland, Oct 19 2014
Paul Barry, On IntegerSequenceBased Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8.
S. Benchekroun, P. Moszkowski, A bijective proof of an enumerative property of legal bracketings Discrete Math. 176 (1997), no. 13, 273277.
Carl M. Bender and Gerald V. Dunne, Polynomials and operator orderings, J. Math. Phys. 29 (1988), 17271731;
A. Bernini, L. Ferrari, R. Pinzani and J. West, The Dyck pattern poset, arXiv preprint arXiv:1303.3785, 2013
M. Bona and B. E. Sagan, On divisibility of Narayana numbers by primes
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 132avoiding permutations, arXiv preprint arXiv:1311.6292, 2013
D. Callan, T. Mansour, M. Shattuck, Restricted ascent sequences and Catalan numbers, arXiv preprint arXiv:1403.6933, 2014
L. Carlitz, and John Riordan, Enumeration of some twoline arrays by extent. J. Combinatorial Theory Ser. A 10 1971 271283. MR0274301(43 #66). (Coefficients of the polynomials A_n(z) defined in (3.9)).
R. Cori, G. Hetyei, Counting genus one partitions and permutations, arXiv preprint arXiv:1306.4628, 2013
R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449, 2013
Yun Ding and Rosena R. X. Du, Counting Humps in Motzkin paths, arXiv preprint arXiv:1109.2661, 2011
T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 6782.
FindStat  Combinatorial Statistic Finder, The number of internal nodes of an ordered tree
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 182
S. Fomin, N. Reading, Root systems and generalized associahedra, Lecture notes for IAS/ParkCity 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), 4165.
S. Giraudo, Intervals of balanced binary trees in the Tamari lattice, arXiv preprint arXiv:1107.3472, 2011
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 preprint, 2015.
F. Hivert, J.C. Novelli and J.Y. Thibon, Commutative combinatorial Hopf algebras
M. Hyatt and J. Remmel, The classification of 231avoiding permutations by descents and maximum drop, arXiv preprint arXiv:1208.1052, 2012.
S. Kamioka, Laurent biorthogonal polynomials, qNarayana polynomials and domino tilings of the Aztec diamonds, arXiv preprint arXiv:1309.0268, 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 SchurSzego composition
A. Laradji and A. Umar, Combinatorial Results for Semigroups of OrderDecreasing Partial Transformations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.8.
P. A. MacMahon, Combinatory analysis.
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
J.C. Novelli and J.Y. Thibon, Polynomial realizations of some trialgebras, Proc. Formal Power Series and Algebraic Combinatorics 2006 (SanDiego, 2006)
J.C. Novelli and J.Y. Thibon, Hopf algebras and dendriform structures arising from parking functions, Fundamenta Mathematicae 193 (2007), pp. 189241, arXiv:0511200.
J.C. Novelli, J.Y. Thibon, Hopf Algebras of mpermutations,(m+1)ary trees, and mparking functions, arXiv preprint arXiv:1403.5962, 2014. See Fig. 4.
M. Sheppeard, Constructive motives and scattering 2013 (pg. 41).  From Tom Copeland, Oct 03 2014
R. A. Sulanke, Moments, Narayana numbers and the cut and paste for lattice paths
R. A. Sulanke, Threedimensional Narayana and Schröder numbers
W. Wang and T. Wang, Generalized Riordan arrays, Discrete Mathematics, Vol. 308, No. 24, 64666500.
Wikipedia, Noncrossing partition
L. K. Williams, Enumeration of totally positive Grassmann cells
J. Wuttke, The zigzag walk with scattering and absorption on the real half line and in a lattice model, J. Phys. A 47 (2014), 215203, 19.


FORMULA

a(n, k) = C(n1, k1)C(n, k1)/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..n1, sum(r=1..k1, a(n1i, kr) a(i, r))) + a(n1, k) a(n, k) = sum(i=1..k1, binomial(n+i1, 2k2)*a(k1, i))  Mike Zabrocki, Aug 26 2004
T(n, k) = C(n, k)*C(n1, k1)  C(n, k1)*C(n1, k) (determinant of a 2 X 2 subarray of Pascal's triangle A007318).  Gerald McGarvey, Feb 24 2005
T(n, k) = binomial(n1, k1)^2  binomial(n1, k)binomial(n1, k2).  David Callan, Nov 02 2005
a(n,k) = C(n,2) (a(n1,k)/((nk)(nk+1)) + a(n1,k1)/(k(k1))) a(n,k) = C(n,k) C(n,k1)/n.  Mitch Harris, Jul 06 2006
Central column = A000891, (2n)!(2n+1)! / (n! (n+1)!)^2.  Zerinvary Lajos, Oct 29 2006
G.f.: (1x*(1+y)sqrt((1x*(1+y))^24*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*(1x)^n*Jacobi_P(n,1,1,(1+x)/(1x)). 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)/(1y)^(k+3) * Jacobi_P(k,1,1,(1+y)/(1y)). 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 halfplane 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 xadic 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/(1xxyx^2y/(1xxyx^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)*xsqrt(12*(1+t)*x+((t1)*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 / (tx^2), the nth 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,1,...,infinity) A132710^j / A010790(j), a normalized Bessel fct. May be represented as the Pascal matrix A007318, n!/[(nk)!*k!], umbralized with b(n)=A002378(n) for n>0 and b(0)=1: A001263(n,k)= b.(n!)/{b.[(nk)!]*b.(k!)} where b.(n!) = b(n)*b(n1)...*b(0), a generalized factorial (see example).  Tom Copeland, Sep 21 2011
With F(x,t) = {1(1t)*xsqrt[12*(1+t)*x+[(t1)*x]^2]}/2 a shifted o.g.f. in x for the Narayana polynomials in t, G(x,t)= x/[t1+1/(1x)] is the compositional inverse in x. Therefore, with H(x,t)=1/(dG(x,t)/dx)=[t1+1/(1x)]^2/{t[x/(1x)]^2}, (see A119900), the (n1)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(n1,k1)*binomial(n+1,k)binomial(n,k1)*binomial(n,k).  Philippe Deléham, Nov 05 2011
Damped sum of a column, in leading order: Lim_{d>0} d^(2k1) Sum_{N>=k} T(N,k)(1d)^N=Catalan(n).  Joachim Wuttke, Sep 11 2014


EXAMPLE

For all n are 12...n (1 block) and 123...n (n blocks) 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:
A007318(5,k)=[1,5/1,5*4/(2*1),...,1]=(1,5,10,10,5,1),
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


MAPLE

a := (n, k)>binomial(n1, k1)*binomial(n, k1)/k;
a:=proc(n, k) option remember; local i; if k=1 or k=n then 1 else add(binomial(n+i1, 2*k2)*a(k1, i), i=1..k1); fi; end:


MATHEMATICA

T[n_, k_] := If[k==0, 0, Binomial[n1, k1] Binomial[n, k1] / k];
Flatten[Table[Binomial[n1, k1] Binomial[n, k1]/k, {n, 15}, {k, n}]] (* Harvey P. Dale, Feb 29 2012 *)


PROG

(PARI) {a(n, k) = if(k==0, 0, binomial(n1, k1) * binomial(n, k1) / 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
(Haskell)
a001263 n k = a001263_tabl !! (n1) !! (k1)
a001263_row n = a001263_tabl !! (n1)
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(n1, k1)*Binomial(n, k1)/k : k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, Oct 19 2014
(Sage)
@CachedFunction
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(n1, k)/((nk)*(nk+1)) + T(n1, k1)/(k*(k1)))
for n in (1..9): print [T(n, k) for k in (1..n)] # Peter Luschny, Oct 28 2014


CROSSREFS

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, A084938.
A108679 (6th column).  Zerinvary Lajos, Jun 18 2007
Cf. A000372, A002083, A056932, A056939, A056940, A056941, A065329, A073345.
A145596, A145597, A145598, A145599.  Peter Bala, Oct 22 2008
A008459 (hvectors type B associahedra), A033282 (fvectors type A associahedra), A145903 (hvectors type D associahedra), A145904 (Hilbert transform).  Peter Bala, Oct 27 2008
Cf. A016098 and A189232 for numbers of crossing set partitions.
Cf. A243752.
Sequence in context: A114176 A056241 A162745 * A162747 A107105 A088925
Adjacent sequences: A001260 A001261 A001262 * A001264 A001265 A001266


KEYWORD

nonn,easy,tabl,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



