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

The number of standard and of effective multiple alignments

APPLIED MATHEMATICS LETTERS 1998年第4期11卷 43-49页

作者： Dress, A Morgenstern, B Stoye, J Univ Bielefeld Fak Math D-33501 Bielefeld Germany GSF Natl Res Ctr Environm & Hlth Inst Biomath & Biometry D-85764 Neuherberg Germany Univ Calif Davis Dept Comp Sci Davis CA 95616 USA

We study the number of all possible alignments of N sequences, N greater than or equal to 2, for two distinct alignment concepts proposed in the literature-standard alignments and effective alignments (consistent equivalence relations). Recursion formulae are developed to calculate these numbers. For standard alignments and for effective alignment of just two sequences, an explicit formula is also presented. The number of all effective alignments of a given site space is shown to be related to Stirling numbers of second kind. (C) 1998 Elsevier Science Ltd. All rights reserved.

关键词： computational biology sequence analysis sequence alignment multiple alignment enumerative combinatorics Mobius inversion exclusion/inclusion principle

来源：评论

学校读者我要写书评

暂无评论

Forbidden subgraphs in connected graphs

引用

THEORETICAL COMPUTER SCIENCE 2004年第1-2期314卷 121-171页

作者： Ravelomanana, V Thimonier, LS Univ Paris 13 LIPN UMR 7030 F-93430 Villetaneuse France Univ Picardie LaRIA EA 2083 F-80000 Amiens France

Given a set xi = {H-1, H-2,...} of connected non-acyclic graphs, a xi-free graph is one which does not contain any member of as copy. Define the excess of a graph as the difference between its number of edges and its number of vertices. Let (W) over cap (k,xi) be the exponential generating function (EGF for brief) of connected xi-free graphs of excess equal to k (k greater than or equal to 1). For each fixed, a fundamental differential recurrence satisfied by the EGFs (W) over cap (k,xi) is derived. We give methods on how to solve this nonlinear recurrence for the first few values of k by means of graph surgery. We also show that for any finite collection xi of non-acyclic graphs, the EGFs (W) over cap (k,xi) are always rational functions of the generating function, T, of Cayley's rooted (non-planar) labelled trees. From this, we prove that almost all connected graphs with n nodes and n + k edges are xi-free, whenever k = o(n(1/3)) and \xi\ < infinity by means of Wright's inequalities and saddle point method. Limiting distributions are derived for sparse connected xi-free components that are present when a random graph on n nodes has approximately n/2 edges. In particular, the probability distribution that it consists of trees, unicyclic components,...,(q + 1)-cyclic components all xi-free is derived. Similar results are also obtained for multigraphs, which are graphs where self-loops and multiple-edges are allowed. (C) 2003 Elsevier B.V. All rights reserved.

关键词： combinatorial problems enumerative combinatorics analytic combinatorics labelled graphs multivariate generating functions asymptotic enumeration random graphs triangle-free graphs

来源：评论

学校读者我要写书评

暂无评论

Diletter circular codes over finite alphabets

引用

MATHEMATICAL BIOSCIENCES 2017年 294卷 120-129页

作者： Fimmel, Elena Michel, Christian J. Struengrnann, Lutz Univ Appl Sci Fac Comp Sci Inst Math Biol D-68163 Mannheim Germany Univ Strasbourg CNRS Theoret Bioinformat 300 Blvd Sebastien Brant F-67400 Illkirch Graffenstaden France

The graph approach of circular codes recently developed (Fimmel et al., 2016) allows here a detailed study of diletter circular codes over finite alphabets. A new class of circular codes is identified, strong comma-free codes. New theorems are proved with the diletter circular codes of maximal length in relation to (i) a characterisation of their graphs as acyclic tournaments;(ii) their explicit description;and (iii) the non-existence of other maximal diletter circular codes. The maximal lengths of paths in the graphs of the comma-free and strong comma-free codes are determined. Furthermore, for the first time, diletter circular codes are enumerated over finite alphabets. Biological consequences of dinucleotide circular codes are analysed with respect to their embedding in the trinucleotide circular code X identified in genes and to the periodicity modulo 2 observed in introns. An evolutionary hypothesis of circular codes is also proposed according to their combinatorial properties.

关键词： Diletter circular code Finite alphabet enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

Enumeration by kernel positions

引用

ADVANCES IN APPLIED MATHEMATICS 2009年第4期42卷 445-470页

作者： Hetyei, Gabor Univ N Carolina Dept Math & Stat Charlotte NC 28223 USA

We introduce a class of two-player games on posers with a rank function, in which each move of the winning strategy is unique, This allows one to enumerate the kernel positions by rank. The main example is a simple game on words in which the number of kernel positions of rank n is a signed factorial multiple of the nth Bernoulli number of the second kind. Generalizations to the degenerate Bernoulli numbers and to negative integer Substitutions into the Bernoulli polynomials are developed. Using an appropriate scoring system for each function with an appropriate Newton expansion we construct a game in which the expected gain of a player equals the definite integral of the function on the interval vertical bar 0. 1 vertical bar. (c) 2008 Elsevier Inc. All rights reserved.

关键词： Bernoulli polynomials Degenerate Bernoullli numbers Digamma function Progressively finite games Kernel position enumerative combinatorics Generating functions Newton expansion Euler's C constant

来源：评论

学校读者我要写书评

暂无评论

Cograph generation with linear delay

引用

THEORETICAL COMPUTER SCIENCE 2018年 713卷 1-10页

作者： Jones, Atila A. Protti, Fabio Del-Vecchio, Renata R. Univ Fed Fluminense Inst Comp Niteroi RJ Brazil Univ Fed Fluminense Inst Matemat Niteroi RJ Brazil

Cographs have always been a research target in areas such as coloring, graph decomposition, and spectral theory. In this work, we present an algorithm to generate all unlabeled cographs with n vertices, based on the generation of cotrees. The delay of our algorithm (time spent between two consecutive outputs) is O(n). The time needed to generate the first output is also O(n), which gives an overall O(n M-n) time complexity, where M-n is the number of unlabeled cographs with n vertices. The algorithm avoids the generation of duplicates (isomorphic outputs) and produces, as a by-product, a linear ordering of unlabeled cographs with n vertices. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Cographs enumerative combinatorics enumerative algorithms

来源：评论

学校读者我要写书评

暂无评论

A bijection between certain non-crossing partitions and sequences

引用

DISCRETE MATHEMATICS 2004年第3期286卷 269-275页

作者： Natarajan, R Kansas State Univ Dept Math Manhattan KS 66506 USA

We present a bijection between non-crossing partitions of the set [2n + 1] into n + 1 blocks such that no block contains two consecutive integers, and the set of sequences {si}(1)(n) such that 1less than or equal tos(i)less than or equal toi, and if s(i) = j, then s(i-r)less than or equal toj - r for 1less than or equal torless than or equal toj - 1. (C) 2004 Elsevier B.V. All rights reserved.

关键词： enumerative combinatorics catalan numbers non-crossing partitions

来源：评论

学校读者我要写书评

暂无评论

DUALITY OF GRADED GRAPHS

引用

JOURNAL OF ALGEBRAIC combinatorics 1994年第4期3卷 357-404页

作者： FOMIN, S MIT DEPT MATHCAMBRIDGEMA 02139 RUSSIAN ACAD SCI SPIIRANTHEORY ALGORITHMSMOSCOWRUSSIA

A graph is said to be graded if its vertices are divided into levels numbered by integers, so that the endpoints Of any edge lie on consecutive levels. Discrete modular lattices and rooted trees are among the typical examples. The following three types of problems are of interest to us: (1) path counting in graded graphs, and related combinatorial identities;(2) bijective proofs of these identities;(3) design and analysis of algorithms establishing corresponding bijections. This article is devoted to (1);its sequel [7] is concerned with the problems (2)-(3). A simplified treatment of some of these results can be found in [8]. In this article, R.P. Stanley's [26,27] linear-algebraic approach to (1) is extended to cover a wide range of graded graphs. The main idea is to consider pairs of graded graphs with a common set of vertices and common rank function. Such graphs am said to be dual if the associated linear operators satisfy a certain commutation relation (e.g., the ''Heisenberg'' one). The algebraic consequences of these relations are then interpreted as combinatorial identities. (This idea is also implicit in [27].) [7] contains applications to various examples of graded graphs, including the Young, Fibonacci, Young-Fibonacci and Pascal lattices, the graph of shifted shapes, the r-nary trees, the Schensted graph, the lattice of finite binary trees, etc. Many enumerative identities (both known and unknown) are obtained. Abstract of [7]. These identities can also be derived in a purely combinatorial way by generalizing the Robinson-Schensted correspondence to the class of graphs under consideration (cf. [5]). The same tools can be applied to permutation enumeration, including involution counting and rook polynomials for Ferrers boards. The bijective correspondences mentioned above are naturally constructed by Schensted-type algorithms. A general approach to these constructions is given. As particular cases we rederive the classical algorithm of Robinson, Schensted

关键词： enumerative combinatorics TABLEAUX YOUNG DIAGRAM DIFFERENTIAL POSET GRADED GRAPH

来源：评论

学校读者我要写书评

暂无评论

On the number of anchored rectangle packings for a planar point set

引用

THEORETICAL COMPUTER SCIENCE 2016年 654卷 143-154页

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

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

来源：评论

学校读者我要写书评

暂无评论

On doubly symmetric Dyck words

引用

THEORETICAL COMPUTER SCIENCE 2021年 896卷 79-97页

作者： Cori, Robert Frosini, Andrea Palma, Giulia Pergola, Elisa Rinaldi, Simone

In this paper we consider doubly symmetric Dyck words, i.e. Dyck words which are fixed by two symmetry operations alpha and beta introduced in [1]. We study combinatorial properties of doubly symmetric Dyck words, leading to the definition of two recursive algorithms to build these words. As a consequence we have a representation of doubly symmetric Dyck words as vectors of integers, called track vectors. Finally, we show some bijections between a subfamily of doubly symmetric Dyck words and a subfamily of integer partitions. The computation of the sequence f(n) of doubly symmetric Dyck words of semi-length n shows surprising properties giving rise to some conjectures. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Dyck languages enumerative combinatorics Integer sequences

来源：评论

学校读者我要写书评

暂无评论

A formula for a doubly refined enumeration of alternating sign matrices

引用

ADVANCES IN APPLIED MATHEMATICS 2010年第1期45卷 28-35页

作者： Karklinsky, Matan Romik, Dan Hebrew Univ Jerusalem Einstein Inst Math IL-91904 Jerusalem Israel

Zeilberger (1996) [12] proved the Refined Alternating Sign Matrix Theorem, which gives a product formula, first conjectured by Mills, Robbins and Rumsey (1983) [9], for the number of alternating sign matrices with given top row. Stroganov (2006) [10] proved an explicit formula for the number of alternating sign matrices with given top and bottom rows. Fischer and Romik (2009) [7] considered a different kind of "doubly-refined enumeration" where one counts alternating sign matrices with given top two rows, and obtained partial results on this enumeration. In this paper we continue the study of the doubly-refined enumeration with respect to the top two rows, and use Stroganov's formula to prove an explicit formula for these doubly-refined enumeration numbers. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Alternating sign matrix Square ice Six-vertex model enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：