- 1、本文档共7页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
排列组合专题之染色问题通法(公式)
排列组合专题之染色问题
【引例】
引例1(在一个正六边形的6个区域栽种观赏植物,如右图,要求同一块中种同
一种植物,相邻的两块种不同的植物(现有四种不同的植物可供选择,则有
________种栽种方案(
引例2(某城市在中心广场建造一个花圃,花圃分为6个部分(如图),现要栽种
4种不同颜色的花,每部分栽种一种且相邻部分不能栽种同样颜色的花,不同的栽
种方法有_____种((以数字作答)
1【分析】首先栽种第1部分,有种栽种方法;C4
然后问题就转化为用余下3种颜色的花,去栽种周围的5个部分(如右图所
示),
此问题和引例1是同一题型,因此我们有必要对这一题型的解法做一深入探
讨。【剖析】
为了深入探讨这一题型的解法,
(1)让我们首先用m(m?3)种不同的颜色(可供选择),去涂4个扇形的情形
(要求每一个扇形着一种颜色,相邻扇形着不同颜色),如图所示
以1和3(相间)涂色相同与否为分类标准:
?1和3涂同一种颜色,有m种涂法;2有m-1种涂法,4也有m-1种涂法,
?共有种涂法。mmm,,,,(1)(1)
2?1和3涂不同种颜色,有种涂法;2有m-2种涂法,4也有m-2种涂法,Am
2?共有种涂法。Amm,,,,(2)(2)m
2432综合?和?,共有+种涂法。mmm,,,,(1)(1)Amm,,,,(2)(2),,,,mmmm463m
(,)下面来分析引例1
以A、C、E(相间)栽种植物情况作为分类标准:
?A、C、E栽种同一种植物,有4种栽法;B、D、F各有3种栽法,
?共有4×3×3×3,108种栽法。
2222?A、C、E栽种两种植物,有种栽法(是4种植物中选出2CCAC4432
22种,是A、C、E3个区域中选出2个区域栽种同一种植物,是CA32
选出的2种植物排列),B、D、F共有3×2×2种栽法(注:若A、C栽种同一种
植物,则B有
3种栽法,D、F各有2种栽法),
222?,,,,共有种栽法。CCA322432432
3?A、C、E栽种3种植物,有种栽法;B、D、F各有2种栽法,A4
3?共有×2×2×2,192种栽法。A4
综合?、?、?,共有108+432+192=732种栽法。
1
(,)上述(1)、(2)给出了“设一个圆分成P,P,…,Pn,共n(n为偶数)个扇
形,用m种不同的颜色12
对这n个扇形着色(m?3,n?3),每一个扇形着一种颜色,相邻扇形着不同颜
色,共有多少种不同
的着色方法”这类问题的一般解题思路:即以相间扇形区域的涂色情况作为分
类标准,再计算其余
相间扇形区域的涂色种数。
(4)那么,“设一个圆分成P,P,…,Pn,共n(n为奇数)个扇形,用m种不同
的颜色对这n个扇形12
着色(m?3,n?3),每一个扇形着一种颜色,相邻扇形着不同颜色,共有多少种
不同的着色方法”这
类问题的解题思路又如何呢,
【分析】
对扇形P有m种涂色方法,1
扇形P有m,1种涂色方法,2
扇形P也有m,1种涂色方法,3
…………
扇形P也有m,1种涂色方法(n
n,1于是,共有种不同的涂色方法。但是,这种涂色方法可能出现P与P着色
相同的情形,这mm,,(1)1n
n,1是不符合题意的,因此,答案应从中减去这些不符合题意的涂色方法。那
么,这些不符合题mm,,(1)
意的涂色方法,又怎样计算呢,这时,把P与P看作一个扇形,其涂色方法相
当于用m种颜色对n,1(n1n
,1为偶数)个扇形涂色(这种转换思维相当巧妙)。而用m种颜色对偶数个扇形
的涂色问题,已在上述的(,)中给出了解题思路。
下面,就让我们把这种解题思路应用于引例2(
【分析】
1?首先栽种第1部分,有种栽种方法;C4
?然
文档评论(0)