We apply the concept of parking functions to functional digraphs of mappings by considering the nodes as parking spaces and the directed edges as one-way streets: Each driver has a preferred parking space and starting...
详细信息
We apply the concept of parking functions to functional digraphs of mappings by considering the nodes as parking spaces and the directed edges as one-way streets: Each driver has a preferred parking space and starting with this node he follows the edges in the graph until he either finds a free parking space or all reachable parking spaces are occupied. If all drivers are successful we speak of a parking function for the mapping. We transfer well-known characterizations of parking functions to mappings. Via analytic combinatorics techniques we study the total number M-n,M-m of mapping parking functions, i.e., the number of pairs (f, s) with f : [n] -> [n] an n-mapping and s is an element of [n](m) a parking function for f with m drivers, yielding exact and asymptotic results. Moreover, we describe the phase change behaviour appearing at m = n/2 for M-n,M-m and relate it to previously studied combinatorial contexts. (C) 2016 Elsevier Inc. All rights reserved.
We introduce several associative algebras and families of vector spaces associated to these algebras. Using lattice vertex operators, we obtain dimension and character formulae for these spaces. In particular, we defi...
详细信息
We introduce several associative algebras and families of vector spaces associated to these algebras. Using lattice vertex operators, we obtain dimension and character formulae for these spaces. In particular, we define a family of representations of symmetric groups which turn out to be isomorphic to parking function modules. We also construct families of vector spaces whose dimensions are Catalan numbers and Fuss-Catalan numbers respectively. Conjecturally, these spaces are related to spaces of global sections of vector bundles on (zero fibres of) Hilbert schemes and representations of rational Cherednik algebras.
We show that the notion of parkization of a word, a variant of the classical standardization, allows us to introduce an internal product on the Hopf algebra of parking functions. Its Catalan subalgebra is stable under...
详细信息
We show that the notion of parkization of a word, a variant of the classical standardization, allows us to introduce an internal product on the Hopf algebra of parking functions. Its Catalan subalgebra is stable under this operation and contains the descent algebra as a left ideal.
In [A conjectured combinatorial formula for the Hilbert series for diagonal harmonics, in: Proceedings of FPSAC 2002 Conference, Melbourne, Australia, Discrete Math., in press] Haglund, Haiman, and the present author ...
详细信息
In [A conjectured combinatorial formula for the Hilbert series for diagonal harmonics, in: Proceedings of FPSAC 2002 Conference, Melbourne, Australia, Discrete Math., in press] Haglund, Haiman, and the present author conjectured a combinatorial formula CH(n)(q, t) for the Hilbert series of diagonal harmonics as a weighted sum of parking functions. Another equivalent combinatorial formula was proposed by the present author in [Multivariate analogues of Catalan numbers, parking functions, and their extensions, UCSD doctoral thesis, June 2003]. These formulas involve three statistics on parking functions called area, dinv, and pmaj. In this article, we use the pmaj statistic to solve several combinatorial problems posed in [A conjectured combinatorial formula for the Hilbert series for diagonal harmonics, in: Proceedings of FPSAC 2002 Conference, Melbourne, Australia, Discrete Math., in press]. In particular, we derive a recursion satisfied by the combinatorial Hilbert series and show that q(n(n - 1)/2) CH(n)(1/q, q) = [n + 1](q)(n-1). (C) 2004 Elsevier Inc. All rights reserved.
parking functions are central in many aspects of combinatorics. We define in this communication a generalization of parking functions which we call (p(1),..., p(k))-parking functions. We give a characterization of the...
详细信息
parking functions are central in many aspects of combinatorics. We define in this communication a generalization of parking functions which we call (p(1),..., p(k))-parking functions. We give a characterization of them in terms of parking functions and we show that they can be interpreted as recurrent configurations in the sandpile model for some graphs. We also establish a correspondence with a Lukasiewicz language, which enables to enumerate (p(1),..., p(k))-parking functions as well as increasing ones.
A parking function can be thought of as a sequence of n drivers, each with a preferred parking space, wanting to park along a one-way street with n parking spaces. Each driver checks her preferred parking space and, i...
详细信息
A parking function can be thought of as a sequence of n drivers, each with a preferred parking space, wanting to park along a one-way street with n parking spaces. Each driver checks her preferred parking space and, if it is occupied, parks in the first available space afterwards. One may consider how the enumeration of these sequences changes if the “parking lot” is made more complex, a question whose solution this dissertation lays the foundations for and answers in the case of certain families of graphs. We begin by generalizing the underlying parking lot to a general digraph and give several equivalent characterizations. We then start by building on recent work in the case that the parking lot is a tree with edges directed towards a root. We generalize the notions of “prime” and “increasing” parking functions to give enumerative results concerning both. Additionally, we consider one of the numerous statistics on classical parking functions, the number of drivers who park in their desired spot, and show that it connects these tree parking functions that are prime and those that are both increasing and prime. Finally, we consider miscellaneous results on various families of trees and enumerate a generalization of Dyck paths in the process
We investigate a particular symmetry in labeled trees first discovered by Gessel, which can be stated as follows: In the set of rooted labeled trees on n + 1 vertices rooted at the smallest vertex, the number of trees...
详细信息
We investigate a particular symmetry in labeled trees first discovered by Gessel, which can be stated as follows: In the set of rooted labeled trees on n + 1 vertices rooted at the smallest vertex, the number of trees with a descents and b + 1 leaves equals the number of trees with b descents and a + 1 leaves. We present two new ways to prove the symmetry resulting from decompositions of trees, which lead to three different bijections from trees to trees in which leaves and descents are swapped. We also interpret the symmetry in terms of parking functions: the number of parking functions on [n] with a descents and b unfavorable spaces (defined in this paper) equals the number of parking functions on [n] with b descents and a unfavorable spaces. We conclude with a generalization of these results to binary trees. (C) 2002 Elsevier Science B.V. All rights reserved.
We consider the inversion enumerator I(n)(q), which counts labeled trees or, equivalently, parking functions. This polynomial has a natural extension to generalized parking functions. Substituting q = -1 into this gen...
详细信息
We consider the inversion enumerator I(n)(q), which counts labeled trees or, equivalently, parking functions. This polynomial has a natural extension to generalized parking functions. Substituting q = -1 into this generalized polynomial produces the number of permutations with a certain descent set. In the classical case, this result implies the formula I(n) (-1) = E(n). the number of alternating permutations. We give a combinatorial proof of these formulas based on the involution principle. We also give a geometric interpretation of these identities in terms of volumes of generalized chain polytopes of ribbon posets. The volume of such a polytope is given by a SLIM over generalized parking functions, which is similar to an expression for the volume of the parking function polytope of Pitman and Stanley. (C) 2009 Elsevier Inc. All rights reserved.
In this paper, we give a new expression for the Tutte polynomial of a general connected graph G in terms of statistics of C,parking functions. In particular, given a G-parking function f, let cb(G) (f) be the number o...
详细信息
In this paper, we give a new expression for the Tutte polynomial of a general connected graph G in terms of statistics of C,parking functions. In particular, given a G-parking function f, let cb(G) (f) be the number of critical-bridge vertices of f and denote w(G)(f) = vertical bar E(G)vertical bar - vertical bar V(G)vertical bar - E-v is an element of v(G) f (v). We prove that T-G(x, y) = Sigma(XcbG(f))(f is an element of PG), where P-G is the set of G-parking functions. Our proof avoids any use of spanning trees and is independent of bijections between the set of G-parking functions and the set of spanning trees. (c) 2009 Elsevier Inc. All rights reserved.
Since their introduction by Konheim and Weiss, parking functions have evolvedinto objects of surprising combinatorial complexity for their simple definitions. First,we introduce these structures, give a brief history ...
详细信息
Since their introduction by Konheim and Weiss, parking functions have evolvedinto objects of surprising combinatorial complexity for their simple definitions. First,we introduce these structures, give a brief history of their development and give afew basic theorems about their structure. Then we examine the internal structures ofparking functions, focusing on the distribution of descents and inversions in parkingfunctions. We develop a generalization to the Catalan numbers in order to countsubsets of the parking functions. Later, we introduce a generalization to parkingfunctions in the form of k-blocked parking functions, and examine their internalstructure. Finally, we expand on the extension to the Catalan numbers, exhibitingexamples to explore its internal structure. These results continue the exploration ofthe deep structures of parking functions and their relationship to other combinatorialobjects
暂无评论