183 research outputs found
The Narayana Distribution
No full text: The Narayana distribution is N n;k = 1 n i n k\Gamma1 ji n k j for 1 k n. This paper concerns structures counted by the Narayana distribution and bijective relationships between them. Here the statistic counting pairs of ascent steps on Catalan paths is prominently considered. Defining the n th Narayana polynomial as N n (w) = P 1kn N n;k w k , for n 1, the paper gives a combinatorial proof of a three term recurrence for these polynomials. It examines the Schroder numbers and the Kirkman numbers and establishes a sequence of bijections linking dissections of polygons to large Schroder paths. keywords: Catalan numbers, lattice paths, Schroder numbers AMS Subject Classification: 05A15 email: [email protected] Note to typesetter: the symbol L is a calligraphic L. It should be set as either a calligraphic L or a script L. Thanks. 1 2 1. introduction Using the steps V = (0; 1) and H = (1; 0), the set of Catalan paths, Cat n , is the set of lattice paths from (0; ..
STAIRCASE TILINGS AND k-CATALAN STRUCTURES
No full textMany interesting combinatorial objects are enumerated by the k-Catalan numbers, one possible generalization of the Catalan numbers. We will present a new combinatorial object that is enumerated by the k-Catalan numbers, staircase tilings. We give a bijection between staircase tilings and k-good paths, and between k-good paths and k-ary trees. In addition, we enumerate k-ary paths according to DD, UDU, and UU, and connect these statistics for k-ary paths to statistics for the staircase tilings. Using the given bijections, we enumerate statistics on the staircase tilings, and obtain connections with Catalan numbers for special values of k. The second part of the paper lists a sampling of other combinatorial structures that are enumerated by the k-Catalan numbers. Many of the proofs generalize from those for the Catalan structures that are being generalized, but we provide one proof that is not a straightforward generalization. We propose a web site repository for these structures, similar to those maintained by Richard Stanley for the Catalan numbers [33] and by Robert Sulanke for the Delannoy numbers [34]. On the website, we list additional combinatorial objects, together with hints on how to show that they are indeed enumerated by the k-Catalan numbers
Generalizing Narayana and Schröder numbers to higher dimensions
No full textLet C(d, n) denotethesetofd-dimensional lattice paths using the steps X1:= (1, 0,...,0), X2: = (0, 1,...,0),...,Xd: = (0, 0,...,1), running from (0, 0,...,0) to (n,n,...,n), and lying in {(x1,x2,...,xd):0 ≤ x1 ≤ x2 ≤... ≤ xd}. Onanypath P: = p1p2...pdn ∈C(d, n), define the statistics asc(P):=|{i: pipi+1 = XjXℓ,j < ℓ} | and des(P):=|{i: pipi+1 = XjXℓ,j> ℓ}|. Define the generalized Narayana number N(d, n, k) tocountthepathsinC(d, n) withasc(P)=k. We consider the derivation of a formula for N(d, n, k), implicit in MacMahon’s work. We examine other statistics for N(d, n, k) and show that the statistics asc and des −d +1 are equidistributed. We use Wegschaider’s algorithm, extending Sister Celine’s (Wilf-Zeilberger) method to multiple summation, to obtain recurrences for N(3,n,k). We introduce the generalized large Schröder numbers (2d−1 k N(d, n, k)2k)n≥1 to count constrained paths using step sets which include diagonal steps
Three dimensional Narayana and Schröder numbers
No full textAbstractConsider the 3-dimensional lattice paths running from (0,0,0) to (n,n,n), constrained to the region {(x,y,z):0⩽x⩽y⩽z}, and using various step sets. With C(3,n) denoting the set of constrained paths using the steps X≔(1,0,0), Y≔(0,1,0), and Z≔(0,0,1), we consider the statistic counting descents on a path P=p1p2…p3n∈C(3,n), i.e., des(P)≔|{i:pipi+1∈{YX,ZX,ZY},1⩽i⩽3n-1}|. A combinatorial cancellation argument and a result of MacMahon yield a formula for the 3-Narayana number, N(3,n,k)≔|{P∈C(3,n):des(P)=k+2}|. We define other statistics distributed by the 3-Narayana number and show that 4∑k2kN(3,n,k) yields the nth large 3-Schröder number which counts the constrained paths using the seven positive steps of the form (ξ1,ξ2,ξ3), ξi∈{0,1}
Stacked polytopes and tight triangulations of manifolds
No full textAbstractTightness of a triangulated manifold is a topological condition, roughly meaning that any simplex-wise linear embedding of the triangulation into Euclidean space is “as convex as possible”. It can thus be understood as a generalization of the concept of convexity. In even dimensions, super-neighborliness is known to be a purely combinatorial condition which implies the tightness of a triangulation. Here, we present other sufficient and purely combinatorial conditions which can be applied to the odd-dimensional case as well. One of the conditions is that all vertex links are stacked spheres, which implies that the triangulation is in Walkupʼs class K(d). We show that in any dimension d⩾4, tight-neighborly triangulations as defined by Lutz, Sulanke and Swartz are tight. Furthermore, triangulations with k-stacked vertex links and the centrally symmetric case are discussed
A Bijective Approach to the Area of Generalized Motzkin Paths
No full textAbstractFor fixed positive integer k, let En denote the set of lattice paths using the steps (1,1), (1,−1), and (k,0) and running from (0,0) to (n,0) while remaining strictly above the x-axis elsewhere. We first prove bijectively that the total area of the regions bounded by the paths of En and the x-axis satisfies a four-term recurrence depending only on k. We then give both a bijective and a generating function argument proving that the total area under the paths of En equals the total number of lattice points on the x-axis hit by the unrestricted paths running from (0,0) to (n−2,0) and using the same step set as above
Counting lattice chains and Delannoy paths in higher dimensions
No full textAbstractLattice chains and Delannoy paths represent two different ways to progress through a lattice. We use elementary combinatorial arguments to derive new expressions for the number of chains and the number of Delannoy paths in a lattice of arbitrary finite dimension. Specifically, fix nonnegative integers n1,…,nd, and let L denote the lattice of points (a1,…,ad)∈Zd that satisfy 0≤ai≤ni for 1≤i≤d. We prove that the number of chains in L is given by 2nd+1∑k=1kmax′∑i=1k(−1)i+kk−1i−1nd+k−1nd∏j=1d−1nj+i−1nj, where kmax′=n1+⋯+nd−1+1. We also show that the number of Delannoy paths in L equals ∑k=1kmax′∑i=1k(−1)i+k(k−1i−1)(nd+k−1nd)∏j=1d−1(nd+i−1nj). Setting ni=n (for all i) in these expressions yields a new proof of a recent result of Duchi and Sulanke [9] relating the total number of chains to the central Delannoy numbers. We also give a novel derivation of the generating functions for these numbers in arbitrary dimension
QPACE: Quantum Chromodynamics Parallel Computing on the Cell Broadband Engine
No full textApplication-driven computers for Lattice Gauge Theory simulations have often been based on system-on-chip designs, but the development costs can be prohibitive for academic project budgets. An alternative approach uses compute nodes based on a commercial processor tightly coupled to a custom-designed network processor. Preliminary analysis shows that this solution offers good performance, but it also entails several challenges, including those arising from the processor's multicore structure and from implementing the network processor on a field-programmable gate array
Narayana numbers and Schur-Szegö composition
No full textIn 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,N-k = 1/nC(n)(k-1)C(n)(k) where C-j(i) stands for the usual binomial coefficient, i.e. C-j(i) = j!/i!(j-i)!. They count Dyck paths of length n and with exactly k peaks, see e.g. [R.A. Sulanke, The Narayana distribution, in: Lattice Path Combinatorics and Applications (Vienna, 1998), J. Statist. Plann. Inference 101 (1-2) (2002) 311-326 (special issue)] and they appeared recently in a number of different combinatorial situations, see for e.g. [. Doslic, D. Syrtan, D. Veljan, Enumerative aspects of secondary structures, Discrete Math. 285 (2004) 67-82; A. Sapounakis, I. Tasoulas, P. Tsikouras, Counting strings in Dyck paths, Discrete Math. 307 (2007) 2909-2924; F. Yano, H. Yoshida, Some set partitions statistics in non-crossing partitions and generating functions, Discrete Math. 307 (2007) 3147-3160]. Strangely enough Narayana polynomials also occur as limits as n -> infinity 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. We present below a relation between Narayana polynomials and the classical Gegenbauer polynomials which implies, in particular, an explicit formula for the density and the distribution function of the asymptotic root-counting measure of the polynomial sequence {N-n(x)}
- …
