Search

Starting from the two-species partially asymmetric simple exclusion process, we study a subclass of signed permutations, the partially signed permutations, using the combinatorics of Laguerre histories. From this physical and bijective point of view, we obtain a natural descent statistic on partially signed permutations; as well as partially signed permutations patterns., Comment: 22 pages, 9 figures

Motivated by the direct-sum-decomposition of the $r^{\text{th}}$ tensor power of the defining representation of the special orthogonal group $\mathrm{SO}(2k + 1)$, we present a bijection between vacillating tableaux and pairs consisting of a standard Young tableau and an orthogonal Littlewood-Richardson tableau for $\mathrm{SO}(3)$.Our bijection preserves a suitably defined descent set. Using it we determine the quasi-symmetric expansion of the Frobenius characters of the isotypic components.On the combinatorial side we obtain a bijection between Riordan paths and standard Young tableaux with 3 rows, all of even length or all of odd length.

Recently, Dokos et al. conjectured that for all $k, m\geq 1$, the patterns $ 12\ldots k(k+m+1)\ldots (k+2)(k+1) $ and $(m+1)(m+2)\ldots (k+m+1)m\ldots 21$ are $maj$-Wilf-equivalent. In this paper, we confirm this conjecture for all $k\geq 1$ and $m=1$. In fact, we construct a descent set preserving bijection between $ 12\ldots k (k-1) $-avoiding permutations and $23\ldots k1$-avoiding permutations for all $k\geq 3$. As a corollary, our bijection enables us to settle a conjecture of Gowravaram and Jagadeesan concerning the Wilf-equivalence for permutations with given descent sets.

We investigate pattern avoidance in alternating permutations and an alternating analogue of Young diagrams. In particular, using an extension of Babson and West's notion of shape- Wilf equivalence described in our recent paper (with N. Gowravaram ), we generalize results of Backelin , West, and Xin and Ouchterlony to alternating permutations. Unlike Ouchterlony and Bona 's bijections , our bijections are not the restrictions of Backelin , West, and Xin's bijections to alternating permutations. This paper is the second of a two-paper series presenting the work of Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux (with N. Gowravaram , arXiv: 1301. 6796v1 ). The first paper in the series is Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux (with N. Gowravaram , Electronic Journal of Combinatorics 20(4):# P17 , 2013).

Based on the classic bijective algorithm for trees due to Chen, we present a decomposition algorithm for noncrossing trees. This leads to a combinatorial interpretation of a formula on noncrossing trees of size $n$ with $k$ descents. We also derive the formula for noncrossing trees of size $n$ with $k$ descents and $i$ leaves, which is a refinement of the formula given by Flajolet and Noy. As an application of our algorithm, we answer a question proposed by Hough, which asks for a bijection between two classes of noncrossing trees with a given number of descents.

In this paper we provide a bijective proof of a theorem of Garsia and Gessel describing the generating function of the major index over the set of all permutations of $[n]=\{1,...,n\}$ which are shuffles of given disjoint ordered sequences $\pi_1,...,\pi_k$ whose union is $[n]$. The proof is based on a result (an "insertion lemma") of Haglund, Loehr, and Remmel which describes the change in major index resulting from the insertion of a given new element in any place in a given permutation. Using this lemma we prove the theorem by establishing a bijection between shuffles of ordered sequences and a certain set of partitions. A special case of Garsia and Gessel's theorem provides a proof of the equidistribution of major index and inversion number over inverse descent classes, a result first proved bijectively by Foata and Schutzenberger in 1978. We provide, based on the method of our first proof, another bijective proof of this result.

We show that the major codes and inversion codes are equidistributed over a set of permutations with prescribed descent indices and right-maximal records.

A large number of generating functions for permutation statistics can be obtained by applying homomorphisms to simple symmetric function identities. In particular, a large number of generating functions involving the number of descents of a permutation $\sigma$, $des(\sigma)$, arise in this way. For any given finite set $S$ of positive integers, we develop a method to produce similar generating functions for the set of permutations of the symmetric group $S_n$ whose descent set contains $S$. Our method will be to apply certain homomorphisms to symmetric function identities involving ribbon Schur functions.

Given sets $X$ and $Y$ of positive integers and a permutation $\sigma = \sigma_1 \sigma_2 \cdots \sigma_n \in S_n$, an $(X,Y)$-descent of $\sigma$ is a descent pair $\sigma_i > \sigma_{i+1}$ whose "top" $\sigma_i$ is in $X$ and whose "bottom" $\sigma_{i+1}$ is in $Y$. Recently Hall and Remmel proved two formulas for the number $P_{n,s}^{X,Y}$ of $\sigma \in S_n$ with $s$ $(X,Y)$-descents, which generalized Liese's results in [1]. We define a new statistic ${\rm stat}_{X,Y}(\sigma)$ on permutations $\sigma$ and define $P_{n,s}^{X,Y}(q)$ to be the sum of $q^{{\rm stat}_{X,Y}(\sigma)}$ over all $\sigma \in S_n$ with $s$ $(X,Y)$-descents. We then show that there are natural $q$-analogues of the Hall-Remmel formulas for $P_{n,s}^{X,Y}(q)$.

There is a well-known combinatorial definition, based on ordered set partitions, of the semigroup of faces of the braid arrangement. We generalize this definition to obtain a semigroup Sigma_n^G associated with G wr S_n, the wreath product of the symmetric group S_n with an arbitrary group G. Techniques of Bidigare and Brown are adapted to construct an anti-homomorphism from the S_n-invariant subalgebra of the semigroup algebra of Sigma_n^G into the group algebra of G wr S_n. The generalized descent algebras of Mantaci and Reutenauer are obtained as homomorphic images when G is abelian., 6 pages, added a reference and updated the Introduction

We consider in this work the enumeration of involutions by descent sets, and based on that, by descent numbers. Formulas of the number of involutions with a prescribed descent set, with a prescribed descent number and Frobenius-type formulas are given.

The generating function for descents in noncrossing trees is found. A bijection shows combinatorially why the descent generating function with descents set equal to $2$ is the generating function for connected noncrossing graphs.

Garsia and Remmel (JCT. A 41 (1986), 246-275) used rook configurations to give a combinatorial interpretation to the $q$-analogue of a formula of Frobenius relating the Stirling numbers of the second kind to the Eulerian polynomials. Later, Remmel and Wachs defined generalized $p,q$-Stirling numbers of the first and second kind in terms of rook placements. Additionally, they extended their definition to give a $p,q$-analogue of rook numbers for arbitrary Ferrers boards. In this paper, we use Remmel and Wach's definition and an extension of Garsia and Remmel's proof to give a combinatorial interpretation to a $p,q$-analogue of a formula of Frobenius relating the $p,q$-Stirling numbers of the second kind to the trivariate distribution of the descent number, major index, and comajor index over $S_n$. We further define a $p,q$-analogue of the hit numbers, and show analytically that for Ferrers boards, the $p,q$-hit numbers are polynomials in $(p,q)$ with nonnegative coefficients.

The number of words $w = w_1\cdots w_n$, $1 \leq w_i \leq k$, for which there are $1 \leq i_1 < \cdots < i_{\ell} \leq n$ and $w_{i_1} > \cdots > w_{i_{\ell}}$, is given, by the Schensted-Knuth correspondence, in terms of standard and semi-standard Young tableaux. When $n \to \infty$, the asymptotics of the number of such words is calculated.