Restricted Dumont permutations, Dyck paths, and noncrossing partitions

We complete the enumeration of Dumont permutations of the second kind avoiding a pattern of length 4 which is itself a Dumont permutation of the second kind. We also consider some combinatorial statistics on Dumont permutations avoiding certain patterns of length 3 and 4 and give a natural bijection between 3142-avoiding Dumont permutations of the second kind and noncrossing partitions that uses cycle decomposition, as well as bijections between 132-, 231- and 321-avoiding Dumont permutations and Dyck paths. Finally, we enumerate Dumont permutations of the first kind simultaneously avoiding certain pairs of 4-letter patterns and another pattern of arbitrary length.     

On the sign-imbalance of partition shapes

Let the sign of a standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. A conjecture by Richard Stanley says that the sum of the signs of all SYTs with n squares is 2^⌊n/2⌋. We present a stronger theorem with a purely combinatorial proof using the Robinson-Schensted correspondence and a new concept called chess tableaux.We also prove a sharpening of another conjecture by Stanley concerning weighted sums of squares of sign-imbalances. The proof is built on a remarkably simple relation between the sign of a permutation and the signs of its RS-corresponding tableaux.     

The Robinson-Schensted correspondence for skew oscillating semi-standard tableaux

We introduce an analogue of the Robinson-Schensted correspondence for skew oscillating semi-standard tableaux that generalizes the correspondence for skew oscillating standard tableaux. We give a geometric construction for skew oscillating semi-standard tableaux and examine its combinatorial properties.     

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.     

Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups

Eulerian quasisymmetric functions were introduced by Shareshian and Wachs in order to obtain a q-analog of Euler?s exponential generating function formula for the Eulerian numbers (Shareshian and Wachs, 2010 [17]). They are defined via the symmetric group, and applying the stable and nonstable principal specializations yields formulas for joint distributions of permutation statistics. We consider the wreath product of the cyclic group with the symmetric group, also known as the group of colored permutations. We use this group to introduce colored Eulerian quasisymmetric functions, which are a generalization of Eulerian quasisymmetric functions. We derive a formula for the generating function of these colored Eulerian quasisymmetric functions, which reduces to a formula of Shareshian and Wachs for the Eulerian quasisymmetric functions. We show that applying the stable and nonstable principal specializations yields formulas for joint distributions of colored permutation statistics, which generalize the Shareshian–Wachs q-analog of Euler?s formula, formulas of Foata and Han, and a formula of Chow and Gessel.     

Random sorting networks

A sorting network is a shortest path from 12?n to n?21 in the Cayley graph of Sn generated by nearest-neighbour swaps. We prove that for a uniform random sorting network, as n→∞ the space-time process of swaps converges to the product of semicircle law and Lebesgue measure. We conjecture that the trajectories of individual particles converge to random sine curves, while the permutation matrix at half-time converges to the projected surface measure of the 2-sphere. We prove that, in the limit, the trajectories are Hölder-1/2 continuous, while the support of the permutation matrix lies within a certain octagon. A key tool is a connection with random Young tableaux.     

Card shuffling and a transformation on S n

Summary We consider two card shuffling schemes. The first, which has appeared in the literature previously ([G], [RB], [T]), is as follows: start with a deck ofn cards, and pick a random tuplet { 1, 2, , n} ⁿ ; interchange cards 1 andt ₁, then interchange cards 2 andt ₂, etc. The second scheme, which can be viewed as a transformation on the symmetric groupS _n , is given by the restriction of the former shuffling scheme to tuplest which form a permutation of {1, 2,,n}.We determine the bias of each of these shuffling schemes with respect to the sets of transpositions and derangements, and the expected number of fixed points of a permutation generated by each of these shuffling schemes. For the latter scheme we prove combinatorially that the permutation which arises with the highest probability is the identity. The same question is open for the former scheme. We refute a candidate answer suggested by numerical evidence [RB].This work was carried out in part while R.S. was visiting the Institute for Mathematics and its Applications and was partly supported through NSF Grant CCR-8707539.     

The structure of alternative tableaux

In this paper we study alternative tableaux introduced by Viennot [X. Viennot, Alternative tableaux, permutations and partially asymmetric exclusion process, talk in Cambridge, 2008]. These tableaux are in simple bijection with permutation tableaux, defined previously by Postnikov [A. Postnikov, Total positivity, Grassmannians, and networks, arXiv:math/0609764v1 [math.CO], 2006].We exhibit a simple recursive structure for alternative tableaux, from which we can easily deduce a number of enumerative results. We also give bijections between these tableaux and certain classes of labeled trees. Finally, we exhibit a bijection with permutations, and relate it to some other bijections that already appeared in the literature.     

Adjacency of Young tableaux and the Springer fibers

We connect different results about irreducible components of the Springer fibers of type A. Firstly, we show a relation between the Spaltenstein partition of the fibers and a total order on the set of standard Young tableaux. Next, using a result of Steinberg, we connect a work of the first author to the Robinson–Schensted map. We also perform the Spaltenstein study of the relative position of the Springer fibers and -fibrations of the flag manifold. This leads us to consider the adjacency relation on the set of standard Young tableaux and to define oriented and labeled graphs with the standard Young tableaux as vertices. Using this adjacency relation, we describe some smooth irreducible components of the Springer fibers. Finally, we show that these graphs can be identified with some full subgraphs of the Bruhat graph.     

Some combinatorial interpretations ofq-analogs of Schröder numbers

We introduce two definitions of Schröder numberq-analogs and show some combinatorial interpretations of theseq-numbers. We use the following combinatorial objects for these interpretations: Schröder paths, 1-colored parallelogram polyominoes and permutations with forbidden subsequences (4231, 4132). We enumerate these objects according to various parameters by means of a recentq-counting technique. We prove that the firstq-Schröder number enumerates of Schröder paths with respect to area and the number of permutation inversions, while the second one counts the 1-colored parallelogram polyominoes according to their width and area. Finally, we illustrate some relations among the parameters characterizing the combinatorial objects.     

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 method for proving polynomial enumeration formulas

We present an elementary method for proving enumeration formulas which are polynomials in certain parameters if others are fixed and factorize into distinct linear factors over Z. Roughly speaking the idea is to prove such formulas by “explaining” their zeros using an appropriate combinatorial extension of the objects under consideration to negative integer parameters. We apply this method to prove a new refinement of the Bender-Knuth (ex-)Conjecture, which easily implies the Bender-Knuth (ex-)Conjecture itself. This is probably the most elementary way to prove this result currently known. Furthermore we adapt our method to q-polynomials, which allows us to derive generating function results as well. Finally we use this method to give another proof for the enumeration of semistandard tableaux of a fixed shape which differs from our proof of the Bender-Knuth (ex-)Conjecture in that it is a multivariate application of our method.     

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.     

Permutation Sign under the Robinson-Schensted Correspondence

We show how the sign of a permutation can be deduced from the tableaux induced by the permutation under the Robinson-Schensted correspondence. The result yields a simple proof of a conjecture on the squares of imbalances raised recently by Stanley.AMS Subject Classification: 05E10, 05A15.     

Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux

We introduce a new family of noncommutative analogues of the Hall-Littlewood symmetric functions. Our construction relies upon Tevlin's bases and simple q-deformations of the classical combinatorial Hopf algebras. We connect our new Hall-Littlewood functions to permutation tableaux, and also give an exact formula for the q-enumeration of permutation tableaux of a fixed shape. This gives an explicit formula for: the steady state probability of each state in the partially asymmetric exclusion process (PASEP); the polynomial enumerating permutations with a fixed set of weak excedances according to crossings; the polynomial enumerating permutations with a fixed set of descent bottoms according to occurrences of the generalized pattern 2-31.     

Permutation polynomials over finite fields from a powerful lemma

Using a lemma proved by Akbary, Ghioca, and Wang, we derive several theorems on permutation polynomials over finite fields. These theorems give not only a unified treatment of some earlier constructions of permutation polynomials, but also new specific permutation polynomials over Fq. A number of earlier theorems and constructions of permutation polynomials are generalized. The results presented in this paper demonstrate the power of this lemma when it is employed together with other techniques.     

Restricted colored permutations and Chebyshev polynomials

Several authors have examined connections between restricted permutations and Chebyshev polynomials of the second kind. In this paper we prove analogues of these results for colored permutations. First we define a distinguished set of length two and length three patterns, which contains only 312 when just one color is used. Then we give a recursive procedure for computing the generating function for the colored permutations which avoid this distinguished set and any set of additional patterns, which we use to find a new set of signed permutations counted by the Catalan numbers and a new set of signed permutations counted by the large Schröder numbers. We go on to use this result to compute the generating functions for colored permutations which avoid our distinguished set and any layered permutation with three or fewer layers. We express these generating functions in terms of Chebyshev polynomials of the second kind and we show that they are special cases of generating functions for involutions which avoid 3412 and a layered permutation.     

Three enumeration formulas of standard Young tableaux of truncated shapes

In this paper we consider the enumeration of three kinds of standard Young tableaux (SYT) of truncated shapes by use of the method of multiple integrals. A product formula for the number of truncated shapes of the form (n^m, n ? r)\δ_k–1 is given, which implies that the number of SYT of truncated shape (n², 1)\(1) is the number of level steps in all 2-Motzkin paths. The number of SYT with three rows truncated by some boxes ((n + k)³)\(k) is discussed. Furthermore, the integral representation of the number of SYT of truncated shape (n^m)\(3, 2) is derived, which implies a simple formula of the number of SYT of truncated shape (nⁿ)\(3, 2).     

Restricted even permutations and Chebyshev polynomials

We study generating functions for the number of even (odd) permutations on n letters avoiding 132 and an arbitrary permutation τ on k letters, or containing τ exactly once. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.