有根二色树的计数

摘要

组合数学主要研究某组离散对象中满足一定条件的格局的存在性、构造性、及计数等问题.由于计算机的迅速发展,组合数学获得了新的生命力,成为数学的一个重要分支.组合计数又是组合数学中一个最基本的研究方向,主要研究满足一定条件的安排方式的数目和计算问题.组合计数的方法之一是在两个由离散结构组成的集合之间找到一个算法,建立一个双射,然后求出它们在生成函数上的关系式.自从M.Fieldler和J.Sedlacek[10]首先讨论了完全二部图中标号生成树的计数以来,一些文章从不同角度、用不同方法对比进行了新的阐述.该文主要是用另一个方法就完全二部图中的有根生成树和有根生成森林及二色有序树进行了讨论,大致分为五节,简单介绍如下:第一节讨论完全二部图中有根生成树的计数.第二节讨论完全二部图中有根生成森林的计数.第三节讨论二色有序树.第四节主要是在第三节提出的第一个算法的基础上,讨论二色有序树上的对合.这些对合的共同点是它们作用在一个二色有序树上之后,可使得内点变成叶子、叶子变成内点.第五节主要是提出了有序树和二色有序树之间的一个组合双射.

目录

文摘

英文文摘

§1前言

§2 [m,n]-二色树的计数

§3 [m,l;n,k]-森林的计数

§4[m,n]-二色有序树的计数

§5 [m,n]-二色有序树上的对合

§6有序树与二色有序树之间的联系

参考文献

致谢