A Generating Tree Approach to <Emphasis Type="Italic">k</Emphasis>-Nonnesting Partitions and Permutations

We describe a generating tree approach to the enumeration and exhaustive generation of k-nonnesting set partitions and permutations. Unlike previous work in the literature which uses the connections of these objects to Young tableaux and restricted lattice walks, our approach deals directly with partition and permutation diagrams. We provide explicit functional equations for the generating functions, with k as a parameter. Key to the solution is a superset of diagrams that permit semi-arcs. Many of the resulting counting sequences also count other well-known objects, such as Baxter permutations, and Young tableaux of bounded height.     

A state-space approach to quantum permutations

In this exposition of quantum permutation groups, an alternative to the ‘Gelfand picture’ of compact quantum groups is proposed. This point of view is inspired by algebraic quantum mechanics and interprets the states of an algebra of continuous functions on a quantum permutation group as quantum permutations. This interpretation allows talk of an element of a quantum permutation group, and allows a clear understanding of the difference between deterministic, random, and quantum permutations. The interpretation is illustrated by various quantum permutation group phenomena.     

Parity-alternating permutations and successions

The study of parity-alternating permutations of {1, 2, … n} is extended to permutations containing a prescribed number of parity successions — adjacent pairs of elements of the same parity. Several enumeration formulae are computed for permutations containing a given number of parity successions, in conjunction with further parity and length restrictions. The objects are classified using direct construction and elementary combinatorial techniques. Analogous results are derived for circular permutations.     

Reduced word manipulation: patterns and enumeration

We develop the technique of reduced word manipulation to give a range of results concerning reduced words and permutations more generally. We prove a broad connection between pattern containment and reduced words, which specializes to our previous work for vexillary permutations. We also analyze general tilings of Elnitsky’s polygon and demonstrate that these are closely related to the patterns in a permutation. Building on previous work for commutation classes, we show that reduced word enumeration is monotonically increasing with respect to pattern containment. Finally, we give several applications of this work. We show that a permutation and a pattern have equally many reduced words if and only if they have the same length (equivalently, the same number of 21-patterns) and that they have equally many commutation classes if and only if they have the same number of 321-patterns. We also apply our techniques to enumeration problems of pattern avoidance and give a bijection between 132-avoiding permutations of a given length and partitions of that same size, as well as refinements of these data and a connection to the Catalan numbers.     

Restricted words by adjacencies

A recurrence, a determinant formula, and generating functions are presented for enumerating words with restricted letters by adjacencies. The main theorem leads to refinements (with up to two additional parameters) of known results on compositions, polyominoes, and permutations. Among the examples considered are (1) the introduction of the ascent variation on compositions, (2) the enumeration of directed vertically convex polyominoes by upper descents, area, perimeter, relative height, and column number, (3) a tri-variate extension of MacMahon's determinant formula for permutations with prescribed descent set, and (4) a combinatorial setting for an entire sequence of bibasic Bessel functions.     

A Logarithmic Connection for Circular Permutation Enumeration

A general theorem is obtained for the enumeration of permutations equivalent under cyclic rotation. This result gives the generating function as the logarithm of a determinant which arises in the enumeration of a related linear permutation enumeration. Applications of this theorem are given to a number of classical enumerative problems.     

一些组合地图新算法的实现

本文主要讨论组合地图列举问题.刘的一部专著中提出了一个判定两个地图是否同构的算法.该算法的时间复杂度为O(m2),其中m为下图的规模.在此基础上,本文给出一个用于地图列举以及进而计算任意连通下图的地图亏格分布的通用算法.本文所得结果比之前文献中所给结果更优.     

The research and progress of the enumeration of lattice paths

The enumeration of lattice paths is an important counting model in enumerative combinatorics. Because it can provide powerful methods and technical support in the study of discrete structural objects in different disciplines, it has attracted much attention and is a hot research field. In this paper, we summarize two kinds of the lattice path counting models that are single lattice paths and family of nonintersecting lattice paths and their applications in terms of the change of dimensions, steps, constrained conditions, the positions of starting and end points, and so on. (1) The progress of classical lattice path such as Dyck lattice is introduced. (2) A method to study the enumeration of lattice paths problem by generating function is introduced. (3) Some methods of studying the enumeration of lattice paths problem by matrix are introduced. (4) The family of lattice paths problem and some counting methods are introduced. (5) Some applications of family of lattice paths in symmetric function theory are introduced, and a related open problem is proposed.     

Enumeration of unrooted hypermaps of a given genus

In this paper we derive an enumeration formula for the number of hypermaps of a given genus g and given number of darts n in terms of the numbers of rooted hypermaps of genus γ≤g with m darts, where m|n. Explicit expressions for the number of rooted hypermaps of genus g with n darts were derived by Walsh [T.R.S. Walsh, Hypermaps versus bipartite maps, J. Combin. Theory B 18 (2) (1975) 155-163] for g=0, and by Arquès [D. Arquès, Hypercartes pointées sur le tore: Décompositions et dénombrements, J. Combin. Theory B 43 (1987) 275-286] for g=1. We apply our general counting formula to derive explicit expressions for the number of unrooted spherical hypermaps and for the number of unrooted toroidal hypermaps with given number of darts. We note that in this paper isomorphism classes of hypermaps of genus g≥0 are distinguished up to the action of orientation-preserving hypermap isomorphisms. The enumeration results can be expressed in terms of Fuchsian groups.     

The enumeration of irreducible combinatorial objects

A unique factorization theory for labelled combinatorial objects is developed and applied to enumerate several families of objects, including certain families of set partitions, permutations, graphs, and collections of subintervals of [1, n]. The theory involves a notion of irreducibility with respect to set partitions and the enumeration formulas that arise result from a generalization of the well-known “exponential formula.”     

Asymptotic behaviour of the containment of certain mesh patterns

We present some results on the proportion of permutations of length n containing certain mesh patterns as n grows large, and give exact enumeration results in some cases. In particular, we focus on mesh patterns where entire rows and columns are shaded. We prove some general results which apply to mesh patterns of any length, and then consider mesh patterns of length four. An important consequence of these results is to show that the proportion of permutations containing a mesh pattern can take a wide range of values between 0 and 1.     

An Enumeration of Binary Self-Dual Codes of Length 32

A binary self-dual code of length 2k is a (2k, k) binary linear code C with the property that every pair of codewords in C are orthogonal. Two self-dual codes, C ₁ and C ₂, are equivalent if and only if there is a permutation of the coordinates of C ₁ that takes C ₁ into C ₂. The automorphism group of a binary code C is the set of all permutations of the coordinates of C that takes C into itself.The main topic of this paper is the enumeration of inequivalent binary self-dual codes. We have developed algorithms that will take lists of inequivalent small codes and produce lists of larger codes where each inequivalent code occurs only a few times. We have defined a canonical form for codes that allowed us to eliminate the overenumeration. So we have lists of inequivalent binary self-dual codes of length up to 32. The enumeration of the length 32 codes is new. Our algorithm also finds the size of the automorphism group so that we can compute the number of distinct binary self-dual codes for a specific length. This number can also be found by counting and matches our total.     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

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.     

Neural correlates of counting large numerosity

The mastery of counting numerosities larger than those correctly estimated by infants or non-human species is an important foundation for the development of higher level calculation skills. The cognitive processes involved in counting are related to spatial attention, language, and number processing. However, the respective involvement of language- and/or visuo-spatial-based brain systems during counting is still under debate. In the present functional magnetic resonance imaging study, we asked 27 right-handed participants to perform an enumeration task on visual arrays of bars that varied in numerosity. Each enumeration condition was contrasted to a color-detection condition that was numerically and spatially matched to the counting condition. The results showed a behavioral discontinuity in response time slopes between large (6–10) and small (1–5) numerosities during enumeration, suggesting that during large enumeration, participants engaged counting processes. Comparing brain regional activity during the enumeration of large numerosity to the enumeration of smaller numerosity, we found increased activation in the bilateral fronto-parietal attentional network, the inferior parietal gyri/intraparietal sulci, and the left ventral premotor and left inferior temporal areas. These results indicated that in adults who master enumeration, counting more than five items requires the strong involvement of spatial attention and eye movements, as well as numerical magnitude processes. Counting large numerosity also recruited verbal working memory areas, subtending a subvocal articulatory code and a visual representation of numbers.     

Generic rectangulations

A rectangulation is a tiling of a rectangle by a finite number of rectangles. The rectangulation is called generic if no four of its rectangles share a single corner. We initiate the enumeration of generic rectangulations up to combinatorial equivalence by establishing an explicit bijection between generic rectangulations and a set of permutations defined by a pattern-avoidance condition analogous to the definition of the twisted Baxter permutations.     

A Problem in Permutations: the Game of 'Mousetrap'

The game of 'Mousetrap, a problem in permutations, first introduced by Arthur Cayley in 1857 and independently addressed by Cayley and Adolph Steen in 1878, has been largely unexamined since. The game involves permutations of n cards numbered consecutively from 1 to n. The cards are laid out face up in some order and the game is played by counting on the cards, beginning the count with 1. If at any time the number of the count matches the number on the card, this is called a hit and the card is thrown out. The counting begins again with 1 on the next card and returns to the first card when the nth card is reached. Each time a card is hit, that card is removed and the counting starts over at 1. The game continues until all the cards have been hit and thrown out (the player wins) or until the counting reaches n with no cards having been hit (the cards win). The game is re-introduced here and a summary of both Cayley's and Steen's work is presented. Computer programs, written to generate the types of permutations dealt with by Steen, uncovered discrepancies in his work. Further examination of these discrepancies lead to the discovery of a combinatorial pattern of coefficients which Steen was unable to recognize because of his computational errors. Corrected versions of Steen's erroneous formulas are presented.     

On summing permutations and some statistical properties

A closed form expression is obtained for the sum of all permutations of n objects taken r at a time. The average and variance of the permutations are derived and are shown to be proportional to the average and variance of the objects themselves. The proportionality constant is a function of only r, n and the base b and is independent of the actual objects considered. Previous results aimed at determining the sum of permutations are shown to be very specific cases of the current development.     

Stories about Groups and Sequences

The main theme of this article is that counting orbitsof an infinite permutation group on finite subsets or tuplesis very closely related to combinatorial enumeration; this pointof view ties together various disparate ``stories'. Among theseare reconstruction problems, the relation between connected andarbitrary graphs, the enumeration of N-free posets, and someof the combinatorics of Stirling numbers.     

A generalized activity network model

In recent years activity networks for projects with both random and deterministic alternative outcomes in key nodes have been considered. The developed control algorithm chooses an optimal outcome direction at every deterministic alternative node which is reached in the course of the project's realization. At each routine decision-making node, the algorithm singles out all the subnetworks (the so-called joint variants) which correspond to all possible outcomes from that node. Decision-making results in determining the optimal joint variant and following the optimal direction up to the next decision-making node. However, such models cover a limited class of alternative networks, namely, only fully-divisible networks which can be subdivided into nonintersecting fragments. In this paper, a more generalized activity network is considered. The model can be applied to a broader spectrum of R&D projects and can be used for all types of alternative networks, for example, for non-divisible networks comprising nodes with simultaneously ‘must follow’, random ‘exclusive OR’ and deterministic ‘exclusive or’ emitters. The branching activities of the third type refer to decision-making outcomes; choosing the optimal outcome is the sole prerogative of the project's management. Such a model is a more universal activity network; we will call it GAAN—Generalized Alternative Activity Network. The problem is to determine the joint variant optimizing the mean value of the objective function subject to restricted mean values of several other criteria. We will prove that such a problem is a NP-complete one. Thus, in general, the exact solution of the problem may be obtained only by looking through all the joint variants on the basis of their proper enumeration. To enumerate the joint variants we will use the lexicographical method in combination with some techniques of discrete optimization. A numerical example will be presented. Various application areas are considered.