On the distributions of the lengths of the longest monotone subsequences in random words

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. (In the limit as k→∞ these become the corresponding distributions for permutations on N letters.) We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating unction gives the distribution of the smallest eigenvalue in the k×k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N→∞ limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k×k hermitian matrices of trace zero. Received: 9 September 1999 / Revised version: 24 May 2000 / Published online: 24 January 2001     

Permutations with roots

We prove that the probability p₂(n) that a random permutation of length n has a square root is monotonically nonincreasing in n. More generally, we prove that the probability p_r(n) that a random permutation of length n has an rth root, r prime, is monotonically nonincreasing in n. We also show for all r≥2 that p_r(n)→0 as n→∞. While doing this, we combinatorially prove that p_r(n)=p_r(n+1) for r prime and for all n not congruent to −1 mod r, and we construct several bijections for sets of permutations defined by modular class restrictions on the cycle lengths. We also include a simple probabilistic proof that, for r≥2, p_r(n)→0 as n→∞. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 157–167, 2000     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

On unimodal subsequences

In this paper we prove that any sequence of n real numbers contains a unimodal subsequence of length at least $\text{[(3n ?}\text{3}\text{4}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{?}\text{1}\text{2}\text{]}$ and that this bound is best possible.     

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     

Permutations with small maximal k-consecutive sums

Let $n$ and $k$ be positive integers with $n>k$. Given a permutation $({\pi }_1,\dots ,{\pi }_n)$ of integers $1,\dots ,n$, we consider $k$-consecutive sums of $\pi$, i.e., $s_i?{\sum }_{j=0}^{k?1}{\pi }_{i+j}$ for $i=1,\dots ,n$, where we let ${\pi }_{n+j}={\pi }_j$. What we want to do in this paper is to know the exact value of $\mathsf{msum}(n,k)?min\left\{max\{s_i:i=1,\dots ,n\}?\frac{k(n+1)}{2}:\pi \in S_n\right\},$ where $S_n$ denotes the set of all permutations of $1,\dots ,n$. In this paper, we determine the exact values of $\mathsf{msum}(n,k)$ for some particular cases of $n$ and $k$. As a corollary of the results, we obtain $\mathsf{msum}(n,3)$, $\mathsf{msum}(n,4)$ and $\mathsf{msum}(n,6)$ for any $n$.     

Geometric Permutations

A difference permutation is a structure which serves as an instrument to recognize important properties of permutations. Since special permutations are models for orthoschemes in generalized hyperbolic spaces (Minkowskian spaces) of dimension d there difference permutations give informations on the type of such orthoschemes. In this note with the help of difference permutations especially geometric permutations are explained which describe the structure of the concerning orthoschemes. This knowledge is necessary to count the numbers of orthoscheme types and special chains of orthoschemes as shown in B?hm (http://www.minet.uni-jena.de/preprints/boehm_08/Napiercycles.pdf).     

On summability of subsequences

Ohne ZusammenfassungDie Untersuchungen dieser Arbeit wurden zum Teil am Courant Institute of Mathematical Sciences, New York University, durchgeführt und dabei von der National Science Foundation, Grant NSF-GP-8724, unterstützt.     

Matching subsequences in trees

Given two rooted, labeled trees P and T the tree path subsequence problem is to determine which paths in P are subsequences of which paths in T. Here a path begins at the root and ends at a leaf. In this paper we propose this problem as a useful query primitive for XML data, and provide new algorithms improving the previously best known time and space bounds.     

Restricted Symmetric Permutations

Pattern-avoiding involutions, which have received much enumerative attention, are pattern-avoiding permutations which are invariant under the natural action of a certain subgroup of D ₈, the symmetry group of a square. Three other nontrivial subgroups of D ₈ also have invariant permutations under this action. For each of these subgroups, we enumerate the set of permutations which are invariant under the action of the subgroup and which also avoid a given set of forbidden patterns. The sets of forbidden patterns we consider include all subsets of S ₃. For each subgroup we also give a bijection between the invariant permutations and certain symmetric signed permutations. Received September 14, 2006     

Proofs with monotone cuts

Atserias, Galesi, and Pudlák have shown that the monotone sequent calculus MLK quasipolynomially simulates proofs of monotone sequents in the full sequent calculus LK (or equivalently, in Frege systems). We generalize the simulation to the fragment MCLK of LK which can prove arbitrary sequents, but restricts cut‐formulas to be monotone. We also show that MLK as a refutation system for CNFs quasipolynomially simulates LK.     

Permutations with extremal number of fixed points

We extend Stanley's work on alternating permutations with extremal number of fixed points in two directions: first, alternating permutations are replaced by permutations with a prescribed descent set; second, instead of simply counting permutations we study their generating polynomials by number of excedances. Several techniques are used: Désarménien's desarrangement combinatorics, Gessel's hook-factorization and the analytical properties of two new permutation statistics “DEZ” and “lec.” Explicit formulas for the maximal case are derived by using symmetric function tools.     

Restricted Simsun Permutations

A permutation is simsun if for all k, the subword of the one-line notation consisting of the k smallest entries does not have three consecutive decreasing elements. Simsun permutations were introduced by Simion and Sundaram, who showed that they are counted by the Euler numbers. In this paper we enumerate simsun permutations avoiding a pattern or a set of patterns of length 3. The results involve Motkzin, Fibonacci, and secondary structure numbers. The techniques in the proofs include generating functions, bijections into lattice paths and generating trees.