Do you want to publish a course? Click here

A New Bijection Between Forests and Parking Functions

135   0   0.0 ( 0 )
 Added by Heesung Shin
 Publication date 2008
  fields
and research's language is English
 Authors Heesung Shin




Ask ChatGPT about the research

In 1980, G. Kreweras gave a recursive bijection between forests and parking functions. In this paper we construct a nonrecursive bijection from forests onto parking functions, which answers a question raised by R. Stanley. As a by-product, we obtain a bijective proof of Gessel and Seos formula for lucky statistic on parking functions.



rate research

Read More

For each skew shape we define a nonhomogeneous symmetric function, generalizing a construction of Pak and Postnikov. In two special cases, we show that the coefficients of this function when expanded in the complete homogeneous basis are given in terms of the (reduced) type of $k$-divisible noncrossing partitions. Our work extends Haimans notion of a parking function symmetric function.
The classical parking functions, counted by the Cayley number (n+1)^(n-1), carry a natural permutation representation of the symmetric group S_n in which the number of orbits is the nth Catalan number. In this paper, we will generalize this setup to rational parking functions indexed by a pair (a,b) of coprime positive integers. We show that these parking functions, which are counted by b^(a-1), carry a permutation representation of S_a in which the number of orbits is a rational Catalan number. We compute the Frobenius characteristic of the S_a-module of (a,b)-parking functions. Next we propose a combinatorial formula for a q-analogue of the rational Catalan numbers and relate this formula to a new combinatorial model for q-binomial coefficients. Finally, we discuss q,t-analogues of rational Catalan numbers and parking functions (generalizing the shuffle conjecture for the classical case) and present several conjectures.
127 - Yidong Sun 2008
In this short note, we first present a simple bijection between binary trees and colored ternary trees and then derive a new identity related to generalized Catalan numbers.
We study Schroder paths drawn in a (m,n) rectangle, for any positive integers m and n. We get explicit enumeration formulas, closely linked to those for the corresponding (m,n)-Dyck paths. Moreover we study a Schroder version of (m,n)-parking functions, and associated (q,t)-analogs.
The emph{Shi arrangement} is the set of all hyperplanes in $mathbb R^n$ of the form $x_j - x_k = 0$ or $1$ for $1 le j < k le n$. Shi observed in 1986 that the number of regions (i.e., connected components of the complement) of this arrangement is $(n+1)^{n-1}$. An unrelated combinatorial concept is that of a emph{parking function}, i.e., a sequence $(x_1, x_2, ..., x_n)$ of positive integers that, when rearranged from smallest to largest, satisfies $x_k le k$. (There is an illustrative reason for the term emph{parking function}.) It turns out that the number of parking functions of length $n$ also equals $(n+1)^{n-1}$, a result due to Konheim and Weiss from 1966. A natural problem consists of finding a bijection between the $n$-dimensional Shi arragnement and the parking functions of length $n$. Stanley and Pak (1996) and Athanasiadis and Linusson 1999) gave such (quite different) bijections. We will shed new light on the former bijection by taking a scenic route through certain mixed graphs.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا