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

21st Annual International Computing and combinatorics Conference (COCOON)

作者： Balas, Kevin Toth, Csaba D. Calif State Univ Northridge Los Angeles CA 91330 USA Los Angeles Mission Coll Dept Math Sylmar CA USA Tufts Univ Dept Comp Sci Medford MA 02155 USA

ISBN: (纸本)9783319213972

We consider packing axis-aligned rectangles r1,..,r(n) in the unit square [0,1](2) such that a vertex of each rectangle n is a given point pi (i.e., r(i) is anchored at p(i)). We explore the combinatorial structure of all locally maximal configurations. When the given points are the lower-left corners of the rectangles, the number of maximal packings is shown to be at most 2(n)C(n), where C-n is the nth Catalan number. The number of maximal packings remains exponential in n when the points may be arbitrary corners of the rectangles. Both upper bounds are complemented with exponential lower bounds. Finally, we define the graph of all lower-left anchored maximal rectangle packings, where the edges correspond to elementary operations between two packings, which leads to an output sensitive algorithm for computing these packings. (C) 2016 Elsevier B.V. All rights reserved.

关键词： enumerative combinatorics Rectangle packing Contact graph

来源：评论

学校读者我要写书评

暂无评论

Unit Interval Parking Functions and the r-Fubini Numbers

引用

Matematica 2024年第1期3卷 370-384页

作者： Bradt, S. Alex Elder, Jennifer Harris, Pamela E. Kirby, Gordon Rojas Reutercrona, Eva Wang, Yuxuan Whidden, Juliet School of Mathematical and Statistical Sciences Arizona State University Tempe 85281 AZ United States Department of Computer Science Math & amp Physics Missouri Western State University Saint Joseph 64501 MO United States Department of Mathematical Sciences University of Wisconsin-Milwaukee Milwaukee 53211 WI United States Department of Mathematics and Statistics San Diego State University San Diego 92182 CA United States Pacific Lutheran University Tacoma 98447 WA United States Mount Holyoke College South Hadley 01075 MA United States Vassar College Poughkeepsie 12604 NY United States

We recall that unit interval parking functions of length n are a subset of parking functions in which every car parks in its preference or in the spot after its preference, and Fubini rankings of length n are rankings of n competitors allowing for ties. We present an independent proof of a result of Hadaway, which establishes that unit interval parking functions and Fubini rankings are in bijection. We also prove that the cardinality of these sets are given by Fubini numbers. In addition, we give a complete characterization of unit interval parking functions by determining when a rearrangement of a unit interval parking function is again a unit interval parking function. This yields an identity for the Fubini numbers as a sum of multinomials over compositions. Moreover, we introduce a generalization of Fubini rankings, which we call the r-Fubini rankings of length n+r. We show that this set is in bijection with unit interval parking functions of length n+r where the first r cars have distinct preferences. We conclude by establishing that these sets are enumerated by the r-Fubini numbers. © The Author(s), under exclusive licence to Springer Science+Business Media LLC, part of Springer Nature 2024.

关键词： enumerative combinatorics Fubini numbers Fubini rankings Parking functions

来源：评论

学校读者我要写书评

暂无评论

Counting Rectangular Drawings or Floorplans in Polynomial Time

Counting Rectangular Drawings or Floorplans in Polynomial Ti...

引用

21st Workshop on Circuits and Systems

作者： Inoue, Youhei Takahashi, Toshihiko Fujimaki, Ryo Renesas Technol Corp Tokyo 1000004 Japan Niigata Univ Acad Assembly Inst Nat Sci & Technol Niigata 9502181 Japan Niigata Univ Grad Sch Sci & Technol Niigata 9502181 Japan

A subdivision of a rectangle into rectangular faces with horizontal and vertical line segments is called a rectangular drawing or floorplan. It has been an open problem to determine whether there exist a polynomial time algorithm for computing R(n). We affirmatively solve the problem, that is, we introduce an O(n(4))-time and O(n(3))-space algorithm for R(n). The algorithm is based on a recurrence for R(n), which is the main result of the paper. We also implement our algorithm and computed R(n) for n <= 3000.

关键词： rectangular drawing floorplan enumerative combinatorics dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Generating and counting unlabeled k-path graphs

Generating and counting unlabeled <i>k</i>-path graphs

引用

1st International Symposium on Combinatorial Optimization (ISCO)

作者： da Costa Pereira, Paulo Renato Garcia, Alex Markenzon, Lilian Inst Mil Engn BR-22290270 Rio De Janeiro Brazil Univ Fed Rio de Janeiro Nucleo Comp Elect BR-20010974 Rio De Janeiro Brazil

A subfamily of k-trees, the k-path graphs generalize path graphs in the same way k-trees generalize trees. This paper presents a code for unlabeled k-path graphs. The effect of structural properties of the family on the code is investigated, leading to the solution of two problems: determining the exact number of unlabeled k-path graphs with n vertices and generating all elements of the family. (c) 2011 Elsevier B.V. All rights reserved.

关键词： enumerative combinatorics Graph theory k-path graphs Structural properties

来源：评论

学校读者我要写书评

暂无评论

On the two-point function of general planar maps and hypermaps

引用

ANNALES DE L INSTITUT HENRI POINCARE D 2014年第3期1卷 265-306页

作者： Bouttier, Jeremie Fusy, Eric Guitter, Emmanuel CEA IPhT Inst Phys Theor F-91191 Gif Sur Yvette France CNRS URA 2306 Paris France Ecole Normale Super Dept Math & Applicat F-75231 Paris 05 France Ecole Polytech LIX F-91120 Palaiseau France

We consider the problem of computing the distance-dependent two-point function of general planar maps and hypermaps, i.e., the problem of counting such maps with two marked points at a prescribed distance. The maps considered here may have faces of arbitrarily large degree, which requires new bijections to be tackled. We obtain exact expressions for the following cases: general and bipartite maps counted by their number of edges, 3-hypermaps and 3-constellations counted by their number of dark faces, and finally general and bipartite maps counted by both their number of edges and their number of faces.

关键词： Random geometry maps graph distance two-point function discrete integrability bijections enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：