一类染色问题的计数公式

数学竞赛

2005年第1

期9

命题与解题

一类染色问题的计数公式

邹　明

(山东省青岛第二中学,262101)

　　给彼此相连的若干区域染色,且任何相

邻的2个区域或间隔的2个区域染不同的颜色,是近年来高考和数学竞赛中的一类常见问题.下面运用排列组合的两个基本原理———加法原理、乘法原理,给出此类问题的几个一般情形的计数公式.

命题1　用m(m≥2)种不同的颜色,证明:如图1,记符合要求的染色方案为

an种,则区域A1有m种染法,区域A2,A3,

…,An各有m-1种染法.这包括了An与A1染同色或不同色两类:若区域An1染同色,AnA1n-1an-;若An1,则符合要求,有

n种染法.故有

an+an-1=m(m-1)

n-1

中n(的区域1,…,n色,且任何相邻的2个区

图1

.

域染不同的颜色.则不同的涂色方案种数为

nn

an=(-1)(m-1)+(m-1).

　　收稿日期:2004-01-19

n

两端同乘以(-1)得(-1)nan-(-1)n-1an-1

=-m(1-m)

n-1

.

两端求和得

nk=3

∑

kk-1

[(-1)ak-(-1)ak-1]

　　(提示:设有1,2,3,4,5五种颜色给四棱锥

S-ABCD染色.由于S、A、B所染颜色不同,则有

270,在条件7|xi(1≤i≤4),且13|xj(5≤j≤7)下的

正整数解的组数.由条件,设x1+x2+x3+x4=7m,

x5+x6+x7=13n(m≥4,n≥3).于是,m、n即是不

5×4×3=60种染色方法.设S、A、B已染好,再分类

讨论,C、D有7种染法.共有60×7=420种染法.)

4.在世界杯足球赛前,F国教练为了考察A1,A2,…,A7这7名队员,准备让他们在3场训练比赛

定方程7m+13n=270的一组正整数解.m=

≥

4,易得3≤n≤18,(n∈N).解方程组得

7

23232

共有正整数解C332C2+C19C9+C6C16=42244组.)

(每场90分钟)中都上场.假设在比赛的任何时刻,

这些队员中有且仅有1人在场上,且A1,A2,A3,A4每人上场的总时间(以分钟为单位)均能被7整除,

A5,A6,A7每人上场的总时间(以分钟为单位)均能

5.如图2,在1个正六

边形的6个区域栽种观赏植物,要求同1区域种同一种植物,相邻的2区域种不同的植物.现有4种不同植物可供选择.则有

种栽种方案.

(2001,全国高中数学联赛)

图2

被13整除.如果每场换人次数不限,那么,按每名队员上场的总时间计算,共有多少种不同的情况?

(2002,全国高中数学联赛)

(提示:设第i名队员上场的时间为xi分钟(i=1,2,…,7),问题即求不定方程x1+x2+…+x7=

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库一类染色问题的计数公式在线全文阅读。