有根无环欧拉地图的数目.pdfVIP

第29卷第2期 应用数学学报 V01．29No．2 2006年3月ACTAMATHEMATICAEAPPLICATAESINICAMarch，2006 有根无环欧拉地图的数目术 蔡俊亮 (北京师范大学数学科学学院，北京100875) (E—mail：caijunliang@bnu．edu．cn) 摘要本文首先解决了有根无环欧拉地图依边数的三次计数方程的求解问题，同时提供一种 有效的计数方法对先前的一些相关结果及其推导过程进行了必要的改进． 关键词一般欧拉地图；无环欧拉地图；计数方程；参数解；显解 MR(2000)主题分类05A15；05C30 中图分类0157．5 1 引言 一个平面地图就是一个图在平面上的嵌入． 如果把地图的一条边规定一个特殊的方 向，那么此边称为根边，根边的始端称为根点， 与根边关联的一个面称为根面，此时该 地图称为有根平面地图或简称为地图． 一个有根平面地图被称为是欧拉地图，如果其所有的顶点次均为偶数．关于欧拉地 W 图的计数，早在六十年代初期Tutte T首先进行过研究[1]．后来，许多学者也对此问 题进行过分类研究[2J1992年，刘彦佩首次研究了有根无环欧拉地图的计数f3】’并获得 如下的以边数和根点次作为参数的三次计数方程[3，(4．11)]1： (1) 这里，h=h(x，Y)表示以边数和根点次作为参变量的有根无环欧拉地图的计数函数．确 切的说，如果记Enl为有根无环欧拉地图的集合，并且定义计数函数： ，=尼。。(z，Y，z)=∑x2m(M)y”‘M’z州’， ME$。z 其中， 2m(M)，n(M)和Z(M)分别表示地图ME厶f的根点次，边数和根面次，那 H=Hs。。(Y)=hE。：(1，Y)=fE。。(1，Y，1)的参数表达式[4]： ‰㈤=菘弗． (3) 本文2004年2月24日收到． +国家自然科学基金)资助项目 注：原方程有误! 2期 蔡俊亮：有根无环欧拉地图的数目 211 数目为： 印=3篓坠袢薪产(2儿洲2一礼2川) 但是，这个结果的推导过程十分复杂，先后构造了十余类相关的地图并研究了它们 之间的计数关系，使得进一步的推广变得更加困难．本文将对[4]的推导过程和计数结果 进行实质性的简化和推广．换言之，本文将利用一般欧拉地图的计数结果，仅仅通过它 与无环欧拉地图的计数关系，便可获得单变量乃至多变量的无环欧拉地图的计数结果． 就结果而言，我们将(3)式和(4)式分别简化为： Y=叼(1一叩)(1—72)2，可月≥。：(Y)=7(1一叩一叩2) (5) 和 印=薹％锱等瓣，喇 (6) 其中 Aj(n)=8j(2n一2j—1)一3n(n一1)． 此外，我们还得到计数函数h=hE。。(X，Y)的参数表达式： fx2y=∈(1一叼)(1一∈叩)2，Y=7(1一卵)(1—72)2； 【X2yhc。：(z，Y)=∈(1—7一∈叩)． 具有n条边且根点次为2m(n≥2m芝2)的有根无环欧拉地图的数目为： 嗽=”等等‰筹糯鬻 其中，J=m+r，k=n—m，而且 l可zF≥。：(可，z)=篁!!一=二二宅；；；；；宅；紫．