Symmetric Permutations Avoiding Two Patterns

Symmetric pattern-avoiding permutations are restricted permutations which are invariant under actions of certain subgroups of D ₄, the symmetry group of a square. We examine pattern-avoiding permutations with 180° rotational-symmetry. In particular, we use combinatorial techniques to enumerate symmetric permutations which avoid one pattern of length three and one pattern of length four. Our results involve well-known sequences such as the alternating Fibonacci numbers, triangular numbers, and powers of two.     

Dyck paths and restricted permutations

This paper is devoted to characterize permutations with forbidden patterns by using canonical reduced decompositions, which leads to bijections between Dyck paths and S_n(321) and S_n(231), respectively. We also discuss permutations in S_n avoiding two patterns, one of length 3 and the other of length k. These permutations produce a kind of discrete continuity between the Motzkin and the Catalan numbers.     

The X-Class and Almost-Increasing Permutations

In this paper we give a bijection between the class of permutations that can be drawn on an X-shape and a certain set of permutations that appears in Knuth [4] in connection to sorting algorithms. A natural generalization of this set leads us to the definition of almost-increasing permutations, which is a one-parameter family of permutations that can be characterized in terms of forbidden patterns. We find generating functions for almost-increasing permutations by using their cycle structure to map them to colored Motzkin paths. We also give refined enumerations with respect to the number of cycles, fixed points, excedances, and inversions.     

On basic forbidden patterns of functions

The allowed patterns of a map on a one-dimensional interval are those permutations that are realized by the relative order of the elements in its orbits. The set of allowed patterns is completely determined by the minimal patterns that are not allowed. These are called basic forbidden patterns.In this paper, we study basic forbidden patterns of several functions. We show that the logistic map L_r(x)=rx(1−x) and some generalizations have infinitely many of them for 1<r≤4, and we give a lower bound on the number of basic forbidden patterns of L₄ of each length. Next, we give an upper bound on the length of the shortest forbidden pattern of a piecewise monotone map. Finally, we provide some necessary conditions for a set of permutations to be the set of basic forbidden patterns of such a map.     

Counting involutory, unimodal, and alternating signed permutations

In this work we count the number of involutory, unimodal, and alternating elements of the group of signed permutations B_n, and the group of even-signed permutations D_n. Recurrence relations, generating functions, and explicit formulas of the enumerating sequences are given.     

A p, q-Analogue of the Generalized Derangement Numbers

In this paper, we study the numbers D _n,k which are defined as the number of permutations σ of the symmetric group S _n such that σ has no cycles of length j for j ≤ k. In the case k = 1, D _n,1 is simply the number of derangements of an n-element set. As such, we shall call the numbers D _n,k generalized derangement numbers. Garsia and Remmel [4] defined some natural q-analogues of D _n,1, denoted by D _n,1(q), which give rise to natural q-analogues of the two classical recursions of the number of derangements. The method of Garsia and Remmel can be easily extended to give natural p, q-analogues D _n,1(p, q) which satisfy natural p, q-analogues of the two classical recursions for the number of derangements. In [4], Garsia and Remmel also suggested an approach to define q-analogues of the numbers D _n,k . In this paper, we show that their ideas can be extended to give a p, q-analogue of the generalized derangements numbers. Again there are two classical recursions for eneralized derangement numbers. However, the p, q-analogues of the two classical recursions are not as straightforward when k ≥ 2. Partially supported by NSF grant DMS 0400507.     

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.     

Forest-Like Permutations

Given a permutation , construct a graph G _π on the vertex set {1, 2,..., n} by joining i to j if (i) i < j and π(i) < π(j) and (ii) there is no k such that i < k < j and π(i) < π(k) < π(j). We say that π is forest-like if G _π is a forest. We first characterize forest-like permutations in terms of pattern avoidance, and then by a certain linear map being onto. Thanks to recent results of Woo and Yong, these show that forest-like permutations characterize Schubert varieties which are locally factorial. Thus forest-like permutations generalize smooth permutations (corresponding to smooth Schubert varieties). We compute the generating function of forest-like permutations. As in the smooth case, it turns out to be algebraic. We then adapt our method to count permutations for which G _π is a tree, or a path, and recover the known generating function of smooth permutations. Received March 27, 2006     

Separable d-Permutations and Guillotine Partitions

We characterize separable multidimensional permutations in terms of forbidden patterns and enumerate them by means of generating function, recursive formula, and explicit formula. We find a connection between multidimensional permutations and guillotine partitions of a box. In particular, a bijection between separable d-dimensional permutations and guillotine partitions of a 2 ^d-1-dimensional box is constructed. We also study enumerating problems related to guillotine partitions under certain restrictions revealing connections to other combinatorial structures. This allows us to obtain several results on patterns in permutations.     

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.     

Transposition generation of alternating permutations

A permutation _{1 2}... _n is alternating if ₁< ₂> ₃< ₄.... Alternating permutations are counted by the Euler numbers. Here we show that alternating permutations can be listed so that successive permutations differ by a transposition, ifn is odd. Extensions and open problems are mentioned.Research supported by the Natural Sciences and Engineering Research Council of Canada under grant A3379.     

Maximal clones on uncountable sets that include all permutations

We first determine the maximal clones on a set X of infinite regular cardinality κ which contain all permutations but not all unary functions, extending a result of Heindorf’s for countably infinite X. If κ is countably infinite or weakly compact, this yields a list of all maximal clones containing the permutations, since in that case the maximal clones above the unary functions are known. We then generalize a result of Gavrilov’s to obtain on all infinite X a list of all maximal submonoids of the monoid of unary functions which contain the permutations. Received January 8, 2004; accepted in final form December 22, 2004.     

Applications of the symmetric chain decomposition of the lattice of divisors

The symmetric chain decomposition of the lattice of divisors,D _N, is applied to prove results about the strict unimodality of the Whitney numbers ofD _N, about minimum interval covers for the union of consecutive rank-sets ofD _N, and about the distribution of sums of vectors in which each vector can be included several times (an extension of the famous Littlewood-Offord problem)Research supported in part by NSA/MSP GrantMDA904-92H3053.     

Relative difference sets fixed by inversion and Cayley graphs

Using graph theoretical technique, we present a construction of a (30,2,29,14)-relative difference set fixed by inversion in the smallest finite simple group—the alternating group A₅. To our knowledge this is the first example known of relative difference sets in the finite simple groups with a non-trivial forbidden subgroup. A connection is then established between some relative difference sets fixed by inversion and certain antipodal distance-regular Cayley graphs. With the connection, several families of antipodal distance-regular Cayley graphs which are coverings of complete graphs are presented.     

Dense Packing of Patterns in a Permutation

We study the length L _k of the shortest permutation containing all patterns of length k. We establish the bounds e ⁻² k ² < L _k ≤ (2/3 + o(1))k ². We also prove that as k → ∞, there are permutations of length (1/4 + o(1))k ² containing almost all patterns of length k. Received January 2, 2007     

A Lie-theoretic setting for the classical interpolation theories

The three classical interpolation theories — Newton-Lagrange, Thiele and Pick-Nevanlinna — are developed within a common Lie-theoretic framework. They essentially involve a recursive process, each step geometrically providing an analytic map from a Riemann surface to a Grassmann manifold. The operation which passes from the (n−1)st to the nth involves the action of what the physicists call a group of gauge transformations. There is also a first-order difference operator which maps the set of solutions of the nth order interpolation to the (n−1)st: This difference operator is, in each case, covariant with respect to the action of the Lie groups involved. For Newton-Lagrange interpolation, this Lie group is the group of affine transformations of the complex plane; for Thiele interpolation the group SL(2, C) of projective transformations; and for Pick-Nevanlinna interpolation the subgroup SU(1, 1) of SL(2, C) which leaves invariant the disk in the complex plane. National Research Council Senior Research Associate at the Ames Research Center (NASA)}.     

The bias of three pseudo-random shuffles

Three schemes for shuffling a deck ofn cards are studied, each involving a random choice from [n] ⁿ . The shuffles favor some permutations over others sincen! does not dividen ⁿ . The probabilities that the shuffles lead to some simple permutations, for instance cycles left and right and the identity, are calculated. Some inequalities are obtained which lead to information about the least and most likely permutations. Numbers of combinatorial interest occur, notably the Catalan numbers and the Bell numbers.     

Monotone path systems in simple regions

A monotone path system (MPS) is a finite set of pairwise disjoint paths (polygonal areas) in thexy-plane such that every horizontal line intersects each of the paths in at most one point. A MPS naturally determines a pairing of its top points with its bottom points. We consider a simple polygon in thexy-plane wich bounds the simple polygonal (closed) regionD. LetT andB be two finite, disjoint, equicardinal sets of points ofD. We give a good characterization for the existence of a MPS inD which pairsT withB, and a good algorithm for finding such a MPS, and we solve the problem of finding all MPSs inD which pairT withB. We also give sufficient conditions for any such pairing to be the same.The first author's research is supported by the Natural Sciences and Engineering Research Council of Canada     

Restricted 123-avoiding Baxter permutations and the Padovan numbers

Baxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.     

An action of subgroups of mapping class groups on polynomial algebras

We study a certain subgroup of the mapping class group of a surface with boundary by obtaining an action of this subgroup on a polynomial algebra. This action comes from a lift of the action of the subgroup on a trace algebra, Magnus having done a similar thing for the braid groups. We then investigate the invariant theory for this action and various representations that this action affords. In particular, we obtain finite permutation representations and infinite linear representations of these subgroups that are non-trivial on subgroups of the Torelli group.