数学竞赛
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=
染色问题中的公式法_专业资料。在排列组合复习中,常常碰到染色问题.染色问题...这类问题旨在考察分类计数原理及分步计数原理的应用,解答时容易出现重算或漏算的...
问题,建立两个折线染色计数 为方便起见,记t在U中的补集为t(i=1,2,…,m),则根据德摩根公式和客斥原理 模型,并探讨其在高考与竞赛中的应用,统一地解决一类...
关于3×n棋盘的染色计数公式_专业资料。文章对2×n棋盘的2个染色计数公式进行推广,从而得到了约束条件下2×n棋盘的2个染色计数公式。...
环形染色问题的公式解法_专业资料。定理 如图把一个圆分成n(n≥2)个扇形... 关于3×n棋盘的染色计数... 43人阅读 3页 2.00 超声波染色上染率...
染色问题的计数方法 9页 免费 一类染色问题的计数公式 3页 免费 细胞计数及... 如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击...
环形染色问题的公式解法_数学_高中教育_教育专区。中学数学杂志2008年第9期 £... 一类染色问题的计数公式 3页 免费 为你的公式轻松着色 暂无评价 2页 1....
与染色有关的计数问题 一、对区域染色问题 对区域的染色问题常见方法: (1)直接根据两个基本原理求解; (2)根据所用颜色的种 数分类; (3)根据某两个区域同色...
容斥原理:在一些计数问题中,经常遇到有关集合元素个...“排除”加了两次的元素) 总结为公式:
与染色有关的计数问题(免费)_数学_自然科学_专业资料。高中数学 与染色有关...每部分栽种一种且相邻 部分不能栽种同一样颜色的花,不同的栽种方法有 种 (...
分析:按照分步计数原理,先为 A 染色共有 5 种, ...把染色问题与某个熟知的公式、图形联系起来,并恰当...1 种染色方法中包含了两类,一类是区域 1 与区域 ...
热门文档