检索结果-内蒙古大学图书馆

Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

Electronic Notes in Discrete Mathematics 2009年第C期35卷 323-328页

作者： Dourado, Mitre Costa de Oliveira, Rodolfo Alves Protti, Fábio Universidade Federal Rural do Rio de Janeiro (UFRRJ) Brazil Universidade Federal do Rio de Janeiro (UFRJ) Brazil Universidade Federal Fluminense (UFF) Brazil

In this work we present an enumeration algorithm for the generation of all Steiner trees containing a given set W of terminals of an unweighted graph G such that | W | = k, for a fixed positive integer k. The enumeration is performed within O (n) delay, where n = | V (G) | consequence of the algorithm is that the Steiner interval and the strong Steiner interval of a subset W ⊆ V (G) can be computed in polynomial time, provided that the size of W is bounded by a constant. © 2009 Elsevier B.V. All rights reserved.

关键词： enumerative combinatorics steiner convexity Steiner tree

来源：评论

学校读者我要写书评

暂无评论

Enumeration of stacks of spheres

引用

Involve 2018年第5期11卷 867-875页

作者： Endicott, Lauren May, Russell Shacklette, Sienna The Craft Academy for Excellence in Science and Mathematics Morehead State University Morehead 40351 KY United States Department of Mathematics and Physics Morehead State University Morehead 40351 KY United States

As a three-dimensional generalization of fountains of coins, we analyze stacks of spheres and enumerate two particular classes, so-called “pyramidal” stacks and “Dominican” stacks. Using the machinery of generating functions, we obtain exact formulas for these types of stacks in terms of the sizes of their bases. © 2018, Mathematical Sciences Publishers. All rights reserved.

关键词： enumerative combinatorics generating functions

来源：评论

学校读者我要写书评

暂无评论

Enumeration and Generating Functions of Rota-Baxter Words

引用

MATHEMATICS IN COMPUTER SCIENCE 2010年第2-3期4卷 313-337页

作者： Guo, Li Sit, William Y. Rutgers State Univ Dept Math & Comp Sci Newark NJ 07102 USA CUNY City Coll Dept Math New York NY 10031 USA

In this paper, we prove results on enumerations of sets of Rota-Baxter words (RBWs) in a single generator and one unary operator. Examples of operators are integral operators, their generalization to Rota-Baxter operators, and Rota-Baxter type operators. RBWs are certain words formed by concatenating generators and images of words under the operators. Under suitable conditions, they form canonical bases of free Rota-Baxter type algebras which are studied recently in relation to renormalization in quantum field theory, combinatorics, number theory, and operads. Enumeration of a basis is often a first step to choosing a data representation in implementation. We settle the case of one generator and one operator, starting with the idempotent case (more precisely, the exponent 1 case). Some integer sequences related to these sets of RBWs are known and connected to other sequences from combinatorics, such as the Catalan numbers, and others are new. The recurrences satisfied by the generating series of these sequences prompt us to discover an efficient algorithm to enumerate the canonical basis of certain free Rota-Baxter algebras.

关键词： enumerative combinatorics Rota-Baxter words Rota-Baxter algebras Compositions Generating functions Grammar Catalan numbers

来源：评论

学校读者我要写书评

暂无评论

A Note on the Number of (Maximal) Antichains in the Lattice of Set Partitions 28th

A Note on the Number of (Maximal) Antichains in the Lattice ...

引用

28th International Conference on Graph-Based Representation and Reasoning (ICCS)

作者： Ignatov, Dmitry I. Natl Res Univ Higher Sch Econ Sch Data Anal & Artificial Intelligence Lab Models & Methods Computat Pragmat Moscow Russia

ISBN: (纸本)9783031409592;9783031409608

Set partitions and partition lattices are well-known objects in combinatorics and play an important role as a search space in many applied problems including ensemble clustering. Searching for antichains in such lattices is similar to that of in Boolean lattices. Counting the number of antichains in Boolean lattices is known as the Dedekind problem. In spite of the known asymptotic for the latter problem, the behaviour of the number of antichains in partition lattices has been paid less attention. In this short paper, we show how to obtain a few first numbers of antichains and maximal antichains in the partition lattices with the help of concept lattices and provide the reader with some related heuristic bounds. The results of our computational experiments confirm the known values and are also recorded in the Online Encyclopaedia of Integer Sequences (see https://***/A358041).

关键词： Formal Concept Analysis partition lattice maximal antichains concept lattices enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

Classification and enumeration of finite semigroups

Classification and enumeration of finite semigroups

引用

作者： Distler, Andreas University of St Andrews

学位级别：博士

The classification of finite semigroups is difficult even for small orders because of their large number. Most finite semigroups are nilpotent of nilpotency rank 3. Formulae for their number up to isomorphism, and up to isomorphism and anti-isomorphism of any order are the main results in the theoretical part of this thesis. Further studies concern the classification of nilpotent semigroups by rank, leading to a full classification for large ranks. In the computational part, a method to find and enumerate multiplication tables of semigroups and subclasses is presented. The approach combines the advantages of computer algebra and constraint satisfaction, to allow for an efficient and fast search. The problem of avoiding isomorphic and anti-isomorphic semigroups is dealt with by supporting standard methods from constraint satisfaction with structural knowledge about the semigroups under consideration. The approach is adapted to various problems, and realised using the computer algebra system GAP and the constraint solver Minion. New results include the numbers of semigroups of order 9, and of monoids and bands of order 10. Up to isomorphism and anti-isomorphism there are 52,989,400,714,478 semigroups with 9 elements, 52,991,253,973,742 monoids with 10 elements, and 7,033,090 bands with 10 elements. That constraint satisfaction can also be utilised for the analysis of algebraic objects is demonstrated by determining the automorphism groups of all semigroups with 9 elements. A classification of the semigroups of orders 1 to 8 is made available as a data library in form of the GAP package Smallsemi. Beyond the semigroups themselves a large amount of precomputed properties is contained in the library. The package as well as the code used to obtain the enumeration results are available on the attached DVD.

关键词： Nilpotent semigroups enumerative combinatorics Data library Power group enumeration 3-nilpotent Computer search

来源：评论

学校读者我要写书评

暂无评论

Counting pseudo progressions

引用

INVOLVE, A JOURNAL OF MATHEMATICS 2020年第5期13卷 759-780页

作者： Cummings, Jay Darcy, Quin Hobson, Natalie Horton, Drew Rhodewalt, Keith Throckmorton, Morgan Ulmer-Strack, Ry Calif State Univ Sacramento Dept Math & Stat Sacramento CA 95819 USA Sonoma State Univ Dept Math & Stat Rohnert Pk CA 94928 USA

An m-pseudo progression is an increasing list of numbers for which there are at most m distinct differences between consecutive terms. This object generalizes the notion of an arithmetic progression. We give two counts for the number of k-term m-pseudo progressions in {1, 2, . . ., n}. We also provide computer-generated tables of values which agree with both counts and graphs that display the growth rates of these functions. Finally, we present a generating function which counts k-term progressions in {1, 2, . . ., n} whose differences are all distinct, and we discuss further directions in Ramsey theory.

关键词： enumerative combinatorics pseudo progressions

来源：评论

学校读者我要写书评

暂无评论

Weighted model counting beyond two-variable logic 18

Weighted model counting beyond two-variable logic

引用

33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) held as part of the Federated Logic Conference (FLoC)

作者： Kuusisto, Antti Lutz, Carsten Univ Bremen Bremen Germany

ISBN: (纸本)9781450355834

It was recently shown by van den Broeck at al. that the symmetric weighted first-order model counting problem (WFOMC) for sentences of two-variable logic FO2 is in polynomial time, while it is #P-1-complete for some FO3-sentences. We extend the result for FO2 in two independent directions: to sentences of the form phi Lambda for all x there exists(=1)y psi(x, y) with phi and psi formulated in FO2 and to sentences of the uniform one-dimensional fragment U-1 of FO, a recently introduced extension of two-variable logic with the capacity to deal with relation symbols of all arities. We note that the former generalizes the extension of FO2 with a functional relation symbol. We also identify a complete classification of first-order prefix classes according to whether WFOMC is in polynomial time or #P-1-complete.

关键词： weighted model counting tractability two-variable logic enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

Enumeration and analysis of models of planar maps via the bijective method

Enumeration and analysis of models of planar maps via the bi...

引用

作者： Collet Gwendal

学位级别：博士

Bijective combinatorics is a field which consists in studying the enumerative properties of some families of mathematical objects, by exhibiting bijections (ideally explicit) which preserve these properties between such families and already known objects. One can then apply any tool of analytic combinatorics to these new objets, in order to get explicit enumeration, asymptotics properties, or to perform random *** this thesis, we will be interested in planar maps – graphs drawn on the plane with no crossing edges. First, we will recover a simple formula –obtained by Eynard – for the generating series of bipartite maps and quasi-bipartite maps with boundaries of prescribed lengths, and we will give anatural generalization to p-constellations and quasi-p-constellations. In the second part of this thesis, we will present an original bijection for outertriangular simple maps – with no loops nor multiple edges – and eulerian triangulations. We then use this bijection to design random samplers for rooted simple maps according to the number of vertices and edges. We will also study the metric properties of simple maps by proving the convergence of the rescaled distance-profile towards an explicit random measure related to the Brownian snake.

关键词： brownian map simple maps maps with boundaries symbolic method planar maps enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

Blossoming bijection for bipartite pointed maps and parametric rationality of general maps of any surface

引用

ADVANCES IN APPLIED MATHEMATICS 2022年 141卷

作者： Dolega, Maciej Lepoutre, Mathias Polish Acad Sci Inst Math Ul Sniadeckich 8 PL-00956 Warsaw Poland Ecole Polytech LIX 1 Rue Honore Estiennes Orves F-91120 Palaiseau France

We construct an explicit bijection between bipartite pointed maps of an arbitrary surface S, and specific unicellular blossoming maps of the same surface. Our bijection gives access to the degrees of all the faces, and distances from the pointed vertex in the initial map. The main construction generalizes recent work of the second author which covered the case of an orientable surface. Our bijection gives rise to a first combinatorial proof of a parametric rationality result concerning the bivariate generating series of maps of a given surface with respect to their numbers of faces and vertices. In particular, it provides a combinatorial explanation of the structural difference between the aforementioned bivariate parametric generating series in the case of orientable and non-orientable maps.

关键词： enumerative combinatorics Bijective combinatorics Combinatorial maps Non-orientable surface Blossoming tree Rationality

来源：评论

学校读者我要写书评

暂无评论

A positional statistic for 1324-avoiding permutations

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2024年第1期26卷

作者： Gil, Juan B. Lopez, Oscar A. Weiner, Michael D. Penn State Altoona Altoona PA 16601 USA Penn State Harrisburg Middletown PA USA

We consider the class S-n(1324) of permutations of size n that avoid the pattern 1324 and examine the subset S-n(a = 1. This notation means that, when written in one line notation, such a permutation must have a to th... 详细信息

We consider the class S-n(1324) of permutations of size n that avoid the pattern 1324 and examine the subset S-n(a < n)(1324) of elements for which a < n <[a-1], a >= 1. This notation means that, when written in one line notation, such a permutation must have a to the left of n, and the elements of {1,& mldr;,a-1} must all be to the right of n. For n >= 2, we establish a connection between the subset of permutations in S-n(1 < n)(1324) having the 1 adjacent to the n (called primitives), and the set of 1324-avoiding dominoes with n-2 points. For a is an element of{1,2}, we introduce constructive algorithms and give formulas for the enumeration of S-n(a < n)(1324) by the position of aa relative to the position of n. For a >= 3, we formulate some conjectures for the corresponding generating functions.

关键词： pattern-avoiding permutations enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：