195 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
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
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}
Hilbert series of the Grassmannian and -Narayana numbers
No full textsummary:We compute the Hilbert series of the complex Grassmannian using invariant theoretic methods. This is made possible by showing that the denominator of the -Hilbert series is a Vandermonde-like determinant. We show that the -polynomial of the Grassmannian coincides with the -Narayana polynomial. A simplified formula for the -polynomial of Schubert varieties is given. Finally, we use a generalized hypergeometric Euler transform to find simplified formulae for the -Narayana numbers, i.e.~the -polynomial of the Grassmannian
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)}
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
QPACE - a QCD parallel computer based on cell processors
No full textQPACE is a novel parallel computer which has been developed to be primarily
used for lattice QCD simulations. The compute power is provided by the IBM
PowerXCell 8i processor, an enhanced version of the Cell processor that is used in the Playstation 3. The QPACE nodes are interconnected by a custom,
application optimized 3-dimensional torus network implemented on an FPGA. To achieve the very high packaging density of 26 TFlops per rack a new water
cooling concept has been developed and successfully realized. In this paper we give an overview of the architecture and highlight some important technical details of the system. Furthermore, we provide initial performance results and report on the installation of 8 QPACE racks providing an aggregate peak performance of 200 TFlops
- …
