朱桂静，何超林（华南师范大学数学科学学院，广东　广州　510631）

关于n圈k色的限制条件下的色多项式

朱桂静，何超林
（华南师范大学数学科学学院，广东广州510631）

对n圈k色的不同限制条件下的色多项式进行研究，包括：（1）给出n圈k色正常染色且满足第xi（i=1，2，…，k）种颜色恰好使用t次或不超过m次的正常染色多项式；（2）给出满足每2个相邻的染了xi色的点的间距不小于s的n圈k色正常染色的色多项式；（3）在集合和映射的层面对n圈k色的限制条件下的色多项式进行研究，从而抽象概括其数学模型并进行推广.

色多项式；n圈k色；组合计数

0　引言

n圈k色正常染色问题是图论与组合数学中一个有趣的问题，文献［1-3］对圈（环）排列进行元素的重排、限距、定元计算等方面的排列计数问题进行了研究，文献［4］给出了图的色多项式的定义以及相关的图的着色定理.本文在对圈图的研究之下，着重对不同的限制条件下的n圈k色正常染色的色多项式进行了研究，同时在此基础将之上升到集合和映射的层面并进行推广计算，对研究n圈k色正常染色的意义下所构成的群的组合计数有一定的意义.

1　相关定义、引理

定义1［4］图G的不同的至多t色的着色的数目，称为图G的色多项式，记作f（G，t）. n圈k色正常染色的色多项式在本文记作fn，k.

定义2［4］用n种颜色对图G的顶点进行着色，且没有相异的邻接点着相同的颜色，则称为G的一个n-顶点着色.用k种颜色对n个顶点的圈进行着色，且没有相异的邻接点着相同的颜色称为n圈k色正常染色.

定义3σ表示Nn→Nk的一种映射关系，记所有的σ组成的集合为Gσ，则=kn.若对任意的i=1，2，…，n-1均有σ（i）≠σ（i+1），且σ（n）≠σ（1），记满足该条件的σ组成的集合为Fσ.

定义4fi（σ）表示σ中像为i的原像个数

引理1［3］N表示正整数集，Nn表示集合｛1，2，…，n｝，n∈N，把Nn中的数依次环形排列，从中选出k个数是：i1，i2，…，ik（k∈N，2≤k≤n）满足：1≤i1≤i2＜…＜ik≤n且|ij+1-ij|≥s （j∈Nk-1），|n-ik+i1|≥s（s∈N），此时称数组｛i1，i2，…，ik｝为n元集环状单弧下限距为s的k组合，记其组合数为fn，k，s，则.，记给定两个位置颜色的色多项式为：引理2［3］n圈k色的正常染色的色多项式为：

推论1给定一个位置颜色的色多项式为：

为了叙述方便，本文约定：N表示正整数集，Nn表示集合｛1，2，…，n｝，表示实数x的下取整，|A|表示集合A的元素个数.

2　主要定理

证明：设事件Ai表示第i种颜色没有使用到，U表示n圈k色的正常染色数，则由容斥原理［5］得：

定理1对于n圈k色，若规定所有的颜色必须都使用到，则其不同的染色方法数有：

定理2对于n圈k色正常染色（k≥3），要求第x（ii=1，2，…，k）种颜色恰好使用t次（0≤t≤）的正常染色多项式为：

证明：将n圈的位置标号为V1，V2，…，Vn.从中选定t个位置，使其染xi色，并设其位置为Vi1，Vi2，…，Vit（1≤i1＜i2＜…＜it≤n）.对于任意的j（1≤j＜t），Vij+1和Vij之间有ij+1-ij-1个点，设这ij+1-ij-1个点的染色方法数为Lj，则有Lj=（k-1）（k-2）ij+1-ij-2.Vit和Vi1之间有n+i1-it-1个点，设这n+i1-it-1个点的染色方法数为Lt，有Lt=（k-1）（k-2）n+i1-it-2.则由乘法原理可得，在给定了Vi1，Vi2，…，Vit的染色后的色多项式为：

下面求满足条件选取的Vi1，Vi2，…，Vit的方法数（其中1≤i1＜i2＜…＜it≤n，ij+1-ij≥ 2，1≤j＜t且n+i1-it≥2），即i1，i2，…，it.为圆排列1，2，…，n的一个排列，且满足间距不小于2，其个数为所以：

特别地，当t=0时，则fn，k，xi，0=fn，k-1=（k-2）n+（-1）n（k-2）.当时t=1，则fn，R，xi，1=n（k-1）（k-2）n-2.

推论2.1对于n圈k色正常染色，要求xi（i=1，2…，R）色使用次数不超过m次的正常染色多项式为：

推论2.2对于n圈k色正常染色，要求每2个相邻的染了xi色的点的距离不小于s，则满足条件的正常染色的色多项式为：

证明：设染了xi色的点为，其中≥k，则由定理2知，xi色恰好使用t次且每两个染xi色的点的间距不小于s的正常染色的色多项式为又故：

定理4H0（i）

证明：H0（i）

证明：定理6

则容易知道：

下面计算

其中

而

综上所述：

对于n圈k色的限制条件下的色多项式还有很多值得研究的地方，特别是在集合和映射的层面对n圈k色的限制条件下的色多项式进行的组合计数研究.

［1］陈琼，常新德.有重复元素的圆排列和环排列的计算问题［J］.商丘职业技术学院学报，2008，7（2）：10-13.

［2］邱建霞，吴康.定元限距组合［J］.内江师范学院学报，2009，10（24）：21-25.

［3］邱建霞.环状限距组合计数的一些结果［J］.海南师范学院学报（自然科学版），2003，16（4）：6-10.

［4］王朝瑞.图论［M］.3版.北京：北京理工大学出版社，2011：154-158.

［5］曹汝成.组合数学［M］.广州：华南理工大学出版社，2000.

Chromatic Polynomials of n-Cycle of k-Coloring Under Different Restricted Conditions

ZHU Guijing，HE Chaolin
（School of Mathematics Sciences，South China Normal University，Guangzhou 510631，Guangdong，China）

Chromatic polynomials of n-cycle of k-coloring in different restricted conditions are studied.Three main results and conclusions are given:（1）Chromatic polynomials of n-cycle of k-coloring in which the xi-th color just uses the t times or no more than m times；（2）Chromatic polynomials of n-cycle of k-coloring in which the distance between two points in xi-th color is not less than s；（3）Chromatic polynomials of n-cycle of k-coloring in the perspective of set and mapping.The mathematical model is abstracted and generalized.

chromatic polynomials；n-cycle of k-coloring；combinatorial enumeration

O157

A

1001-4217（2016）02-0045-06

2015-07-30

朱桂静（1991—），女（汉族），广东梅州人，硕士研究生.研究方向：组合数学、数学课程论.

E-mail：1248639313@qq.com.