%I A001263
%S A001263 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,
%T A001263 1,1,28,196,490,490,196,28,1,1,36,336,1176,1764,1176,336,36,1,1,45,540,
%U A001263 2520,5292,5292,2520,540,45,1,1,55,825,4950,13860,19404,13860,4950,825
%N 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.
%C A001263 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
(Harris.Mitchell(AT)mgh.harvard.edu), Jul 15 2000
%C A001263 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 (callan(AT)stat.wisc.edu), Mar 23
2004
%C A001263 Number of permutations of [n] which avoid-132 and have k-1 descents -
Mike Zabrocki (zabrocki(AT)mathstat.yorku.ca), Aug 26 2004
%C A001263 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 (Harris.Mitchell(AT)mgh.harvard.edu),
Jul 06 2006
%C A001263 Antidiagonal sums given by A004148 (without first term).
%C A001263 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 (deutsch(AT)duke.poly.edu), Jan
18 2007
%C A001263 A108679 equals the 6th column of the table of Narayana numbers - Zerinvary
Lajos (zerinvarylajos(AT)yahoo.com), Jun 18 2007
%C A001263 Comment from Gary W. Adamson (qntmpkt(AT)yahoo.com), 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:
%C A001263 A: 1....3....6....10....15
%C A001263 B: 15...10....6.....3.....1
%C A001263 C: 1...15...50....50....15....1 = row 6.
%C A001263 (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)
%C A001263 Other versions are in A090181 and A131198 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr),
Nov 18 2007
%C A001263 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
(jvospost3(AT)gmail.com), Apr 08 2008
%C A001263 For an apparent connection to Lagrange inversion, see A134264. [From
Tom Copeland (tcjpn(AT)msn.com), Aug 15 2008]
%C A001263 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). [From A. Umar (aumarh(AT)squ.edu.om), Aug 21 2008]
%C A001263 Contribution from Peter Bala (pbala(AT)toucansurf.com), Oct 27 2008:
(Start)
%C A001263 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.
%C A001263 (End)
%D A001263 M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008),
2544-2563.
%D A001263 Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal
Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
%D A001263 Benchekroun, S.; Moszkowski, P.; A bijective proof of an enumerative
property of legal bracketings. Discrete Math. 176 (1997), no. 1-3,
273-277.
%D A001263 Berman and Koehler, Cardinalities of finite distributive lattices, Mitteilungen
aus dem Mathematischen Seminar Giessen, 121 (1976), p. 103-124
%D A001263 M. Bona and B. E. Sagan, On Divisibility of Narayana Numbers by Primes,
Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.4.
%D A001263 T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary
structures, Discr. Math., 285 (2004), 67-82.
%D A001263 A. Frabetti, Simplicial properties of the set of planar binary trees,
J. Algebraic Combin., 13 (2001), 41-65.
%D A001263 Hwang, F. K.; Mallows, C. L.; Enumerating nested and consecutive partitions.
J. Combin. Theory Ser. A 70 (1995), no. 2, 323-333.
%D A001263 W. Krandick, Trees and jumps and real roots, J. Computational and Applied
Math., 162, 2004, 51-55.
%D A001263 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 A001263 G. Kreweras, Les preordres totaux compatibles avec un ordre partiel.
Math. Sci. Humaines No. 53 (1976), 5-30.
%D A001263 Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal
of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
%D A001263 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 21 2008]
%D A001263 P. A. MacMahon, Combinatory Analysis, Sect. 495, 1916.
%D A001263 T. V. Narayana, Lattice Path Combinatorics with Statistical Applications.
Univ. Toronto Press, 1979, pp. 100-101.
%D A001263 A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans
in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.
%D A001263 A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck
paths, Discrete Math., 307 (2007), 2909-2924.
%D A001263 R. P. Stanley, Theory and application of plane partitions. II. Studies
in Appl. Math. 50 (1971), p. 259-279. Thm. 18.1
%D A001263 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see
Problem 6.36(a) and (b).
%D A001263 F. Yano and H. Yoshida, Some set partition statistics in non-crossing
partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.
%D A001263 J. Riordan, Combinatorial Identities, Wiley, 1968, p.17 [From Roger L.
Bagula (rlbagulatftn(AT)yahoo.com), Feb 13 2009]
%D A001263 Graham, R. L. and J. Riordan, The solution of a certain recurrence, Amer.
Math. Monthly 73, 1966, pp. 604-608 [From Roger L. Bagula (rlbagulatftn(AT)yahoo.com),
Feb 13 2009]
%H A001263 T. D. Noe, <a href="b001263.txt">Rows n=1..100 of triangle, flattened</
a>
%H A001263 M. Bona and B. E. Sagan, <a href="http://arXiv.org/abs/math.CO/0505382">
On divisibility of Narayana numbers by primes</a>
%H A001263 S. Fomin, N. Reading, <a href="http://arxiv.org/abs/math.CO/0505518">
Root systems and generalized associahedra</a>, Lecture notes for
IAS/Park-City 2004. [From Peter Bala (pbala(AT)toucansurf.com), Oct
27 2008]
%H A001263 Alessandra Frabetti, <a href="http://cartan.u-strasbg.fr/irma/publications/
1997/97040.shtml">Simplicial properties of the set of planar binary
trees</a>.
%H A001263 R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/
catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer
Sequences, Vol. 3 (2000), Article #00.1.6 [From Peter Bala (pbala(AT)toucansurf.com),
Oct 22 2008]
%H A001263 F. Hivert, J.-C. Novelli and J.-Y. Thibon, <a href="http://arXiv.org/
abs/math.CO/0605262">Commutative combinatorial Hopf algebras</a>
%H A001263 Vladimir Kostov and Boris Shapiro, <a href="http://arXiv.org/pdf/0804.1028">
Narayana numbers and Schur-Szego composition</a>
%H A001263 A. Laradji and A. Umar, <a href="http://www.cs.uwaterloo.ca/journals/
JIS/">Combinatorial Results for Semigroups of Order-Decreasing Partial
Transformations</a>, Journal of Integer Sequences, Vol. 7 (2004),
Article 04.3.8.
%H A001263 P. A. MacMahon, <a href="http://www.hti.umich.edu/cgi/t/text/text-idx?c=umhistmath;
idno=ABU9009">Combinatory analysis</a>.
%H A001263 D. Merlini, R. Sprugnoli and M. C. Verri, <a href="http://www.dsi.unifi.it/
~merlini/fun01.ps">Waiting patterns for a printer</a>, FUN with algorithm'01,
Isola d'Elba, 2001.
%H A001263 A. Micheli and D. Rossin, <a href="http://arXiv.org/abs/math.CO/0506538">
Edit distance between unlabeled ordered trees</a>
%H A001263 J.-C. Novelli and J.-Y. Thibon, <a href="http://arXiv.org/abs/math.CO/
0605061">Polynomial realizations of some trialgebras</a>, Proc. Formal
Power Series and Algebraic Combinatorics 2006 (San-Diego, 2006)
%H A001263 J.-C. Novelli and J.-Y. Thibon, <a href="http://journals.impan.gov.pl/
fm/Inf/193-3-1.html">Hopf algebras and dendriform structures arising
from parking functions</a>, Fundamenta Mathematicae 193 (2007), pp.
189-241, arXiv:<a href="http://arxiv.org/abs/math/0511200">0511200</
a>.
%H A001263 R. A. Sulanke, <a href="http://math.boisestate.edu/~sulanke/recentpapindex.html">
Moments, Narayana numbers and the cut and paste for lattice paths</
a>
%H A001263 R. A. Sulanke, <a href="http://math.boisestate.edu/~sulanke/recentpapindex.html">
Three-dimensional Narayana and Schr\"oder numbers</a>
%H A001263 L. K. Williams, <a href="http://arXiv.org/abs/math.CO/0307271">Enumeration
of totally positive Grassmann cells</a>
%H A001263 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
Publications/books.html">Analytic Combinatorics</a>, 2009; see page
182
%F A001263 a(n, k) = C(n-1, k-1)C(n, k-1)/k for k!=0; a(n, 0)=0.
%F A001263 Triangle equals [0, 1, 0, 1, 0, 1, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0,
...] where DELTA is Deleham's operator defined in A084938.
%F A001263 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 (zabrocki(AT)mathstat.yorku.ca),
Aug 26 2004
%F A001263 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 (Gerald.McGarvey(AT)comcast.net),
Feb 24 2005
%F A001263 T(n, k) = binomial(n-1, k-1)^2 - binomial(n-1, k)bi(n-1, k-2). - David
Callan (callan(AT)stat.wisc.edu), Nov 02 2005
%F A001263 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 (Harris.Mitchell(AT)mgh.harvard.edu),
Jul 06 2006
%F A001263 G.f.: (1-x(1+y)-sqrt((1-x(1+y))^2-4yx^2))/(2x) = Sum_{n>0, k>0} a(n,
k) x^n y^k.
%F A001263 Contribution from Peter Bala (pbala(AT)toucansurf.com), Oct 22 2008:
(Start)
%F A001263 Relation with Jacobi polynomials of parameter (1,1):
%F A001263 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 non-positive, 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.
%F A001263 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.
%F A001263 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).
%F A001263 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.
%F A001263 (End)
%e A001263 1; 1,1; 1,3,1; 1,6,6,1; 1,10,20,10,1; 1,15,50,50,15,1; ...
%e A001263 a(6,1)=a(6,6)=1, a(6,2)=a(6,5)=15, a(6,3)=a(6,4)=50.
%p A001263 a := (n,k)->binomial(n-1,k-1)*binomial(n,k-1)/k;
%p A001263 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:
%t A001263 a[n_, k_] := If[k==0, 0, Binomial[n-1, k-1]Binomial[n, k-1]/k]
%o A001263 (PARI) a(n,k)=if(k==0,0,binomial(n-1,k-1)*binomial(n,k-1)/k)
%Y A001263 Cf. A000372, A002083, A056932, A056939, A056940, A056941.
%Y A001263 Cf. A065329, A073345.
%Y A001263 Columns give A000217, A002415, A006542, A006857.
%Y A001263 Row sums gives A000108 Catalan numbers, n>0.
%Y A001263 Cf. A084938.
%Y A001263 Central column = A000891, (2n)!(2n+1)! / (n! (n+1)!)^2 - Zerinvary Lajos
(zerinvarylajos(AT)yahoo.com), Oct 29 2006.
%Y A001263 Cf. A090181 (triangle with additional leading (trivial) row and column).
%Y A001263 A008459, A145596, A145597, A145598, A145599. [From Peter Bala (pbala(AT)toucansurf.com),
Oct 22 2008]
%Y A001263 A008459 (h-vectors type B associahedra), A033282 (f-vectors type A associahedra),
A145903 (h-vectors type D associahedra), A145904 (Hilbert transform).
[From Peter Bala (pbala(AT)toucansurf.com), Oct 27 2008]
%Y A001263 Sequence in context: A114176 A056241 A162745 this_sequence A162747 A107105
A088925
%Y A001263 Adjacent sequences: A001260 A001261 A001262 this_sequence A001264 A001265
A001266
%K A001263 nonn,easy,tabl,nice
%O A001263 1,5
%A A001263 N. J. A. Sloane (njas(AT)research.att.com).
%E A001263 Updated reference Charles R Greathouse IV (charles.greathouse(AT)case.edu),
Oct 28 2009
|
