A Generalization of Alternating Sign Matrices

In alternating sign matrices, the first and last nonzero entry in each row and column is specified to be +1. Such matrices always exist. We investigate a generalization by specifying independently the sign of the first and last nonzero entry in each row and column to be either a +1 or a ?1. We determine necessary and sufficient conditions for such matrices to exist whose proof contains an algorithm for their construction.     

Bijections on two variations of noncrossing partitions

We find bijections on 2-distant noncrossing partitions, 12312-avoiding partitions, 3-Motzkin paths, UH-free Schröder paths and Schröder paths without peaks at even height. We also give a direct bijection between 2-distant noncrossing partitions and 12312-avoiding partitions.     

Linear relations of refined enumerations of alternating sign matrices

In recent papers we have studied refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows. The present paper is a first step towards extending these considerations to alternating sign matrices where in addition some left and right columns are fixed. The main result is a simple linear relation between the number of n×n alternating sign matrices where the top row as well as the left and the right column is fixed and the number of n×n alternating sign matrices where the two top rows and the bottom row are fixed. This may be seen as a first indication for the fact that the refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows as well as left and right columns can possibly be reduced to the refined enumerations where only some top and bottom rows are fixed. For the latter numbers we provide a system of linear equations that conjecturally determines them uniquely.     

A new proof of the refined alternating sign matrix theorem

In the early 1980s, Mills, Robbins and Rumsey conjectured, and in 1996 Zeilberger proved a simple product formula for the number of n×n alternating sign matrices with a 1 at the top of the ith column. We give an alternative proof of this formula using our operator formula for the number of monotone triangles with prescribed bottom row. In addition, we provide the enumeration of certain 0-1-(−1) matrices generalizing alternating sign matrices.     

An operator formula for the number of halved monotone triangles with prescribed bottom row

Monotone triangles are certain triangular arrays of integers, which correspond to n×n alternating sign matrices when prescribing (1,2,…,n) as bottom row of the monotone triangle. In this article we define halved monotone triangles, a specialization of which correspond to vertically symmetric alternating sign matrices. We derive an operator formula for the number of halved monotone triangles with prescribed bottom row which is analogous to our operator formula for the number of ordinary monotone triangles [I. Fischer, The number of monotone triangles with prescribed bottom row, Adv. in Appl. Math. 37 (2) (2006) 249-267].     

A direct bijection between descending plane partitions with no special parts and permutation matrices

We present a direct bijection between descending plane partitions with no special parts and permutation matrices. This bijection has the desirable property that the number of parts of the descending plane partition corresponds to the inversion number of the permutation. Additionally, the number of maximum parts in the descending plane partition corresponds to the position of the one in the last column of the permutation matrix. We also discuss the possible extension of this approach to finding a bijection between descending plane partitions and alternating sign matrices.     

Bijections on two variations of noncrossing partitions

We find bijections on 2-distant noncrossing partitions, 12312-avoiding partitions, 3-Motzkin paths, UH-free Schröder paths and Schröder paths without peaks at even height.     

Enumeration of symmetry classes of alternating sign matrices and characters of classical groups

An alternating sign matrix is a square matrix with entries 1, 0 and −1 such that the sum of the entries in each row and each column is equal to 1 and the nonzero entries alternate in sign along each row and each column. To some of the symmetry classes of alternating sign matrices and their variations, G. Kuperberg associate square ice models with appropriate boundary conditions, and give determinant and Pfaffian formulae for the partition functions. In this paper, we utilize several determinant and Pfaffian identities to evaluate Kuperberg's determinants and Pfaffians, and express the round partition functions in terms of irreducible characters of classical groups. In particular, we settle a conjecture on the number of vertically and horizontally symmetric alternating sign matrices (VHSASMs). Dedicated to the memory of David Robbins.     

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.     

New constants in discrete Lieb–Thirring inequalities for Jacobi matrices

As is known, some results used for improving constants in the Lieb–Thirring inequalities for Schr?dinger operators in L ²(−∞, ∞) can be translated to discrete Schr?dinger operators and, more generally, to Jacobi matrices. We improve constants obtained earlier for Lieb–Thirring inequalities for the moments of eigenvalues larger than or equal to one. Bibliography: 9 titles.     

Simple permutations and pattern restricted permutations

A simple permutation is one that does not map any non-trivial interval onto an interval. It is shown that, if the number of simple permutations in a pattern restricted class of permutations is finite, the class has an algebraic generating function and is defined by a finite set of restrictions. Some partial results on classes with an infinite number of simple permutations are given. Examples of results obtainable by the same techniques are given; in particular it is shown that every pattern restricted class properly contained in the 132-avoiding permutations has a rational generating function.     

The operator formula for monotone triangles - simplified proof and three generalizations

We provide a simplified proof of our operator formula for the number of monotone triangles with prescribed bottom row, which enables us to deduce three generalizations of the formula. One of the generalizations concerns a certain weighted enumeration of monotone triangles which specializes to the weighted enumeration of alternating sign matrices with respect to the number of −1s in the matrix when prescribing (1,2,…,n) as the bottom row of the monotone triangle.     

Restricted Dumont Permutations

We analyze the structure and enumerate Dumont permutations of the first and second kinds avoiding certain patterns or sets of patterns of length 3 and 4. Some cardinalities are given by Catalan numbers, powers of 2, little Schr?der numbers, and other known or related sequences. Received June 21, 2004     

Alternating sign matrices and descending plane partitions

An alternating sign matrix is a square matrix such that (i) all entries are 1, ?1, or 0, (ii) every row and column has sum 1, and (iii) in every row and column the nonzero entries alternate in sign. Striking numerical evidence of a connection between these matrices and the descending plane partitions introduced by Andrews (Invent. Math.53 (1979), 193–225) have been discovered, but attempts to prove the existence of such a connection have been unsuccessful. This evidence, however, did suggest a method of proving the Andrews conjecture on descending plane partitions, which in turn suggested a method of proving the Macdonald conjecture on cyclically symmetric plane partitions (Invent. Math.66 (1982), 73–87). In this paper is a discussion of alternating sign matrices and descending plane partitions, and several conjectures and theorems about them are presented.     

Sign-balance identities of Adin–Roichman type on 321-avoiding alternating permutations

Adin and Roichman proved a set of refined sign-balance identities on 321-avoiding permutations respecting the last descent of the permutations, which we call the identities of Adin–Roichman type. In this work, we construct a new involution on plane trees that proves refined sign-balance properties on 321-avoiding alternating permutations respecting the first and last entries of the permutations respectively and obtain two sets of identities of Adin–Roichman type.     

Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials

Several authors have examined connections among 132-avoiding permutations, continued fractions, and Chebyshev polynomials of the second kind. In this paper we find analogues for some of these results for permutations π avoiding 132 and 1□23 (there is no occurrence π_i<π_j<π_j+1 such that 1?i?j-2) and provide a combinatorial interpretation for such permutations in terms of lattice paths. Using tools developed to prove these analogues, we give enumerations and generating functions for permutations which avoid both 132 and 1□23, and certain additional patterns. We also give generating functions for permutations avoiding 132 and 1□23 and containing certain additional patterns exactly once. In all cases we express these generating functions in terms of Chebyshev polynomials of the second kind.     

Refined enumerations of alternating sign matrices: monotone (<Emphasis Type="Italic">d</Emphasis>,<Emphasis Type="Italic">m</Emphasis>)-trapezoids with prescribed top and bottom row

Monotone triangles are plane integer arrays of triangular shape with certain monotonicity conditions along rows and diagonals. Their significance is mainly due to the fact that they correspond to n×n alternating sign matrices when prescribing (1,2,…,n) as bottom row of the array. We define monotone (d,m)-trapezoids as monotone triangles with m rows where the d−1 top rows are removed. (These objects are also equivalent to certain partial alternating sign matrices.) It is known that the number of monotone triangles with bottom row (k ₁,…,k _n ) is given by a polynomial α(n;k ₁,…,k _n ) in the k _i ’s. The main purpose of this paper is to show that the number of monotone (d,m)-trapezoids with prescribed top and bottom row appears as a coefficient in the expansion of a specialisation of α(n;k ₁,…,k _n ) with respect to a certain polynomial basis. This settles a generalisation of a recent conjecture of Romik et al. (Adv. Math. 222:2004–2035, 2009). Among other things, the result is used to express the number of monotone triangles with bottom row (1,2,…,i−1,i+1,…,j−1,j+1,…,n) (which is, by the standard bijection, also the number of n×n alternating sign matrices with given top two rows) in terms of the number of n×n alternating sign matrices with prescribed top and bottom row, and, by a formula of Stroganov for the latter numbers, to provide an explicit formula for the first numbers. (A formula of this type was first derived by Karklinsky and Romik using the relation of alternating sign matrices to the six-vertex model.)     

On principal iteration semigroups in the case of multiplier zero

We collect and generalize various known definitions of principal iteration semigroups in the case of multiplier zero and establish connections among them. The common characteristic property of each definition is conjugating of an iteration semigroup to different normal forms. The conjugating functions are expressed by suitable formulas and satisfy either B?ttcher’s or Schr?der’s functional equation.     

Pattern Avoidance in Ordered Set Partitions

In this paper we consider the enumeration of ordered set partitions avoiding a permutation pattern of length 2 or 3. We provide an exact enumeration for avoiding the permutation 12. We also give exact enumeration for ordered partitions with 3 blocks and ordered partitions with n?1 blocks avoiding a permutation of length 3. We use enumeration schemes to recursively enumerate 123-avoiding ordered partitions with any block sizes. Finally, we give some asymptotic results for the growth rates of the number of ordered set partitions avoiding a single pattern; including a Stanley-Wilf type result that exhibits existence of such growth rates.     

Weighted Counting of Inversions on Alternating Sign Matrices

We generalize the author’s formula (2011) on weighted counting of inversions on permutations to one on alternating sign matrices. The proof is based on the sequential construction of alternating sign matrices from the unit matrix which essentially follows from the earlier work of Lascoux-Schützenberger (1996).