论文部分内容阅读
树是组合图论中一类重要的结构,它不仅是计数组合学中一个基本的研究对象,还被广泛应用于生物信息学,计算机科学等领域.有关树中限制点的出度的计数问题是近年来被国内外越来越多的数学家所研究.Deustch和Shapiro曾给出了n条边的平面树中所有奇出度点的个数并证明了平面树中奇度点和奇出度点总数的两倍关系.本文主要研究了k-叉树中给定出度的点的计数问题,并有以下结论：n条边的k-叉树中出度为i的点的总数为(ik)(n-ikn).我们分别用生成函数和双射两种方法对这一结论进行了证明.