24 research outputs found
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
On the maximum number of cliques in a graph embedded in a surface
No full textThis paper studies the following question: given a surface σ and an integer n, what is the maximum number of cliques in an n-vertex graph embeddable in σ? We characterise the extremal graphs for this question, and prove that the answer is between 8(n-ω)+2 ω and 8n+5/2 2 ω+o(2 ω), where ω is the maximum integer such that the complete graph K ω embeds in σ. For the surfaces S 0, S 1, S 2, N 1, N 2, N 3 and N 4 we establish an exact answer. © 2011 David Wood.SCOPUS: ar.jinfo:eu-repo/semantics/publishe
Networks and Poisson line patterns : fluctuation asymptotics
No full textIn [1] it was shown how to construct networks connecting arbitrary configurations
xn of n cities in a square of area n which for example (i) involve only εn more total
network length than the Euclidean Steiner tree connecting all n cities, and yet (ii)
establish a network connection length between two randomly chosen cities which
is on average only O(log n) more than average Euclidean connection length [1,
Theorem 3, version (b)]. Moreover, under a certain quantitative equidistribution
condition on the city locations xn (which can be phrased either analytically or in
terms of a truncated Wasserstein coupling between a randomly chosen city and the
uniform distribution on the square), a complementary result shows that for O(n)
total connection length the average network connection length must have an excess
over the average Euclidean connection length of at least Ω(√log n) [1, Theorem
5]. The methods of proof involve stochastic geometry: in the case of the lower
bound [1, Theorem 5] the idea is to associate the uniform choice of two cities with
approximately uniform random lines, and then to use simple ideas from stereology.
In the case of the upper bound [1, Theorem 3] one augments the Euclidean Steiner
tree by a sparse Poisson line process, to obtain good long-distance communication,
and adds an additional relatively infinitesimal amount of additional connectivity,
to ensure efficient passage from Steiner tree to line process network
