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

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

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

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

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

色多項(xiàng)式；n圈k色；組合計(jì)數(shù)

0　引言

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

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

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

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

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

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

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

推論1給定一個(gè)位置顏色的色多項(xiàng)式為：

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

2　主要定理

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

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

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

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

下面求滿足條件選取的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的一個(gè)排列，且滿足間距不小于2，其個(gè)數(shù)為所以：

特別地，當(dāng)t=0時(shí)，則fn，k，xi，0=fn，k-1=（k-2）n+（-1）n（k-2）.當(dāng)時(shí)t=1，則fn，R，xi，1=n（k-1）（k-2）n-2.

推論2.1對(duì)于n圈k色正常染色，要求xi（i=1，2…，R）色使用次數(shù)不超過(guò)m次的正常染色多項(xiàng)式為：

推論2.2對(duì)于n圈k色正常染色，要求每2個(gè)相鄰的染了xi色的點(diǎn)的距離不小于s，則滿足條件的正常染色的色多項(xiàng)式為：

證明：設(shè)染了xi色的點(diǎn)為，其中≥k，則由定理2知，xi色恰好使用t次且每?jī)蓚€(gè)染xi色的點(diǎn)的間距不小于s的正常染色的色多項(xiàng)式為又故：

定理4H0（i）

證明：H0（i）

證明：定理6

則容易知道：

下面計(jì)算

其中

而

綜上所述：

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

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

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

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

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

［5］曹汝成.組合數(shù)學(xué)［M］.廣州：華南理工大學(xué)出版社，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ù)學(xué)、數(shù)學(xué)課程論.

E-mail：1248639313@qq.com.