關(guān)于n圈k色的限制條件下的色多項式

朱桂靜，何超林（華南師范大學數(shù)學科學學院，廣東　廣州　510631）

關(guān)于n圈k色的限制條件下的色多項式

朱桂靜，何超林
（華南師范大學數(shù)學科學學院，廣東廣州510631）

對n圈k色的不同限制條件下的色多項式進行研究，包括：（1）給出n圈k色正常染色且滿足第xi（i=1，2，…，k）種顏色恰好使用t次或不超過m次的正常染色多項式；（2）給出滿足每2個相鄰的染了xi色的點的間距不小于s的n圈k色正常染色的色多項式；（3）在集合和映射的層面對n圈k色的限制條件下的色多項式進行研究，從而抽象概括其數(shù)學模型并進行推廣.

色多項式；n圈k色；組合計數(shù)

0　引言

n圈k色正常染色問題是圖論與組合數(shù)學中一個有趣的問題，文獻［1-3］對圈（環(huán)）排列進行元素的重排、限距、定元計算等方面的排列計數(shù)問題進行了研究，文獻［4］給出了圖的色多項式的定義以及相關(guān)的圖的著色定理.本文在對圈圖的研究之下，著重對不同的限制條件下的n圈k色正常染色的色多項式進行了研究，同時在此基礎(chǔ)將之上升到集合和映射的層面并進行推廣計算，對研究n圈k色正常染色的意義下所構(gòu)成的群的組合計數(shù)有一定的意義.

1　相關(guān)定義、引理

定義1［4］圖G的不同的至多t色的著色的數(shù)目，稱為圖G的色多項式，記作f（G，t）. n圈k色正常染色的色多項式在本文記作fn，k.

定義2［4］用n種顏色對圖G的頂點進行著色，且沒有相異的鄰接點著相同的顏色，則稱為G的一個n-頂點著色.用k種顏色對n個頂點的圈進行著色，且沒有相異的鄰接點著相同的顏色稱為n圈k色正常染色.

定義3σ表示Nn→Nk的一種映射關(guān)系，記所有的σ組成的集合為Gσ，則=kn.若對任意的i=1，2，…，n-1均有σ（i）≠σ（i+1），且σ（n）≠σ（1），記滿足該條件的σ組成的集合為Fσ.

定義4fi（σ）表示σ中像為i的原像個數(shù)

引理1［3］N表示正整數(shù)集，Nn表示集合｛1，2，…，n｝，n∈N，把Nn中的數(shù)依次環(huán)形排列，從中選出k個數(shù)是：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），此時稱數(shù)組｛i1，i2，…，ik｝為n元集環(huán)狀單弧下限距為s的k組合，記其組合數(shù)為fn，k，s，則.，記給定兩個位置顏色的色多項式為：引理2［3］n圈k色的正常染色的色多項式為：

推論1給定一個位置顏色的色多項式為：

為了敘述方便，本文約定：N表示正整數(shù)集，Nn表示集合｛1，2，…，n｝，表示實數(shù)x的下取整，|A|表示集合A的元素個數(shù).

2　主要定理

證明：設(shè)事件Ai表示第i種顏色沒有使用到，U表示n圈k色的正常染色數(shù)，則由容斥原理［5］得：

定理1對于n圈k色，若規(guī)定所有的顏色必須都使用到，則其不同的染色方法數(shù)有：

定理2對于n圈k色正常染色（k≥3），要求第x（ii=1，2，…，k）種顏色恰好使用t次（0≤t≤）的正常染色多項式為：

證明：將n圈的位置標號為V1，V2，…，Vn.從中選定t個位置，使其染xi色，并設(shè)其位置為Vi1，Vi2，…，Vit（1≤i1＜i2＜…＜it≤n）.對于任意的j（1≤j＜t），Vij+1和Vij之間有ij+1-ij-1個點，設(shè)這ij+1-ij-1個點的染色方法數(shù)為Lj，則有Lj=（k-1）（k-2）ij+1-ij-2.Vit和Vi1之間有n+i1-it-1個點，設(shè)這n+i1-it-1個點的染色方法數(shù)為Lt，有Lt=（k-1）（k-2）n+i1-it-2.則由乘法原理可得，在給定了Vi1，Vi2，…，Vit的染色后的色多項式為：

下面求滿足條件選取的Vi1，Vi2，…，Vit的方法數(shù)（其中1≤i1＜i2＜…＜it≤n，ij+1-ij≥ 2，1≤j＜t且n+i1-it≥2），即i1，i2，…，it.為圓排列1，2，…，n的一個排列，且滿足間距不小于2，其個數(shù)為所以：

特別地，當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）色使用次數(shù)不超過m次的正常染色多項式為：

推論2.2對于n圈k色正常染色，要求每2個相鄰的染了xi色的點的距離不小于s，則滿足條件的正常染色的色多項式為：

證明：設(shè)染了xi色的點為，其中≥k，則由定理2知，xi色恰好使用t次且每兩個染xi色的點的間距不小于s的正常染色的色多項式為又故：

定理4H0（i）

證明：H0（i）

證明：定理6

則容易知道：

下面計算

其中

而

綜上所述：

對于n圈k色的限制條件下的色多項式還有很多值得研究的地方，特別是在集合和映射的層面對n圈k色的限制條件下的色多項式進行的組合計數(shù)研究.

［1］陳瓊，常新德.有重復元素的圓排列和環(huán)排列的計算問題［J］.商丘職業(yè)技術(shù)學院學報，2008，7（2）：10-13.

［2］邱建霞，吳康.定元限距組合［J］.內(nèi)江師范學院學報，2009，10（24）：21-25.

［3］邱建霞.環(huán)狀限距組合計數(shù)的一些結(jié)果［J］.海南師范學院學報（自然科學版），2003，16（4）：6-10.

［4］王朝瑞.圖論［M］.3版.北京：北京理工大學出版社，2011：154-158.

［5］曹汝成.組合數(shù)學［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—），女（漢族），廣東梅州人，碩士研究生.研究方向：組合數(shù)學、數(shù)學課程論.

E-mail：1248639313@qq.com.