Search

We correct typographical errors in our original paper.

We investigate permutations and involutions that avoid a pattern of length three and have a unique longest increasing subsequence (ULIS). We prove an explicit formula for 231-avoiders, we show that the growth rate for 321-avoiding permutations with a ULIS is 4, and prove that their generating function is not rational. We relate the case of 132-avoiders to the existing literature, raising some interesting questions. For involutions, we construct a bijection between 132-avoiding involutions with a ULIS and bidirectional ballot sequences.

A random binary search tree grown from the uniformly random permutation of $[n]$ is studied. We analyze the exact and asymptotic counts of vertices by rank, the distance from the set of leaves. The asymptotic fraction $c_k$ of vertices of a fixed rank $k\ge 0$ is shown to decay exponentially with $k$. Notoriously hard to compute, the exact fractions $c_k$ had been determined for $k\le 3$ only. We computed $c_4$ and $c_5$ as well; both are ratios of enormous integers, denominator of $c_5$ being $274$ digits long. Prompted by the data, we proved that, in sharp contrast, the largest prime divisor of $c_k$'s denominator is $2^{k+1}+1$ at most. We conjecture that, in fact, the prime divisors of every denominator for $k>1$ form a single interval, from $2$ to the largest prime not exceeding $2^{k+1}+1$., 28 pages

We consider two varieties of labeled rooted trees, namely non-plane and plane 1-2 trees. In these tree varieties, we study the probability that a vertex chosen from all vertices of all trees of a given size uniformly at random has a given rank. We prove that this probability converges to a limit as the tree size goes to infinity.

We use stack words to find a new, simple proof for the best known upper bound for the number of 3-stack sortable permutations of a given length. This is the first time that stack words are used to obtain such a result., Comment: 6 pages

We show that for every $k$, the probability that a randomly selected vertex of a random binary search tree on $n$ nodes is at distance $k-1$ from the closest leaf converges to a rational constant $c_k$ as $n$ goes to infinity., 12 pages 1 figure

This paper motivates and sets up the mathematical framework for a new program of investigation: to isolate and clarify the precise influence of symmetry on the probability space of assembly pathways that successfully lead to icosahedral viral shells. Several tractable open questions are posed. Besides its virology motivation, the topic is of independent mathematical interest for studying constructions of symmetric polyhedra. Preliminary results are presented: a natural, structural classification of subsets of facets ofT= 1 polyhedra, based on their stabilizing subgroups of the icosahedral group; and a theorem that uses symmetry to formalize why increasing depth increases the numeracy (and hence probability) of an assembly pathway type (or symmetry class) for aT= 1 viral shell.

We present a method that provides very simple proofs for some instances of the Stanley–Wilf conjecture. Some of these instances had been proved before by much more complicated arguments, and some others are new.

For each n, we construct a simplicial complex whose k-dimensional faces are in one-to-one correspondence with 2-stack sortable permutations of length n having k ascents.

We prove that the probability p2(n) that a random permutation of length n has a square root is monotonically nonincreasing in n. More generally, we prove that the probability pr(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 pr(n)0 as n∞. While doing this, we combinatorially prove that pr(n)=pr(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, pr(n)0 as n∞. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 157–167, 2000

The purpose of this paper is to enumerate various classes of cyclically colored m-gonal plane cacti, called m-ary cacti. This combinatorial problem is motivated by the topological classification of complex polynomials having at most m critical values, studied by Zvonkin and others. We obtain explicit formulae for both labelled and unlabelled m-ary cacti, according to i) the number of polygons, ii) the vertex-color distribution, iii) the vertex-degree distribution of each color. We also enumerate m-ary cacti according to the order of their automorphism group. Using a generalization of Otter's formula, we express the species of m-ary cacti in terms of rooted and of pointed cacti. A variant of the m-dimensional Lagrange inversion is then used to enumerate these structures. The method of Liskovets for the enumeration of unrooted planar maps can also be adapted to m-ary cacti., Comment: LaTeX2e, 28 pages, 9 figures (eps), 3 tables

Proving a first nontrivial instance of a conjecture of Noonan and Zeilberger we show that the numberSr(n) of permutations of lengthncontaining exactlyrsubsequences of type 132 is aP-recursive function ofn. We show that this remains true even if we impose some restrictions on the permutations. We also show the stronger statement that the ordinary generating functionGr(x) ofSr(n) is algebraic, in fact, it is rational in the variablesxand1−4x. We use this information to show that the degree of the polynomial recursion satisfied bySr(n) isr.

We prove that the number of 1324-avoiding permutations of length n is less than (7+4\sqrt{3})^n., 6 pages

Motivated by the question of how macromolecules assemble, the notion of an {\it assembly tree} of a graph is introduced. Given a graph $G$, the paper is concerned with enumerating the number of assembly trees of $G$, a problem that applies to the macromolecular assembly problem. Explicit formulas or generating functions are provided for the number of assembly trees of several families of graphs, in particular for what we call $(H,\phi)$-graphs. In some natural special cases, we apply powerful recent results of Zeilberger and Apagodu on multivariate generating functions, and results of Wimp and Zeilberger, to deduce recurrence relations and very precise asymptotic formulas for the number of assembly trees of the complete bipartite graphs $K_{n,n}$ and the complete tripartite graphs $K_{n,n,n}$. Future directions for reseach, as well as open questions, are suggested., Comment: 17 pages, 5 figures

We prove that the total number $S_{n,132}(q)$ of copies of the pattern $q$ in all 132-avoiding permutations of length $n$ is the same for $q=231$, $q=312$, or $q=213$. We provide a combinatorial proof for this unexpected threefold symmetry. We then significantly generalize this result by proving a large family of non-trivial equalities of the type $S_{n,132}(q)=S_{n,132}(q')$.

We use Janson's dependency criterion to prove that the distribution of $d$-descents of permutations of length $n$ converge to a normal distribution as $n$ goes to infinity. We show that this remains true even if $d$ is allowed to grow with $n$, up to a certain degree., Comment: 7 pages

We prove an interesting fact describing the location of the roots of the generating polynomials of the numbers of derangements of length $n$, counted by their number of cycles. We then use this result to prove that if $k$ is the number of cycles of a randomly selected derangement of length $n$, then the probability that $k$ is congruent to a given $r$ modulo a given $q$ converges to $1/q$. Finally, we generalize our results to $a$-derangements, which are permutations in which each cycle is longer than $a$.

We enumerate weighted graphs with a certain upper bound condition. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that if the given graph is a bipartite graph, then its generating function is of the form $\frac{p(x)}{(1-x)^{m+1}}$, where $m$ is the number of vertices of the graph and $p(x)$ is a polynomial of degree at most $m$., Comment: 25 pages

We provide a combinatorial proof for the fact that for any fixed $n$, the sequence $\{i(n,k)\}_{0\leq k\leq {n\choose 2}}$ of the numbers of permutations of length $n$ having $k$ inversions is log-concave.

We review the various ways that stacks, their variations and their combinations, have been used as sorting devices. In particular, we show that they have been a key motivator for the study of permutation patterns. We also show that they have connections to other areas in combinatorics such as Young tableau, planar graph theory, and simplicial complexes.

Consider the number of permutations in the symmetric group on n letters that contain c copies of a given pattern. As c varies (with n held fixed) these numbers form a sequence whose properties we study for the monotone patterns and the patterns 1, l, l-1, ..., 2. We show that, except for the patterns 1, 2 and 2, 1 where the sequence is well-known to be log concave, there are infinitely many n where the sequence has internal zeros., Comment: 24 pages

We constructively prove that the partially ordered set of finite permutations ordered by deletion of entries contains an infinite antichain. In other words, there exists an infinite collection of permutations no one of which contains another as a pattern.

We determine all permutation classes defined by pattern avoidance which are equinumerous to the class of permutations whose Schubert variety is smooth. We also provide a lattice path interpretation for the numbers of such permutations.

Answering a question of Wilf, we show that if $n$ is sufficiently large, then one cannot cover an $n \times p(n)$ rectangle using each of the $p(n)$ distinct Ferrers shapes of size $n$ exactly once. Moreover, the maximum number of pairwise distinct, non-overlapping Ferrers shapes that can be packed in such a rectangle is only $\Theta(p(n)/ \log n).$, Comment: 7 pages, 4 figures