Richard Stanley's two-volume basic introduction to enumerative combinatorics has become the standard guide to the topic for students and experts alike. This thoroughly revised second edition of ...volume two covers the composition of generating functions, in particular the exponential formula and the Lagrange inversion formula, labelled and unlabelled trees, algebraic, D-finite, and noncommutative generating functions, and symmetric functions. The chapter on symmetric functions provides the only available treatment of this subject suitable for an introductory graduate course and focusing on combinatorics, especially the Robinson-Schensted-Knuth algorithm. An appendix by Sergey Fomin covers some deeper aspects of symmetric functions, including jeu de taquin and the Littlewood-Richardson rule. The exercises in the book play a vital role in developing the material, and this second edition features over 400 exercises, including 159 new exercises on symmetric functions, all with solutions or references to solutions.
We enumerate cyclic permutations avoiding two patterns of length three each by providing explicit formulas for all but one of the pairs for which no such formulas were known. The pair (123, 231) ...proves to be the most difficult of these pairs. We also prove a lower bound for the growth rate of the number of cyclic permutations that avoid a single pattern q, where q is an element of a certain infinite family of patterns. Keywords: permutations, cycles, pattern avoidance, enumeration
In the
two-echelon capacitated vehicle routing problem
(2E-CVRP), the delivery to customers from a
depot
uses intermediate depots, called
satellites
. The 2E-CVRP involves two levels of routing ...problems. The first level requires a design of the routes for a vehicle fleet located at the depot to transport the customer demands to a subset of the satellites. The second level concerns the routing of a vehicle fleet located at the satellites to serve all customers from the satellites supplied from the depot. The objective is to minimize the sum of routing and handling costs. This paper describes a new mathematical formulation of the 2E-CVRP used to derive valid lower bounds and an exact method that decomposes the 2E-CVRP into a limited set of
multidepot capacitated vehicle routing problems
with side constraints. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods.
Complexity theory aims to understand and classify computational problems, especially decision problems, according to their inherent complexity. This book uses new techniques to expand the theory for ...use with counting problems. The authors present dichotomy classifications for broad classes of counting problems in the realm of P and NP. Classifications are proved for partition functions of spin systems, graph homomorphisms, constraint satisfaction problems, and Holant problems. The book assumes minimal prior knowledge of computational complexity theory, developing proof techniques as needed and gradually increasing the generality and abstraction of the theory. This volume presents the theory on the Boolean domain, and includes a thorough presentation of holographic algorithms, culminating in classifications of computational problems studied in exactly solvable models from statistical mechanics.
Computing directional distance functions for a free disposal hull (FDH) technology in general requires solving nonlinear mixed integer programs. Cherchye et al. (J Product Anal 15(3):201–215,
2001
) ...provide an enumeration algorithm for the FDH directional distance function in case of a variable returns to scale technology. In this contribution, we provide fast enumeration algorithms for the FDH directional distance functions under constant, nonincreasing, and nondecreasing returns to scale assumptions. Consequently, enumeration algorithms are now available for all commonly used returns to scale assumptions.
Self-focused attention refers to awareness of self-referent, internally generated information. It can be categorized into dysfunctional (i.e., self-rumination) and functional (self-reflection) ...aspects. According to theory on cognitive resource limitations (e.g., Moreno, 2006), there is a difference in cognitive resource allocation between these two aspects of self-focused attention. We propose a new task, self-relevant word (SRW) enumeration, that can aid in behaviorally identifying individuals' use of self-rumination and self-reflection. The present study has two purposes: to determine the association between self-focus and SRW enumeration, and to examine the effect of dysfunctional SRW enumeration on repetitive negative thinking. One hundred forty-six undergraduate students participated in this study. They completed a measure of state anxiety twice, before and after imagining a social failure situation. They also completed the SRW enumeration task, Repetitive Thinking Questionnaire, Short Fear of Negative Evaluation Scale, and Rumination-Reflection Questionnaire. A correlational analysis indicated a significant positive correlation between self-reflection and the number of SRWs. Furthermore, individuals high in self-reflection had a tendency to pay more attention to problems than did those high in self-rumination. A significant positive correlation was found between self-rumination and the strength of self-relevance of negative SRWs. Through a path analysis, we found a significant positive effect of the self-relevance of negative SRWs on repetitive negative thinking. Notably, however, the model that excluded self-rumination as an explanatory variable showed a better fit to the data than did the model that included it. In summary, SRW enumeration might enable selective and independent detection of the degree of self-reflection and self-rumination, and therefore should be examined in future research in order to design new behavioral procedures.
A trapezoidal number, a sum of at least two consecutive positive integers, is a figurate number that can be represented by points rearranged in the plane as a trapezoid. Such numbers have been of ...interest and extensively studied. In this paper, a generalization of trapezoidal numbers has been introduced. For each positive integer m, a positive integer N is called an m-trapezoidal number if N can be written as an arithmetic series of at least 2 terms with common difference m. Properties of m-trapezoidal numbers have been studied together with their trapezoidal representations. In the special case where m=2, the characterization and enumeration of such numbers have been given as well as illustrative examples. Precisely, for a fixed 2-trapezoidal number N, the ways and the number of ways to write N as an arithmetic series with common difference 2 have been determined. Some remarks on 3-trapezoidal numbers have been provided as well.
In this paper, we address the Uncapacitated Plant Cycle Location Problem. It is a location-routing problem aimed at determining a subset of locations to set up plants dedicated to serving customers. ...We propose a mathematical formulation to model the problem. The high computational burden required by the formulation when tackling large scenarios encourages us to develop a Greedy Randomized Adaptive Search Procedure with Probabilistic Learning Model. Its rationale is to divide the problem into two interconnected sub-problems. The computational results indicate the high performance of our proposal in terms of the quality of reported solutions and computational time. Specifically, we have overcome the best approach from the literature on a wide range of scenarios. KEYWORDS Greedy Randomized Adaptive Search Procedure, Probabilistic Learning Model, Uncapacitated Plant Cycle Location Problem.
Estimation is such an important yet sometimes overlooked skill. This article explores a dynamic approach to estimation, where students refine their estimates as they gain access to more information ...in a 'how many' investigation.
In this paper we address the problem of generating all elements obtained by the saturation of an initial set by some operations. More precisely, we prove that we can generate the closure of a boolean ...relation (a set of boolean vectors) by polymorphisms with a polynomial delay. Therefore we can compute with polynomial delay the closure of a family of sets by any set of "set operations": union, intersection, symmetric difference, subsets, supersets ...). To do so, we study the MEMBERSHIP.sub.F problem: for a set of operations F, decide whether an element belongs to the closure by F of a family of elements. In the boolean case, we prove that MEMBERSHIP.sub.F is in P for any set of boolean operations F. When the input vectors are over a domain larger than two elements, we prove that the generic enumeration method fails, since MEMBERSHIP.sub.F is NP-hard for some F. We also study the problem of generating minimal or maximal elements of closures and prove that some of them are related to well known enumeration problems such as the enumeration of the circuits of a matroid or the enumeration of maximal independent sets of a hypergraph. Keywords: enumeration, set saturation, incremental polynomial time, polynomial delay, Post's lattice, maximal independent sets
PDF
