The Enumeration of Maximally Clustered Permutations

The maximally clustered permutations are characterized by avoiding the classical permutation patterns {3421, 4312, 4321}. This class contains the freely braided permutations and the fully commutative permutations. In this work, we show that the generating functions for certain fully commutative pattern classes can be transformed to give generating functions for the corresponding freely braided and maximally clustered pattern classes. Moreover, this transformation of generating functions is rational. As a result, we obtain enumerative formulas for the pattern classes mentioned above as well as the corresponding hexagon-avoiding pattern classes where the hexagon-avoiding permutations are characterized by avoiding {46718235, 46781235, 56718234, 56781234}.     

The Enumeration of Permutations Avoiding 3124 and 4312

Annals of Combinatorics - We find the generating function for the class of all permutations that avoid the patterns 3124 and 4312 by showing that it is an inflation of the union of two geometric...     

Permutations via linear translators

We show that many infinite classes of permutations over finite fields can be constructed via translators with a large choice of parameters. We first characterize some functions having linear translators, based on which several families of permutations are then derived. Extending the results of [9], we give in several cases the compositional inverse of these permutations. The connection with complete permutations is also utilized to provide further infinite classes of permutations. Moreover, we propose new tools to study permutations of the form $x\mapsto x+{(x^{p^m}-x+\delta )}^s$ and a few infinite classes of permutations of this form are proposed.     

Enumeration of Bigrassmannian Permutations Below a Permutation in Bruhat Order

In theory of Coxeter groups, bigrassmannian elements are well known as elements which have precisely one left descent and precisely one right descent. In this article, we prove formulas on enumeration of bigrassmannian permutations weakly below a permutation in Bruhat order in the symmetric groups. For the proof, we use equivalent characterizations of bigrassmannian permutations by Lascoux-Schützenberger and Reading.     

Polyominoes tiling by a genetic algorithm

Most existing placement algorithms were designed to handle blocks that are rectangular in shape. In this paper, we show how a genetic algorithm (GA) is used to construct an optimal arrangement of two-dimensional rectilinear blocks. Our approach does not require the orientation of each block to be fixed. To transform the placement problem to a GA problem, we devised a decoding technique known as circular placement. The novelty of the circular placement technique is that it configures the rectilinear blocks by building up potentially good groupings of blocks starting from the corners of the placement area. To complement the circular placement approach, we present a methodology for deriving a suitable objective function. We confirm the performance of our GA-based placement algorithm by presenting simulation results of some problems on tiling with up to 128 polyominoes. The algorithm described in this paper has great potential for applications in packing, compacting and general component placement in the various disciplines of engineering.     

Enumeration via ballot numbers

Several interesting combinatorial coefficients such as the Catalan numbers and the Bell numbers can be described either via a 3-term recurrence or as sums of (weighted) ballot numbers. This paper gives some general results connecting 3-term recurrences with ballot sequences with several applications to the enumeration of various combinatorial instances.     

Refined Enumeration of Permutations Sorted with Two Stacks and a D 8-Symmetry

We study permutations that are sorted by operators of the form S ° α ° S, where S is the usual stack sorting operator introduced by Knuth and α is any D ₈-symmetry obtained by combining the classical reverse, complement, and inverse operations. Such permutations can be characterized by excluded (generalized) patterns. Some conjectures about the enumeration of these permutations, refined with numerous classical statistics, have been proposed by Claesson, Dukes, and Steingrímsson. We prove these conjectures, and enrich one of them with a few more statistics. The proofs mostly rely on generating trees techniques, and on a recent bijection of Giraudo between Baxter and twisted Baxter permutations.     

Exact Enumeration of 1342-Avoiding Permutations: A Close Link with Labeled Trees and Planar Maps

Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating functionH(x) of all 1342-avoiding permutations of lengthnas well as anexactformula for their numberS_n(1342). While achieving this, we bijectively prove that the number of indecomposable 1342-avoiding permutations of lengthnequals that of labeled plane trees of a certain type onnvertices recently enumerated by Cori, Jacquard, and Schaeffer, which is in turn known to be equal to the number of rooted bicubic maps enumerated by Tutte (Can. J. Math.33(1963), 249–271). Moreover,H(x) turns out to be algebraic, proving the first nonmonotonic, longer-than-three instance of a conjecture of Noonan and Zeilberger (Adv. Appl. Math.17(1996), 381–407). We also prove thatconverges to 8, so in particular, lim_n→∞(S_n(1342)/S_n(1234))=0.     

Enumeration of nilpotent loops via cohomology

The isomorphism problem for centrally nilpotent loops can be tackled by methods of cohomology. We develop tools based on cohomology and linear algebra that either lend themselves to direct count of the isomorphism classes (notably in the case of nilpotent loops of order 2q, q a prime), or lead to efficient classification computer programs. This allows us to enumerate all nilpotent loops of order less than 24.     

Varieties Defined by Permutations

We continue to study interrelations between permutative varieties and the cyclic varieties defined by cycles of the form . A criterion is given determining whether a cyclic variety is interpretable in . For a permutation without fixed elements, it is stated that a set of primes for which is interpretable in in the lattice is finite. It is also proved that for distinct primes , the Helly number of a type in coincides with dimension of the dual type and equals .     

Counting Simsun Permutations by Descents

We count in the present work simsun permutations of length n by their number of descents. Properties studied include the recurrence relation and real-rootedness of the generating function of the number of n-simsun permutations with k descents. By means of generating function arguments, we show that the descent number is equidistributed over n-simsun permutations and n-André permutations. We also compute the mean and variance of the random variable X _n taking values the descent number of random n-simsun permutations, and deduce that the distribution of descents over random simsun permutations of length n satisfies a central and a local limit theorem as n ?? +???.     

The Enumeration of Permutations with a Prescribed Number of “Forbidden” Patterns

We initiate a general approach for the fast enumeration of permutations with a prescribed number of occurrences of “forbidden” patterns that seems to indicate that the enumerating sequence is always P-recursive. We illustrate the method completely in terms of the patterns “abc,” “cab,” and “abcd.”     

2-Binary trees: Bijections and related issues

A 2-binary tree is a binary rooted tree whose root is colored black and the other vertices are either black or white. We present several bijections concerning different types of 2-binary trees as well as other combinatorial structures such as ternary trees, non-crossing trees, Schröder paths, Motzkin paths and Dyck paths. We also obtain a number of enumeration results with respect to certain statistics.     

Permutations Generated by Stacks and Deques

Lower and upper bounds are given for the the number of permutations of length n generated by two stacks in series, two stacks in parallel, and a general deque.     

Enumeration by kernel positions

We introduce a class of two-player games on posets with a rank function, in which each move of the winning strategy is unique. This allows one to enumerate the kernel positions by rank. The main example is a simple game on words in which the number of kernel positions of rank n is a signed factorial multiple of the nth Bernoulli number of the second kind. Generalizations to the degenerate Bernoulli numbers and to negative integer substitutions into the Bernoulli polynomials are developed. Using an appropriate scoring system for each function with an appropriate Newton expansion we construct a game in which the expected gain of a player equals the definite integral of the function on the interval [0,1].     

Permutations and words counted by consecutive patterns

Generating functions which count occurrences of consecutive sequences in a permutation or a word which matches a given pattern are studied by exploiting the combinatorics associated with symmetric functions. Our theorems take the generating function for the number of permutations which do not contain a certain pattern and give generating functions refining permutations by the both the total number of pattern matches and the number of non-overlapping pattern matches. Our methods allow us to give new proofs of several previously recorded results on this topic as well as to prove new extensions and new q-analogues of such results.     

Permutations and words counted by consecutive patterns

Generating functions which count occurrences of consecutive sequences in a permutation or a word which matches a given pattern are studied by exploiting the combinatorics associated with symmetric functions. Our theorems take the generating function for the number of permutations which do not contain a certain pattern and give generating functions refining permutations by the both the total number of pattern matches and the number of non-overlapping pattern matches. Our methods allow us to give new proofs of several previously recorded results on this topic as well as to prove new extensions and new q-analogues of such results.     

On the Construction of Permutation Arrays via Mappings from Binary Vectors to Permutations

An (n, d, k)-mapping f is a mapping from binary vectors of length n to permutations of length n + k such that for all x, y {0,1}ⁿ, d_H (f(x), f(y)) ≥ d_H (x, y) + d, if d_H (x, y) ≤ (n + k) − d and d_H (f(x), f(y)) = n + k, if d_H (x, y) > (n + k) − d. In this paper, we construct an (n,3,2)-mapping for any positive integer n ≥ 6. An (n, r)-permutation array is a permutation array of length n and any two permutations of which have Hamming distance at least r. Let P(n, r) denote the maximum size of an (n, r)-permutation array and A(n, r) denote the same setting for binary codes. Applying (n,3,2)-mappings to the design of permutation array, we can construct an efficient permutation array (easy to encode and decode) with better code rate than previous results [Chang (2005). IEEE Trans inf theory 51:359–365, Chang et al. (2003). IEEE Trans Inf Theory 49:1054–1059; Huang et al. (submitted)]. More precisely, we obtain that, for n ≥ 8, P(n, r) ≥ A(n − 2, r − 3) > A(n − 1,r − 2) = A(n, r − 1) when n is even and P(n, r) ≥ A(n − 2, r − 3) = A(n − 1, r − 2) > A(n, r − 1) when n is odd. This improves the best bound A(n − 1,r − 2) so far [Huang et al. (submitted)] for n ≥ 8. The work was supported in part by the National Science Council of Taiwan under contract NSC-93-2213-E-009-117     

Enumeration of trees by inversions

Mallows and Riordan “The Inversion Enumerator for Labeled Trees,” Bulletin of the American Mathematics Society, vol. 74 [1968] pp. 92-94) first defined the inversion polynomial, J_n(q) for trees with n vertices and found its generating function. In the present work, we define inversion polynomials for ordered, plane, and cyclic trees, and find their values at q = 0, ± 1. Our techniques involve the use of generating functions (including Lagrange inversion), hypergeometric series, and binomial coefficient identities, induction, and bijections. We also derive asymptotic formulae for those results for which we do not have a closed form. © 1995 John Wiley & Sons, Inc.