Crossings of signed permutations and $q$-Eulerian numbers of type $B$

In this paper we want to study combinatorics of the type B per- mutations and in particular the join statistics crossings, excedances and the number of negative entries. We generalize most of the results known for type A (i.e. zero negative entries) and use a mix of enumerative, algebraic and bijective techniques. This work has been motivated by permutation tableaux of type B introduced by Lam and Williams, and natural statistics that can be read on these tableaux. We mostly use (pignose) diagrams and labelled Motzkin paths for the combinatorial interpretations of our results.

Related papers:

title: Enumeration of totally positive Grassmann cells
abstract: Postnikov (Webs in totally positive Grassmann cells, in preparation) has given a combinatorially explicit cell decomposition of the totally nonnegative part of a Grassmannian, denoted Grk,n+, and showed that this set of cells is isomorphic as a graded poset to many other interesting graded posets. The main result of our work is an explicit generating function which enumerates the cells in Grk,n+ according to their dimension. As a corollary, we give a new proof that the Euler characteristic of Grk,n+ is 1. Additionally, we use our result to produce a new q-analog of the Eulerian numbers, which interpolates between the Eulerian numbers, the Narayana numbers, and the binomial coefficients.

title: Total positivity for cominuscule Grassmannians
abstract: In this paper we explore the combinatorics of the nonneg- ative part (G/P )≥0 of a cominuscule Grassmannian. For each such Grassmannian we define Γ — certain fillings of generalized Young diagrams which are in bijection with the cells of (G/P )≥0 .I n the classical cases, we describe Γ explicitly in terms of pattern avoidance. We also define a game on diagrams, by which one can reduce an arbitrary diagram to a Γ We give enumerative results and relate our Γ to other combinatorial objects. Surprisingly, the totally nonnegative cells in the open Schubert cell of the odd and even orthogonal Grassmannians are (essentially) in bijection with preference functions and atomic preference functions respectively.

title: The Matrix Ansatz, orthogonal polynomials, and permutations
abstract: In this paper we outline a Matrix Ansatz approach to some problems of combinatorial enumeration. The idea is that many interesting quantities can be expressed in terms of products of matrices, where the matrices obey certain relations. We illustrate this approach with applications to moments of orthogonal polynomials, permutations, signed permutations, and tableaux.

title: Descent Numbers and Major Indices for the Hyperoctahedral Group
abstract: We introduce and study three new statistics on the hyperoctahedral group B"n and show that they give two generalizations of Carlitz's identity for the descent number and major index over S"n. This answers a question posed by Foata.

title: Matrix Ansatz, lattice paths and rook placements
abstract: We give two combinatorial interpretations of the Matrix Ansatz of the PASEP in terms of lattice paths and rook placements. This gives two (mostly) combinatorial proofs of a new enumeration formula for the partition function of the PASEP. Besides other interpretations, this formula gives the generating function for permutations of a given size with respect to the number of ascents and occurrences of the pattern $13-2$, the generating function according to weak exceedances and crossings, and the $n^{\mathrm{th}}$ moment of certain $q$-Laguerre polynomials.

title: Rook placements in Young diagrams and permutation enumeration
abstract: Given two operators [email protected]? and [email protected]? subject to the relation [email protected][email protected][email protected][email protected]?=p, and a word w in [email protected]? and [email protected]?, the rewriting of w in normal form is combinatorially described by rook placements in Young diagrams. We give enumerative results about these rook placements, particularly in the case where p=(1-q)/q^2. This case naturally arises in the context of the PASEP, a random process whose partition function and stationary distribution can be derived using two operators D and E subject to the relation DE-qED=D+E (matrix Ansatz). Using the link obtained by Corteel and Williams between the PASEP, permutation tableaux and permutations, we prove a conjecture of Corteel and Rubey about permutation enumeration. This result gives the generating function for permutations of given size with respect to the number of ascents and occurrences of the pattern 13-2, this is also the moments of some q-Laguerre orthogonal polynomials.

title: Combinatorics of Coxeter Groups
abstract: I.- The basics.- Bruhat order.- Weak order and reduced words.- Roots, games, and automata.- II.- Kazhdan-Lusztig and R-polynomials.- Kazhdan-Lusztig representations.- Enumeration.- Combinatorial Descriptions.

title: Combinatorics on permutation tableaux of type A and type B
abstract: We give two bijective proofs of a result of Corteel and Nadeau. We find a generating function related to unrestricted columns of permutation tableaux. As a consequence, we obtain a sign-imbalance formula for permutation tableaux. We extend the first bijection of Corteel and Nadeau between permutations and permutation tableaux to type B objects. Using this type B bijection, we generalize a result of Lam and Williams. We prove that the bijection of Corteel and Nadeau and our type B bijection can be expressed as zigzag maps on the alternative representation.

title: Bijections for permutation tableaux
abstract: In this paper we propose two bijections between permutation tableaux and permutations. These bijections show how natural statistics on the tableaux are equidistributed to classical statistics on permutations: descents, RL-minima and pattern enumerations. We then use those bijections to define subclasses of permutation tableaux that are in bijection with set partitions.

title: Permutation tableaux and permutation patterns
abstract: In this paper we introduce and study a class of tableaux which we call permutation tableaux; these tableaux are naturally in bijection with permutations, and they are a distinguished subset of the -diagrams of Alex Postnikov [A. Postnikov, Webs in totally positive Grassmann cells, in preparation; L. Williams, Enumeration of totally positive Grassmann cells,  (2005) 319-342]. The structure of these tableaux is in some ways more transparent than the structure of permutations; therefore we believe that permutation tableaux will be useful in furthering the understanding of permutations. We give two bijections from permutation tableaux to permutations. The first bijection carries tableaux statistics to permutation statistics based on relative sizes of pairs of letters in a permutation and their places. We call these statistics weak excedance statistics because of their close relation to weak excedances. The second bijection carries tableaux statistics (via the weak excedance statistics) to statistics based on generalized permutation patterns. We then give enumerative applications of these bijections. One nice consequence of these results is that the polynomial enumerating permutation tableaux according to their content generalizes both Carlitz'q-analog of the Eulerian numbers [L. Carlitz, q-Bernoulli and Eulerian numbers,  (1954) 332-350] and the more recent q-analog of the Eulerian numbers found in [L. Williams, Enumeration of totally positive Grassmann cells,  (2005) 319-342]. We conclude our paper with a list of open problems, as well as remarks on progress on these problems which has been made by A. Burstein, S. Corteel, N. Eriksen, A. Reifegerste, and X. Viennot.

title: Touchard–Riordan formulas, T-fractions, and Jacobi’s triple product identity
abstract: Touchard–Riordan-like formulas are certain expressions appearing in enumeration problems and as moments of orthogonal polynomials. We begin this article with a new combinatorial approach to prove such formulas, related to integer partitions. This gives a new perspective on the original result of Touchard and Riordan. But the main goal is to give a combinatorial proof of a Touchard–Riordan-like formula for q-secant numbers discovered by the first author. An interesting limit case of these objects can be directly interpreted in terms of partitions, so that we obtain a connection between the formula for q-secant numbers, and a particular case of Jacobi’s triple product identity.Building on this particular case, we obtain a “finite version” of the triple product identity. It is in the form of a finite sum which is given a combinatorial meaning, so that the triple product identity can be obtained by taking the limit. Here the proof is non-combinatorial and relies on a functional equation satisfied by a T-fraction. Then from this result on the triple product identity, we derive a whole new family of Touchard–Riordan-like formulas whose combinatorics is not yet understood. Eventually, we prove a Touchard–Riordan-like formula for a q-analog of Genocchi numbers, which is related with Jacobi’s identity for (q;q)3 rather than the triple product identity.

title: Signed words and permutations, V; a sextuple distribution
abstract: We calculate the distribution of the sextuple statistic over the hyperoctahedral group Bn that involves the flag-excedance and flag-descent numbers “fexc” and “fdes,” the flag-major index “fmaj,” the positive and negative fixed point numbers “
$\mathop{\rm fix}\nolimits ^{+}$
” and “
$\mathop{\rm fix}\nolimits ^{-}$
” and the negative letter number “neg.” Several specializations are considered. In particular, the joint distribution for the pair 
$(\mathop{\rm fexc}\nolimits ,\mathop{\rm fdes}\nolimits )$ 
is explicitly derived.

title: Crossings, Motzkin paths and moments
abstract: Stanton and Zeng, and Kim, Stanton and Zeng introduced certain q-analogues of Laguerre and Charlier polynomials. The moments of these orthogonal polynomials have combinatorial models in terms of crossings in permutations and set partitions. The aim of this article is to prove simple formulae for the moments of the q-Laguerre and the q-Charlier polynomials, in the style of the Touchard-Riordan formula (which gives the moments of some q-Hermite polynomials, and also the distribution of crossings in matchings). Our method mainly consists of the enumeration of weighted Motzkin paths, which are naturally associated with the moments. Some steps are bijective, in particular, we describe a decomposition of paths which generalises a previous construction of Penaud for the case of the Touchard-Riordan formula. There are also some non-bijective steps using basic hypergeometric series, and continued fractions or, alternatively, functional equations.

title: Moments of Askey-Wilson polynomials
abstract: New formulas for the nth moment of the Askey-Wilson polynomials are given. These are derived using analytic techniques, and by considering three combinatorial models for the moments: Motzkin paths, matchings, and staircase tableaux. A related positivity theorem is given and another one is conjectured.

title: The symmetric and unimodal expansion of Eulerian polynomials via continued fractions
abstract: This paper was motivated by a conjecture of Branden [P. Branden, Actions on permutations and unimodality of descent polynomials,  (2008) 514-531] about the divisibility of the coefficients in an expansion of generalized Eulerian polynomials, which implies the symmetric and unimodal property of the Eulerian numbers. We show that such a formula with the conjectured property can be derived from the combinatorial theory of continued fractions. We also discuss an analogous expansion for the corresponding formula for derangements and prove a (p,q)-analogue of the fact that the (-1)-evaluation of the enumerator polynomials of permutations (resp. derangements) by the number of excedances gives rise to tangent numbers (resp. secant numbers). The (p,q)-analogue unifies and generalizes our recent results [H. Shin,  The q-tangent and q-secant numbers via continued fractions,  (2010) 1689-1705] and that of Josuat-Verges [M. Josuat-Verges, A q-enumeration of alternating permutations,  (2010) 1892-1906].

title: Non-crossing partitions for classical reflection groups
abstract: We introduce analogues of the lattice of non-crossing set partitions for the classical reflection groups of types B and D . The type B analogues (first considered by Montenegro in a different guise) turn out to be as well-behaved as the original non-crossing set partitions, and the type D analogues almost as well-behaved. In both cases, they are EL-labellable ranked lattices with symmetric chain decompositions (self-dual for type B ), whose rank-generating functions, zeta polynomials, rank-selected chain numbers have simple closed forms.

title: Symmetric Distribution of Crossings and Nestings in Permutations of Type B
abstract: This note contains two results on the distribution of crossing numbers and nesting numbers in permutations of type B. More precisely, we prove a $B_n$-analogue of the symmetric distribution of crossings and nestings of permutations due to Corteel [ 149–163] as well as the symmetric distribution of $k$-crossings and $k$-nestings of permutations due to Burrill et al. [DMTCS proc. AN (2010), 593–600].