On the number of rim hook tableaux

A hooklength formula for the number of rim hook tableaux is used to obtain an inequality relating the number of rim hook tableaux of a given shape to the number of standard Young tableaux of the same shape. This provides an upper bound for a certain family of characters of the symmetric group. The analogues for shifted shapes and rooted trees are also given. Bibliography: 13 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 223, 1995, pp. 219–226. Partially supported by the NSF (DMS-9400914).     

Vertex Operators for Standard Bases of the Symmetric Functions

We present formulas for operators which add a row or a column to the partition indexing the power, monomial, forgotten, Schur, homogeneous and elementary symmetric functions. As an application of these operators we show that the operator that adds a column to the Schur unctions can be used to calculate a formula for the number of pairs of standard tableaux the same shape and height less than or equal to a fixed k.     

Symmetry and Log-Concavity Results for Statistics on Fibonacci Tableaux

In this paper, we study the properties of the inversion statistic and the Fibonacci major index, Fibmaj, as defined on standard Fibonacci tableaux. We prove that these two statistics are symmetric and log-concave over all standard Fibonacci tableaux of a given shape μ and provide two combinatorial proofs of the symmetry result, one a direct bijection on the set of tableaux and the other utilizing 0, 1-fillings of a staircase shape. We conjecture that the inversion and Fibmaj statistics are log-concave over all standard Fibonacci tableaux of a given size n. In addition, we show a well-known bijection between standard Fibonacci tableaux of size n and involutions in S _n which takes the Fibmaj statistic to a new statistic called the submajor index on involutions.     

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.     

Tableaux and plane partitions of truncated shapes

We consider a new kind of straight and shifted plane partitions/Young tableaux – ones whose diagrams are no longer of partition shape, but rather Young diagrams with boxes erased from their upper right ends. We find formulas for the number of standard tableaux in certain cases, namely a shifted staircase without the box in its upper right corner, i.e. truncated by a box, a rectangle truncated by a staircase and a rectangle truncated by a square minus a box. The proofs involve finding the generating function of the corresponding plane partitions using interpretations and formulas for sums of restricted Schur functions and their specializations. The number of standard tableaux is then found as a certain limit of this function.     

The Distributions of the Entries of Young Tableaux

Let T be a standard Young tableau of shape λ⊢k. We show that the probability that a randomly chosen Young tableau of n cells contains T as a subtableau is, in the limit n→∞, equal to f^λ/k!, where f^λ is the number of all tableaux of shape λ. In other words, the probability that a large tableau contains T is equal to the number of tableaux whose shape is that of T, divided by k!. We give several applications, to the probabilities that a set of prescribed entries will appear in a set of prescribed cells of a tableau, and to the probabilities that subtableaux of given shapes will occur. Our argument rests on a notion of quasirandomness of families of permutations, and we give sufficient conditions for this to hold.     

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.     

Designs and Representation of the Symmetric Group

We study (generalized) designs supported by words of given composition. We characterize them in terms of orthogonality relations with Specht modules; we define some zonal functions for the symmetric group and we give a closed formula for them, indexed on ordered pair of semi-standard generalized tableaux: Hahn polynomials are a particular case. We derive an algorithm to test if a set is a design. We use it to search designs in some ternary self-dual codes.     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

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.     

A Symmetry Theorem on a Modified Jeu De Taquin

For their bijective proof of the hook-length formula for the number of standard tableaux of a fixed shape Novelli et al. define a modified jeu de taquin which transforms an arbitrary filling of the Ferrers diagram with 1, 2, , n(tabloid) into a standard tableau. Their definition relies on a total order of the cells in the Ferrers diagram induced by a special standard tableau, however, this definition also makes sense for the total order induced by any other standard tableau. Given two standard tableaux P, Q of the same shape we show that the number of tabloids which result in P if we perform the modified jeu de taquin with respect to the total order induced by Q is equal to the number of tabloids which result in Q if we perform the modified jeu de taquin with respect to P. This symmetry theorem extends to skew shapes and shifted skew shapes.     

On selecting a random shifted young tableau

A probabilistic algorithm of Greene, Nijenhuis, and Wilf is applied to shifted shapes. It is proved that this procedure yields a Young tableau of the given shape and that all such tableaux are equally likely.     

Multiplicity Free Schur, Skew Schur, and Quasisymmetric Schur Functions

In this paper we classify all Schur functions and skew Schur functions that are multiplicity free when expanded in the basis of fundamental quasisymmetric functions, termed F-multiplicity free. Combinatorially, this is equivalent to classifying all skew shapes whose standard Young tableaux have distinct descent sets. We then generalize our setting, and classify all F-multiplicity free quasisymmetric Schur functions with one or two terms in the expansion, or one or two parts in the indexing composition. This identifies composition shapes such that all standard composition tableaux of that shape have distinct descent sets. We conclude by providing such a classification for quasisymmetric Schur function families, giving a classification of Schur functions that are in some sense almost F-multiplicity free.     

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.     

On the Orthogonal Tableaux of Koike and Terada

Many different definitions have been given for semistandard odd and even orthogonal tableaux which enumerate the corresponding irreducible orthogonal characters. Weightpreserving bijections have been provided between some of these sets of tableaux (see [3], [8]). We give bijections between the (semistandard) odd orthogonal Koike-Terada tableaux and the odd orthogonal Sundaram-tableaux and between the even orthogonal Koike-Terada tableaux and the even orthogonal King-Welsh tableaux. As well, we define an even version of orthogonal Sundaram tableaux which enumerate the irreducible characters of O(2n).     

Arc permutations

Arc permutations and unimodal permutations were introduced in the study of triangulations and characters. This paper studies combinatorial properties and structures on these permutations. First, both sets are characterized by pattern avoidance. It is also shown that arc permutations carry a natural affine Weyl group action, and that the number of geodesics between a distinguished pair of antipodes in the associated Schreier graph, and the number of maximal chains in the weak order on unimodal permutations, are both equal to twice the number of standard Young tableaux of shifted staircase shape. Finally, a bijection from non-unimodal arc permutations to Young tableaux of certain shapes, which preserves the descent set, is described and applied to deduce a conjectured character formula of Regev.     

Pieri’s formula for generalized Schur polynomials

Young's lattice, the lattice of all Young diagrams, has the Robinson-Schensted-Knuth correspondence, the correspondence between certain matrices and pairs of semi-standard Young tableaux with the same shape. Fomin introduced generalized Schur operators to generalize the Robinson-Schensted-Knuth correspondence. In this sense, generalized Schur operators are generalizations of semi-standard Young tableaux. We define a generalization of Schur polynomials as expansion coefficients of generalized Schur operators. We show that the commutation relation of generalized Schur operators implies Pieri's formula for generalized Schur polynomials.     

Combinatorics of the K-theory of affine Grassmannians

We introduce a family of tableaux that simultaneously generalizes the tableaux used to characterize Grothendieck polynomials and k-Schur functions. We prove that the polynomials drawn from these tableaux are the affine Grothendieck polynomials and k-K-Schur functions – Schubert representatives for the K-theory of affine Grassmannians and their dual in the nil Hecke ring. We prove a number of combinatorial properties including Pieri rules.