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

作者： 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Monsters in the hollow: counting Naiki braid patterns using de Bruijn's Monster theorem

引用

JOURNAL OF MATHEMATICS AND THE ARTS 2023年第1-2期17卷 99-110页

作者： Holden, Joshua Rose Hulman Inst Technol Dept Math Terre Haute IN 47803 USA

The Japanese braids known as Naiki, which are distinguished by their hollow interior, have a simple structure shared by many other fiber arts and crafts. The way in which this structure forms a cylindrical braid imposes a particular set of symmetries on the final product. This paper uses enumerative combinatorics, including de Bruijn's Monster Theorem, to count the number of two-color Naiki braids under equivalence by this natural set of symmetries.

关键词： Braiding Japanese crafts fiber arts weaving counting patterns enumerative combinatorics generating functions Monster theorem symmetry

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

SEMI-BAXTER AND STRONG-BAXTER: TWO RELATIVES OF THE BAXTER SEQUENCE

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第4期32卷 2795-2819页

作者： Bouvel, Mathilde Guerrini, Veronica Rechnitzer, Andrew Rinaldi, Simone Univ Zurich Inst Math CH-8057 Zurich Switzerland Univ Siena Dept Informat Engn & Math I-53100 Siena Italy Univ British Columbia Dept Math Vancouver BC V6T 1Z2 Canada

In this paper, we enumerate two families of pattern-avoiding permutations: those avoiding the vincular pattern 2 (41) under bar 3, which we call semi-Baxter permutations, and those avoiding the vincular patterns 2 (41) under bar 3, 3 (14) under bar 2, and 3 (41) under bar 2, which we call strong-Baxter permutations. We call semi-Baxter numbers and strong-Baxter numbers the associated enumeration sequences. We prove that the semi-Baxter numbers enumerate in addition plane permutations (avoiding 2 (14) under bar 3). The problem of counting these permutations was open and has given rise to several conjectures, which we also prove in this paper. For each family (that of semi-Baxter-or, equivalently, plane-and that of strong-Baxter permutations), we describe a generating tree, which translates into a functional equation for the generating function. For semi-Baxter permutations, it is solved using (a variant of) the kernel method: this gives an expression for the generating function while also proving its D-finiteness. From the obtained generating function, we derive closed formulas for the semi-Baxter numbers, a recurrence that they satisfy, as well as their asymptotic behavior. For strong-Baxter permutations, we show that their generating function is (a slight modification of) that of a family of walks in the quarter plane, which is known to be non-D-finite.

关键词： enumerative combinatorics permutations generating functions

来源：评论

学校读者我要写书评

暂无评论

Using Binary Patterns for Counting Falsifying Assignments of Conjunctive Forms

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2015年 315卷 17-30页

作者： De Ita Luna, Guillermo Raymundo Marcial-Romero, J. Pozos-Parra, Pilar Hernandez, Jose A. Benemerita Univ Autonoma Puebla Fac Ciencias Computac Puebla Mexico Univ Autonoma Estado Mexico Fac Ingn Toluca Mexico Univ Juarez Autonoma Tabasco Div Acad Informat & Sistemas Tabasco Mexico

The representation of the set of falsifying assignments of clauses via binary patterns has been useful in the design of algorithms for solving #FAL (counting the number of falsifying assignments of conjunctive forms (CF)). Given as input a CF formula F expressed by m clauses defined over n variables, we present a deterministic algorithm for computing #FAL(F). Principally, our algorithm computes non-intersecting subsets of falsifying assignments of F until the space of falsifying assignments defined by F is covered. Due to #SAT(F) = 2(n)-#FAL(F), results about #FAL can be established dually for #SAT. The time complexity of our proposals for computing #FAL(F) is established according to the number of clauses and the number of variables of F.

关键词： #SAT #FAL Binary Patterns enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

Classical and consecutive pattern avoidance in rooted forests

引用

JOURNAL OF COMBINATORIAL THEORY SERIES A 2023年 194卷

作者： Garg, Swapnil Peng, Alan MIT Cambridge MA 02139 USA

Following Anders and Archer, we say that an unordered rooted labeled forest avoids the pattern Sigma is an element of Sk if in each tree, each sequence of labels along the shortest path from the root to a vertex does not contain a subsequence with the same relative order as Sigma. For each permutation Sigma is an element of Sk-2, we construct a bijection between n-vertex forests avoiding (Sigma)(k - 1)k := Sigma (1) middot middot middot Sigma(k - 2)(k - 1)k and n-vertex forests avoiding (Sigma)k(k - 1) := Sigma (1) middot middot middot Sigma(k - 2)k(k - 1), giving a common generalization of results of West on permutations and Anders-Archer on forests. We further define a new object, the forest-Young diagram, which we use to extend the notion of shape-Wilf equivalence to forests. In particular, this allows us to generalize the above result to a bijection between forests avoiding {(Sigma 1)k(k - 1), (Sigma 2)k(k - 1), ..., (Sigma t)k(k - 1)} and forests avoiding {(Sigma 1)(k - 1)k, (Sigma 2)(k - 1)k, ..., (Sigma t)(k - 1)k} for Sigma 1, . . . , Sigma cent is an element of Sk-2. Furthermore, we give recurrences enumerating the forests avoiding {123 middot middot middot k}, {213}, and other sets of patterns. Finally, we extend the Goulden-Jackson cluster method to study consecutive pattern avoidance in rooted trees as defined by Anders and Archer. Using the generalized cluster method, we prove that if two length-k patterns are strong-c-forest-Wilf equivalent, then up to complementation, the two patterns must start with the same number. We also prove the surprising result that the patterns 1324 and 1423 are strong-c-forest-Wilf equivalent, even though they are not c-Wilf equivalent with respect to permutations. (c) 2022 Elsevier Inc. All rights reserved.

关键词： enumerative combinatorics Pattern avoidance Cluster method Rooted forests

来源：评论

学校读者我要写书评

暂无评论

combinatorics of Second Derivative: Graphical Proof of Glaisher-Crofton Identity

引用

ADVANCES IN MATHEMATICAL PHYSICS 2018年第Pt.2期2018卷 9575626-1-9575626-9页

作者： Blasiak, Pawel Duchamp, Gerard H. E. Penson, Karol A. Polish Acad Sci Inst Nucl Phys PL-31342 Krakow Poland Univ Paris 13 Sorbonne Paris Cite CNRS LIPNUMR 7030 F-93430 Villetaneuse France Univ Pierre Marie Curie Paris 06 Sorbonne Univ CNRS LPTMCUMR 7600 F-75252 Paris 05 France

We give a purely combinatorial proof of the Glaisher-Crofton identity which is derived from the analysis of discrete structures generated by the iterated action of the second derivative. The argument illustrates the utility of symbolic and generating function methodology of modern enumerative combinatorics. The paper is meant for nonspecialists as a gentle introduction to the field of graphical calculus and its applications in computational problems.

关键词： Generating function Second derivative combinatorics enumerative combinatorics Derivative

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：