ENUMERATIONS OF ONE-VERTEX MAPS WITH FACE PARTITION ON THE PLANE

In addition to the known method given in [1],authors provide other three methods to the enumeration of one-vertex maps with face partition on the plane.Correspondingly,there are four functional equations in the enufuntion .It is shown that the four equations are equivalent.Moreover,an explicit expression of the solution is found by expanding the powers of the matrix of infinite order directly.This is a new complement of what appeared in [1].     

Enumeration of cyclic graphs and cyclic designs

The close relationship of cyclic graphs and cyclic designs is pointed out and used in the enumeration of cyclic graphs. An explicit formula is given for graphs with a prime number of vertices and a general constructive method of enumeration is developed. The problem is shown to be the same as that of enumerating cyclic paired-comparison designs which was previously considered by the author. The earlier results are extended and modified.     

Decomposed enumeration of extreme points in the linear programming problem

In this paper we consider the problem of enumeration of extreme points in the linear programming problem when the matrix is of block-angular type. It is shown how decomposition methods can be used. Finally application of decomposed enumeration to the problem of computing equilibrium prices in a capital market network is given as an example.     

Fuzzy logic, continuity and effectiveness

 It is shown the complete equivalence between the theory of continuous (enumeration) fuzzy closure operators and the theory of (effective) fuzzy deduction systems in Hilbert style. Moreover, it is proven that any truth-functional semantics whose connectives are interpreted in [0,1] by continuous functions is axiomatizable by a fuzzy deduction system (but not by an effective fuzzy deduction system, in general). Received: 15 February 2001 / Revised version: 31 May 2001 / Published online: 12 July 2002     

A Formal Calculus for the Enumerative System of Sequences—III. Further Developments

We use the material of Parts I and II to obtain further results in sequence enumeration. These include the enumeration of sequences with respect to both maximal π₁ and π₂-paths, and the enumeration of sequences with distinguished substrings. We use the material to derive an enumerative proof of a generalization of a result of Foata and Schützenberger. Finally, we reconsider the enumeration of permutations with periodic pattern and show that the required generating function may be exhibited as the solution of a set of first-order nonlinear differential equations. Subsequent work has shown these to be matrix Riccati equations, although we refer to them here as Volterra equations.     

On the complexity of the dualization problem

The computational complexity of discrete problems concerning the enumeration of solutions is addressed. The concept of an asymptotically efficient algorithm is introduced for the dualization problem, which is formulated as the problem of constructing irreducible coverings of a Boolean matrix. This concept imposes weaker constraints on the number of “redundant” algorithmic steps as compared with the previously introduced concept of an asymptotically optimal algorithm. When the number of rows in a Boolean matrix is no less than the number of columns (in which case asymptotically optimal algorithms for the problem fail to be constructed), algorithms based on the polynomialtime-delay enumeration of “compatible” sets of columns of the matrix is shown to be asymptotically efficient. A similar result is obtained for the problem of searching for maximal conjunctions of a monotone Boolean function defined by a conjunctive normal form.     

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

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

Enumeration problems for classes of self-similar graphs

We describe a general construction principle for a class of self-similar graphs. For various enumeration problems, we show that this construction leads to polynomial systems of recurrences and provide methods to solve these recurrences asymptotically. This is shown for different examples involving classical self-similar graphs such as the Sierpiński graphs. The enumeration problems we investigate include counting independent subsets, matchings and connected subsets.     

Genetic algorithms applied to the solution of hybrid optimal control problems in astrodynamics

Many space mission planning problems may be formulated as hybrid optimal control problems, i.e. problems that include both continuous-valued variables and categorical (binary) variables. There may be thousands to millions of possible solutions; a current practice is to pre-prune the categorical state space to limit the number of possible missions to a number that may be evaluated via total enumeration. Of course this risks pruning away the optimal solution. The method developed here avoids the need for pre-pruning by incorporating a new solution approach using nested genetic algorithms; an outer-loop genetic algorithm that optimizes the categorical variable sequence and an inner-loop genetic algorithm that can use either a shape-based approximation or a Lambert problem solver to quickly locate near-optimal solutions and return the cost to the outer-loop genetic algorithm. This solution technique is tested on three asteroid tour missions of increasing complexity and is shown to yield near-optimal, and possibly optimal, missions in many fewer evaluations than total enumeration would require.     

Schensted Algorithms for Dual Graded Graphs

This paper is a sequel to [3]. We keep the notation and terminology and extend the numbering of sections, propositions, and formulae of [3].The main result of this paper is a generalization of the Robinson-Schensted correspondence to the class of dual graded graphs introduced in [3], This class extends the class of Y-graphs, or differential posets [22], for which a generalized Schensted correspondence was constructed earlier in [2].The main construction leads to unified bijective proofs of various identities related to path counting, including those obtained in [3]. It is also applied to permutation enumeration, including rook placements on Ferrers boards and enumeration of involutions.As particular cases of the general construction, we re-derive the classical algorithm of Robinson, Schensted, and Knuth [19, 12], the Sagan-Stanley [18], Sagan-Worley [16, 29] and Haiman's [11] algorithms and the author's algorithm for the Young-Fibonacci graph [2]. Some new applications are suggested.The rim hook correspondence of Stanton and White [23] and Viennot's bijection [28] are also special cases of the general construction of this paper.In [5], the results of this paper and the previous paper [3] were presented in a form of extended abstract.     

Arithmetical Semigroups Related to Trees and Polyhedra,II — Maps on Surfaces

This paper extends recent investigations by Arnold Knopfmacher and John Knopfmacher [10] of asymptotic enumeration questions concerning finite graphs, trees and polyhedra. The present emphasis is on the counting of non‐isomorphic maps of not necessarily connected finite graphs on arbitrary surfaces. A significant aid towards this goal is provided by an extended abstract prime number theorem, based partly on more delicate tools of analysis due to W. K. Hayman [8].     

Bilabelled increasing trees and hook-length formulae

We introduce two different kinds of increasing bilabellings of trees, for which we provide enumeration formulae. One of the bilabelled tree families considered is enumerated by the reduced tangent numbers and is in bijection with a tree family introduced by Poupard [11]. Both increasing bilabellings naturally lead to hook-length formulae for trees and forests; in particular, one construction gives a combinatorial interpretation of a formula for labelled unordered forests obtained recently by Chen et al. [1].     

Computing Linear Codes and Unitals

The 2-rank of any 2-(28,4,1) design (unital on 28 points) is known to be between 19 and 27. It is shown by the enumeration and analysis of certain binary linear codes that there are no unitals of 2-rank 20, and that there are exactly 4 isomorphism classes of unitals of 2-rank 21. Combined with previous results, this completes the classification of unitals on 28 points of 2-rank less than 22.     

Zero-one programming with many variables and few constraints

One of the more successful techniques for solving zero-one integer programs has been the implicit enumeration strategy first introduced by E. Balas. However, experience has shown that the efficiency of these enumerative techniques depends critically upon the bumber of variables. In this paper an algorithm is developed and computational experience provided for solving zero-one integer programs with many variables and few constraints. Sub-problems solved via implicit enumeration are generated from the linear programming relaxation and the variables in these sub-problems correspond to the fractional variables obtained in the linear program. Since the number of fractional variables in the linear program is bounded by the number of constraints in the linear program, the sub-problems will in general contain many fewer variables than the original zero-one integer program.     

Some set partition statistics in non-crossing partitions and generating functions

In this paper we shall give the generating functions for the enumeration of non-crossing partitions according to some set partition statistics explicitly, which are based on whether a block is singleton or not and is inner or outer. Using weighted Motzkin paths, we find the continued fraction form of the generating functions. There are bijections between non-crossing partitions, Dyck paths and non-nesting partitions, hence we can find applications in the enumeration of Dyck paths and non-nesting partitions. We shall also study the integral representation of the enumerating polynomials for our statistics. As an application of integral representation, we shall give some remarks on the enumeration of inner singletons in non-crossing partitions, which is equivalent to one of udu's at high level in Dyck paths investigated in [Y. Sun, The statistic “number of udu's” in Dyck paths, Discrete Math. 284 (2004) 177-186].     

The Computational Implications of Variations in State Variable/State Ratios in Dynamic Programming and Total Enumeration

Dynamic programming computational efficiency rests upon the so-called principle of optimality, where it is possible to decompose combinatorial problems into individual sub-problems (stages). The sub-problems are solved independently and linked together through the use of the state variables which reflect optimal decisions for other (preceding) stages.A class of combinatorial problems which poses a particularly difficult challenge to dynamic programming methods is that which requires that decisions made in a given stage reflect the accumulation of decisions made in multiple preceding stages. It is generally accepted that such an increase in state space dimension is affected by computer storage limitations. In addition, it can be shown that such a problem structure can cause a dynamic-programming methodology to be inferior from the point of view of computation time as well.This phenomenon is demonstrated by varying the number of preceding stages whose decisions affect the pay-off determination for a given stage in five inventory models and solving the problems by both dynamic programming and total enumeration. In addition, a comparison of computational requirements to solve a problem of practical magnitude is presented. Computational results confirm that, owing to the nature of the interaction between overlapping shift schedules, total enumeration was superior to dynamic programming and branch-and-bound integer programming for a bank-clerk scheduling problem.     

Enumeration of maps on the projective plane

1. IntroductionA lnap is rooted if an edge is distinguished togetl1er with an end and a side of the edge.An edge belo11ging to only one face is called double (or 8ingular by some author), al1 othersbelonging to exactly two faces are called s1ngle. The enumeration of rooted p1anar maps wasfirst introduced by Tutte['], Techniques originated by Tutte [2,3l for enumerating variousclasses of rooted Inaps on tIle sphere are here applied to the c1asses of alI rooted maps onthe projective plane. Th…     

Restricted permutations and the wreath product

Restricted permutations are those constrained by having to avoid subsequences ordered in various prescribed ways. A closed set is a set of permutations all satisfying a given basis set of restrictions. A wreath product construction is introduced and it is shown that this construction gives rise to a number of useful techniques for deciding the finite basis question and solving the enumeration problem. Several applications of these techniques are given.     

Central and local limit theorems applied to asymptotic enumeration. III. Matrix recursions

Let a multivariate sequence a_n(k) be obtained by a matrix recursion. It is shown that it is usually easy to establish central and local limit theorems for a_n(k). The proof requires a lemma on multisection of multivariate series which appears to be new. The applications of the limit theorems include covering by polyominoes, enumeration of plane animals, occupancy problems, 0–1 matrices, and nonexistence of critical phenomena.     

On the classification and enumeration of self-dual codes

A complete classification is given of all [22, 11] and [24, 12] binary self-dual codes. For each code we give the order of its group, the number of codes equivalent to it, and its weight distribution. There is a unique [24, 12, 6] self-dual code. Several theorems on the enumeration of self-dual codes are used, including formulas for the number of such codes with minimum distance ? 4, and for the sum of the weight enumerators of all such codes of length n. Selforthogonal codes which are generated by code words of weight 4 are completely characterized.