본문 바로가기 메뉴바로가기

Papers

Profiles of ordered trees with mutation and associated Riordan matrices

http://dx.doi.org/10.1016/j.laa.2016.09.006

We consider ordered trees with a distinguished vertex which we call a mutator. There are many situations where this model arises. An ordered tree could represent a river network, supply lines, an employee organization chart, a phylogenetic tree, or a family tree. The mutator could be a dam or a source of pollution, a break in a supply line, a corrupt employee, and so on. We look at such things as the number of affected vertices, distance from the root, and the effect of various succession rules. Among the types of trees these results apply to are ordered trees defined by a uniform updegree requirement. We find some profiles of trees with a mutation in terms of Riordan matrices. The asymptotic formulas for the ratios of vertices of the new type to all vertices are also derived by using singularity analysis of generating functions.

We consider ordered trees with a distinguished vertex which we call a mutator. There are many situations where this model arises. An ordered tree could represent a river network, supply lines, an employee organization chart, a phylogenetic tree, or a family tree. The mutator could be a dam or a source of pollution, a break in a supply line, a corrupt employee, and so on. We look at such things as the number of affected vertices, distance from the root, and the effect of various succession rules. Among the types of trees these results apply to are ordered trees defined by a uniform updegree requirement. We find some profiles of trees with a mutation in terms of Riordan matrices. The asymptotic formulas for the ratios of vertices of the new type to all vertices are also derived by using singularity analysis of generating functions.