Weighted inversion numbers,restricted growth functions,and standard young tableaux

We give a family of weighted inversion numbers with the same generating function which interpolate between the inversion number and MacMahon's major index. Foata's bijection is obtained in a natural way from a simple involution. An alternative proof uses q-difference equations which yield some new results. We obtain a new generating function for restricted growth functions and two q-analogs of a formula for the number of standard Young tableaux of a given shape. While the first really goes back to MacMahon, the second uses one of our weighted inversion numbers and appears to be new.     

Evacuation and a geometric construction for Fibonacci tableaux

Tableaux have long been used to study combinatorial properties of permutations and multiset permutations. Discovered independently by Robinson and Schensted and generalized by Knuth, the Robinson–Schensted correspondence has provided a fundamental tool for relating permutations to tableaux. In 1963, Schützenberger defined a process called evacuation on standard tableaux which gives a relationship between the pairs of tableaux (P,Q) resulting from the Schensted correspondence for a permutation and both the reverse and the complement of that permutation. Viennot gave a geometric construction for the Schensted correspondence and Fomin described a generalization of the correspondence which provides a bijection between permutations and pairs of chains in Young's lattice.In 1975, Stanley defined a Fibonacci lattice and in 1988 he introduced the idea of a differential poset. Roby gave an insertion algorithm, analogous to the Schensted correspondence, for mapping a permutation to a pair of Fibonacci tableaux. The main results of this paper are to give an evacuation algorithm for the Fibonacci tableaux that is analogous to the evacuation algorithm on Young tableaux and to describe a geometric construction for the Fibonacci tableaux that is similar to Viennot's geometric construction for Young tableaux.     

A Bijection from Staircase Tableaux to Inversion Tables,Giving Some Eulerian and Mahonian Statistics

We give a simple bijection between staircase tableaux and inversion tables. Some nice properties of the bijection allow us to easily compute the generating polynomials of subsets of the staircase tableaux. We also give a combinatorial interpretation of some statistics of these tableaux in terms of permutations.     

An explicit bijection between semistandard tableaux and non-elliptic sl 3 webs

The sl ₃ spider is a diagrammatic category used to study the representation theory of the quantum group U _q (sl ₃). The morphisms in this category are generated by a basis of non-elliptic webs. Khovanov–Kuperberg observe that non-elliptic webs are indexed by semistandard Young tableaux. They establish this bijection via a recursive growth algorithm. Recently, Tymoczko gave a simple version of this bijection in the case that the tableaux are standard and used it to study rotation and join of webs. This article builds on Tymoczko’s bijection to give a simple and explicit algorithm for constructing all non-elliptic sl ₃ webs. As an application, we generalize results of Petersen–Pylyavskyy–Rhoades and Tymoczko proving that, for all non-elliptic sl ₃ webs, rotation corresponds to jeu de taquin promotion and join corresponds to shuffling.     

Standard Young tableaux and colored Motzkin paths

In this paper, we propose a notion of colored Motzkin paths and establish a bijection between the n-cell standard Young tableaux (SYT) of bounded height and the colored Motzkin paths of length n. This result not only gives a lattice path interpretation of the standard Young tableaux but also reveals an unexpected intrinsic relation between the set of SYTs with at most $2d+1$ rows and the set of SYTs with at most 2d rows.     

Permutation tableaux and permutation patterns

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, Adv. Math. 190 (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, Trans. Amer. Math. Soc. 76 (1954) 332-350] and the more recent q-analog of the Eulerian numbers found in [L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (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.     

Symmetric Schröder paths and restricted involutions

Let A_k be the set of permutations in the symmetric group S_k with prefix 12. This paper concerns the enumeration of involutions which avoid the set of patterns A_k. We present a bijection between symmetric Schröder paths of length 2n and involutions of length n+1 avoiding A₄. Statistics such as the number of right-to-left maxima and fixed points of the involution correspond to the number of steps in the symmetric Schröder path of a particular type. For each k≥3 we determine the generating function for the number of involutions avoiding the subsequences in A_k, according to length, first entry and number of fixed points.     

A bijection proving orthogonality of the characters of Sn

Suppose ? and β are partitions of n. If ? ? β, a bijection is given between positive pairs of rim hook tableaux of the same shape λ and content β and ?, respectively, and negative pairs of rim hook tableaux of some other shape μ and content β and ?, respectively. If ? = β, the bijection is between positive pairs and either negative pairs or permutations of hooks. The bijection, in the latter case, is a generalization of the Schensted correspondence between pairs of standard tableaux and permutations. If the irreducible characters of S_n are interpreted combinatorially using the Murnaghan-Nakayama formula, these bijections prove

$\text{∑}\text{λ}\text{X}{}^{\mathrm{\lambda }}{}_{\mathrm{\rho }}\text{X}{}^{\mathrm{\lambda }}{}_{\mathrm{\beta }}\text{=δ}{}_{\mathrm{\rho \beta }}\text{1}{}^{\mathrm{j1}}\text{J1!2}{}^{\mathrm{j2}}\text{J2!…}$

where ? = 1^j12^j2….     

A Rogers-Ramanujan bijection

In this paper we give a bijection between the partitions of n with parts congruent to 1 or 4 (mod 5) and the partitions of n with parts differing by at least 2. This bijection is obtained by a cut-and-paste procedure which starts with a partition in one class and ends with a partition in the other class. The whole construction is a combination of a bijection discovered quite early by Schur and two bijections of our own. A basic principle concerning pairs of involutions provides the key for connecting all these bijections. It appears that our methods lead to an algorithm for constructing bijections for other identities of Rogers-Ramanujan type such as the Gordon identities.     

Pairs of noncrossing free Dyck paths and noncrossing partitions

Using the bijection between partitions and vacillating tableaux, we establish a correspondence between pairs of noncrossing free Dyck paths of length 2n and noncrossing partitions of [2n+1] with n+1 blocks. In terms of the number of up steps at odd positions, we find a characterization of Dyck paths constructed from pairs of noncrossing free Dyck paths by using the Labelle merging algorithm.     

A simple bijectio n betwee n sta ndard 3× n tableaux a nd irreducible webs for $\mathfrak{sl}_{3}$

Combinatorial spiders are a model for the invariant space of the tensor product of representations. The basic objects, webs, are certain directed planar graphs with boundary; algebraic operations on representations correspond to graph-theoretic operations on webs. Kuperberg developed spiders for rank 2 Lie algebras and \mathfrak sl₂\mathfrak {sl}_{2}. Building on a result of Kuperberg, Khovanov–Kuperberg found a recursive algorithm giving a bijection between standard Young tableaux of shape 3×n and irreducible webs for \mathfraksl₃\mathfrak{sl}_{3} whose boundary vertices are all sources.     

Diagonally convex directed polyominoes and even trees: a bijection and related issues

We present a simple bijection between diagonally convex directed (DCD) polyominoes with n diagonals and plane trees with 2n edges in which every vertex has even degree (even trees), which specializes to a bijection between parallelogram polyominoes and full binary trees. Next we consider a natural definition of symmetry for DCD-polyominoes, even trees, ternary trees, and non-crossing trees, and show that the number of symmetric objects of a given size is the same in all four cases.     

Young-Fibonacci insertion, tableauhedron and Kostka numbers

This work is first concerned with some properties of the Young-Fibonacci insertion algorithm and its relation with Fomin's growth diagrams. It also investigates a relation between the combinatorics of Young-Fibonacci tableaux and the study of Okada's algebras associated to the Young-Fibonacci lattice. The original algorithm was introduced by Roby and we redefine it in such a way that both the insertion and recording tableaux of any permutation are conveniently interpreted as saturated chains in the Young-Fibonacci lattice. Using our conventions, we give a simpler proof of a property of Killpatrick's evacuation algorithm for Fibonacci tableaux. It also appears that this evacuation is no longer needed in making Roby's and Fomin's constructions coincide. We provide the set of Young-Fibonacci tableaux of size n with a structure of graded poset called tableauhedron, induced by the weak order of the symmetric group, and realized by transitive closure of elementary transformations on tableaux. We show that this poset gives a combinatorial interpretation of the coefficients of the transition matrix from the analogue of complete symmetric functions to analogue of the Schur functions in Okada's algebra associated to the Young-Fibonacci lattice. We prove a similar result relating usual Kostka numbers with four partial orders on Young tableaux, studied by Melnikov and Taskin.     

q-Analog of tableau containment

We prove a q-analog of the following result due to McKay, Morse and Wilf: the probability that a random standard Young tableau of size n contains a fixed standard Young tableau of shape λ?k tends to fλ/k! in the large n limit, where fλ is the number of standard Young tableaux of shape λ. We also consider the probability that a random pair (P,Q) of standard Young tableaux of the same shape contains a fixed pair (A,B) of standard Young tableaux.     

Major index for 01-fillings of moon polyominoes

We propose a major index statistic on 01-fillings of moon polyominoes which, when specialized to certain shapes, reduces to the major index for permutations and set partitions. We consider the set F(M,s;A) of all 01-fillings of a moon polyomino M with given column sum s whose empty rows are A, and prove that this major index has the same distribution as the number of north-east chains, which are the natural extension of inversions (resp. crossings) for permutations (resp. set partitions). Hence our result generalizes the classical equidistribution results for the permutation statistics inv and maj. Two proofs are presented. The first is an algebraic one using generating functions, and the second is a bijection on 01-fillings of moon polyominoes in the spirit of Foata's second fundamental transformation on words and permutations.     

Fibonacci Numbers, Reduced Decompositions, and 321/3412 Pattern Classes

We provide a bijection between the permutations in S _n that avoid 3412 and contain exactly one 321 pattern with the permutations in S _n+1 that avoid 321 and contain exactly one 3412 pattern. The enumeration of these classes is obtained from their classification via reduced decompositions. The results are extended to involutions in the above pattern classes using reduced decompositions reproducing a result of Egge.     

On bijections for pattern-avoiding permutations

By considering bijections from the set of Dyck paths of length 2n onto each of Sn(321) and Sn(132), Elizalde and Pak in [S. Elizalde, I. Pak, Bijections for refined restricted permutations, J. Combin. Theory Ser. A 105 (2004) 207-219] gave a bijection that preserves the number of fixed points and the number of excedances in each σ∈Sn(321). We show that a direct bijection Γ:Sn(321)→Sn(132) introduced by Robertson in [A. Robertson, Restricted permutations from Catalan to Fine and back, Sém. Lothar. Combin. 50 (2004) B50g] also preserves the number of fixed points and the number of excedances in each σ. We also show that a bijection ?^∗:Sn(213)→Sn(321) studied in [J. Backelin, J. West, G. Xin, Wilf-equivalence for singleton classes, Adv. in Appl. Math. 38 (2007) 133-148] and [M. Bousquet-Melou, E. Steingrimsson, Decreasing subsequences in permutations and Wilf equivalence for involutions, J. Algebraic Combin. 22 (2005) 383-409] preserves these same statistics, and we show that an analogous bijection from Sn(132) onto Sn(213) does the same.     

Cyclic Tableaux and Symmetric Functions

We introduce the notion of cyclic tableaux and develop involutions for Waring's formulas expressing the power sum symmetric function p_n in terms of the elementary symmetric function e_n and the homogeneous symmetric function h_n. The coefficients appearing in Waring's formulas are shown to be a cyclic analog of the multinomial coefficients, a fact that seems to have been neglected before. Our involutions also spell out the duality between these two forms of Waring's formulas, which turns out to be exactly the “duality between sets and multisets.” We also present an involution for permutations in cycle notation, leading to probably the simplest combinatorial interpretation of the Möbius function of the partition lattice and a purely combinatorial treatment of the fundamental theorem on symmetric functions. This paper is motivated by Chebyshev polynomials in connection with Waring's formula in two variables.     

The Eulerian distribution on involutions is indeed unimodal

Let In,k (respectively Jn,k) be the number of involutions (respectively fixed-point free involutions) of {1,…,n} with k descents. Motivated by Brenti's conjecture which states that the sequence In,0,In,1,…,In,n−1 is log-concave, we prove that the two sequences In,k and J2n,k are unimodal in k, for all n. Furthermore, we conjecture that there are nonnegative integers an,k such that