涂色问题

类型1(直线型结构)：用(2)mm种颜色给如图所示的由(2)nn个区域组成的直线型结构图涂色，相邻不同色总的涂法有11nNmm种.证明：由分步计数原理按序号逐个涂色即可。类型2(星型结构)：用(2)mm种颜色给如图所示的由(2)nn个区域组成的星型结构图涂色，则相邻不同色总的涂法有11nNmm种.证明：由分步计数原理按序号逐个涂色即可。类型3(环形结构)：用(2)mm种颜色给如图所示的由(2)nn个区域组成的环形结构图涂色，则相邻不同色总的不同涂法有？？种.如：如图，把一个圆分成(2)nn个扇形，每个扇形用红、白、蓝、黑四色之一染色，要求相邻扇形不同色，有多少种染色方法？1A2AnA⑤3A⑤解：设分成n个扇形时染色方法为na种(1)当n=2时1A、2A有24A=12种，即2a=12(2)当分成n个扇形，如图，1A与2A不同色，2A与3A不同色，，1nA与nA不同色，共有143n种染色方法，但由于nA与1A邻，所以应排除nA与1A同色的情形；nA与1A同色时，可把nA、1A看成一个扇形，与前2n个扇形加在一起为1n个扇形，此时有1na种染色法，故有如下递推关系：1143nnnaa1A⑤1A2A⑤2AnA⑤nA3A⑤类型3(环形结构)：用(2)mm种颜色给如图所示的由(2)nn个区域组成的环形结构图涂色，则相邻不同色总的不同涂法有？？种.1-1)1(nnnamma111nnNmm类型4(全连通型结构)：用()mmn种颜色给由n个区域组成的全连通型结构图(任何两个区域都连通，如图)涂色，则相邻不同色的涂法有nmNA种.证明：任何两个区域都连通，所以颜色各不相同。例1.某城市在中心广场建造一个花圃，花圃分为6个部分(如图).现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有种.(以数字作答)120例、四棱锥PABCD，用4种不同的颜色涂在四棱锥的各个面上，要求相邻不同色，有多少种涂法？ABCDP变式1：例、四棱锥PABCD，用4种不同的颜色涂在四棱锥的各个顶点上，要求相邻顶点不同色，有多少种涂法？ABCDP变式2：例2、用n种不同的颜色为下列两块广告牌着色，要求在1,2,3,4四个区域中相邻(有公共边界)的区域用不同的颜色，(1)若6n，为左图着色时共有多少种不同的方法？(2)若为右图着色时，共有120种不同的方法，求n的值.（1）（2）解：结构抽象如图，(1)涂法数为：366-2480A（）(2)涂法数为：44123120nnTAnnnn，∴5n（1）（2）例3.用6种不同的颜色为下图中的5个区域着色，要求相邻(有公共边界)的区域用不同的颜色，共有多少种不同的方法？解：结构抽象如右图，先涂124,,AAA的三角形，再涂3A，最后涂5A，共有3645A多少种不同的方法A1A3A4A5A6A2例4.用6种不同的颜色为下列两块广告牌着色，要求相邻(有公共边界)的区域用不同的颜色，共有多少种不同的方法？136245解：结构抽象如右图，466162(先涂1A，再涂线型结构23456AAAAA).例5.(2008重庆)某人有4种颜色的灯泡(每种颜色的灯泡足够多)，要在如题(16)图所示的6个点111,,,,,ABCABC上各装一个灯泡，要求同一条线段两端的灯泡不同色，则每种颜色的灯泡都至少用一个的安装方法共有种(用数字作答).C1B1CBAA1343(1211)216AC1B1CBAA1变式1、若下、上层对应点灯泡颜色允许相同，则共有（）种涂法；2、若下、上层有且只有一组对应点颜色相同，则有（）种涂法；3、若下、上层有且只有两组对应点颜色分别相同，则有（）种涂法；3、若下、上层有且只有三组对应点颜色分别相同，则有（）种涂法；例、如图，A、B、C三人相互传球，第一次球从A手中传出。经过7次传球后，球又回到A手中，问此三人不同的传球方式有种。设经过n次传球后，球又回到A手中，此三人不同的传球方式有na种，下面我们通过合理分步，恰当分类找出递推关系：第一步进行第一次传球：A传给其他人，有2种传球方法；第二步进行第二次传球：拿球者把球传给其他人，仍有2种传球方法；同理，第三次、第四次、……、第1n次传球都有2种传球方法，最后进行第n次传球，由于只能传给甲，故只有一次传球方法，相乘得12n种传球方法，但要注意第1n次传球不能传给甲，否则就不存在第n次传球，因此要去掉第1n次传球，球恰好传给甲的传球方法数，这就是由甲先传，经过1n次传球后球又回到甲手中的传球方法，显然，这里有1na种传球方法，所以有递推关系：112nnnaa，又易得，01a，由递推式可得：12122aa，23324322,26aaaa，454210aa，565222aa，676242aa.构造递推数列求解问题