圆环染色问题的公式解法

一、圆环染色问题计算公式 如图1所示,把一个圆环（从圆环“中心”出发,以环“半径”为界）分成n（n≥2）个扇形区域A1A2…An,现有m（m≥2）种不同颜色为这n个区域染色,要求相邻两个区域An与An＋1颜色不同,则共有an=（m-1）^n＋（-1）^n（m-1）种不同的染色方法。     

“传球”问题可看作“种植”问题的一个应用

文[1]把“传球”问题推广到一般情况:m(m≥2,m∈N*)个人互相传球,甲先发球作为第一次传球,经过n(n≥2,m∈N*)次传球后,球仍回到甲手中,则不同的传球方法有多少种?并推得一般结论an=mm-1[(m-1)n-1-(-1)n-1].图1圆文[2]把“种植”问题推广到一般情况:如图1,一个圆形花坛分为n(n≥3,n∈N*)个扇形,种植m(m≥3,m∈N*)种不同颜色的花,要求相邻两部分种植不同颜色的花,有多少种不同的种植方法?也推得一般结论:an=(m-1)n (-1)n(m-1).文[1]的结论难记,随手整理一下:an=1m[(m-1)n (-1)n(m-1)].这是文[2]的结论的m分之一!这激起了我的好奇心!经过探索…     

不定方程与组合问题

[问题一]试求不定方程x1+x2+x3+…+xm=n(m≥2,n≥2,m≤n)的正整数解的组数. 分析本题可用“挡板法”求解,由于x1≥1,x2≥1,…,xm≥l,把n分解成n个1,这n个1共有n-1个空挡.插入m-1块“挡板”,把n个1分成m个部分.则每一种情况对应不定方程的一组解,所以原不定方程共有Cm-1n组解.     

利用递推数列巧解圆环涂色问题

一、问题如图1在圆中,将圆分n等份得到n个区域M1,M2,M3,…,Mn（n≥2）.现取k（k≥2）种颜色对这n个区域涂色,要求每相邻的两个区域涂不同的两种颜色,试求涂色的方案有多少种？解设涂色方案总数为an（n≥2）,当n=2时,显然知：a2=k（k-1）.现探求{an}的递推公式：     

利用递推数列巧解圆环涂色问题

<正>一、问题如图1在圆中,将圆分n等份得到n个区域M1,M2,M3,…,Mn(n≥2).现取k(k≥2)种颜色对这n个区域涂色,要求每相邻的两个区域涂不同的两种颜色,试求涂色的方案有多少种?解设涂色方案总数为an(n≥2),当n=2时,显然知:a2=k(k-1).现探求{an}的递推公式:依题意知:区域M1有k种涂法,M2有k-1种涂法,……,Mn-1有k-1种涂法,若区域     

也谈“广义吉祥数”的计数问题

文[1]将自然数a的吉祥数意义推广为:如果a的各位数字之和等于m(m∈N ),那么称a为“广义吉祥数”,进而就所有不超过n 1位的各位数字之和为m的“广义吉祥数”的个数(记作A(n 1,m))的计数问题,给出如下4个定理:定理1当1≤m≤9,m∈Z,n≥0,n∈Z时,A(n 1,m)=Cnn m.定理2当10≤n≤19,m∈Z,n≥0,n∈Z时,A(n 1,m)=Cnn m-(n 1)Cnn m-10.定理3当9|m且0≤n<9m-1或9m且0≤n<[9m](m≥1,n∈Z,n≥0,n∈Z)时,A(n 1,m)=0.定理4当9|m且n≥9m-1或9m且n≥[9m](m≥1,m∈Z,n≥0,m∈Z)时,A(n 1,m)=∑[1m0]i=0(-1)iCni 1Cnn m-10i.本文也给出并证明该问题的一…     

"传球问题"的一般解法

问题包含甲在内的m(m≥2)个人练习传球,设传球n次,球首先从甲手中传出,第n次仍传给甲,共有多少种不同的传球方法?分析设第n次球传给甲的传球方法有an种,第n次球不传给甲的传球方法有bn种,对每个传球的人来说,每次传球的方法有m-1种,n次传球共有(m-1)n种方法.∴an+bn=(m-1)n.另外,第n+1次球传给甲,则第n次球必不传给甲,因而an+1=bn,∴an+an+1=(m-1)n.设cn=an(m-1)n,则cn+1+1m-1cn=1m-1,∴c-1=-1(c-1).又a1=0,c1=0,c1-1m=-1m,∴数列{cn-1m}是首项为-1m,公比为-1m-1的等比数列,∴cn=1m+(-1m).(-1m-1)n-1,∴an=1m(m-1)n+(-1)n.m-1m.例1甲、乙、…     

“传球”问题可看作“种植”问题的一个应用

文[1]把“传球”问题推广到一般情况：m（m≥2，m∈N^＊）个人互相传球，甲先发球作为第一次传球，经过n（n≥2，m∈N^＊）次传球后，球仍回到甲手中，则不同的传球方法有多少种？并推得一般结论     

THE BOUNDS ABOUT THE WHEEL-WHEEL RAMSEY NUMBERS

In this paper, we determine the bounds about Ramsey number R(W_m, W_n),where W_i is a graph obtained from a cycle C_i and an additional vertex by joining it to every vertex of the cycle C_i. We prove that 3m+1 ≤ R(W_m, W_n) ≤8m-3 for odd n, m ≥ n ≥ 3, m ≥ 5, and 2m + 1 ≤ R(W_m, W_n) ≤ 7m-2 for even n and m ≥ n + 502. Especially, if m is sufficiently large and n = 3, we have R(W_m, W_3) = 3m + 1.     

浅析隔板法的应用

众所周知，隔板法可以解决如下问题：求将n个相同元素分给m个不同对象（n≥m），每个对象至少有一个元素的方法数．此类问题可以视作在行-1个空中插入m-1块板，共有Cm-1n-1种方法．     

笛卡尔乘积图的圈点连通度

图G的圈点连通度,记为κ_c(G),是所有圈点割中最小的数目,其中每个圈点割S满足G-S不连通且至少它的两个分支含圈.这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度:(1)如果G_1≌K_m且G_2≌K_n,则κ_c(G_1×G_2)=min{3m+n-6,m+3n-6},其中m+n≥8,m≥n+2,或n≥m+2,且κ_c(G_1×G_2)=2m+2n-8,其中m+n≥8,m=n,或n=m+1,或m=n+11;(2)如果G_1≌K_m(m≥3)且G_2■K_n,则min{3m+κ(G_2)-4,m+3κ(G_2)-3,2m+2κ(G_2)-4}≤κ_c(G_1×G_2)≤mκ(G2);(3)如果G_1■K_m,K_(1,m-1)且G_2■K_n,K_(1,n-1),其中m≥4,n≥4,则min{3κ(G_1)+κ(G_2)-1,κ(G_1)+3κ(G_2)-1,2_κ(G_1)+2_κ(G_2)-2}≤κ_c(G_1×G_2)≤min{mκ(G_2),nκ(G_1),2m+2n-8}.     

着色问题的一种统一解法

有 n种颜色给 m个区域涂色 ,解决这样一类问题 ,比较容易产生“疑团”[1 ] .现介绍一种统一的方法 ,可以轻松地解决问题 ,疑团随之烟消云散 .图 1例 1　如图 1 ,用 5种颜色给图中的五个区域涂色 ,每个区域涂一种颜色 ,相邻区域不同颜色 ,那么共有多少种不同的涂色方法 ?解　我们把每一个区域画成一个小圆圈 ,相邻区域间用一条线段连接起来 ,就可以得到图 2 .图 2图 3用 5种颜色 ,有 A55种方法 ;用 4种颜色 (参见图 2 ) ,共有 3种情形 ,有 3A4 4种方法(相同的颜色打上同样的阴影 ,以下同 ) ;用 3种颜色 (参见图 3) ,有 A33种方法 ;所以共有…     

综合题新编选登

题188有一种摇奖盘是将一单位圆分成n（n≥3）个均匀的扇形区域构成的（如图1所示），现需将这n个扇形区域用三种不同颜色涂色，并要求三种颜色都要使用，且相邻的区域不能同色，如果把含有n（n≥3）价扇形区域摇奖盘的涂色方法数记为an（图1），     

例说一个计数模型的应用

问题 1将n个相同的球和(m-1)(m-1≥1)根相同的木条排成一行，问排法有多少种?     

不定方程x1+x2+…+xn=m的解的个数及在计数问题中的作用

不少计数问题归结为不定方程 x1+ x2+… + xn =m在特定条件下的解的个数问题便迎刃而解 .本文研究不定方程 x1+ x2 +… + xn =m在有关条件下的解的个数问题 ,并举例说明其在计数问题中的应用 .(注 :文中约定 :当 m 相似文献   

构造不定方程模型巧解几类组合问题

本文探究不定方程模型在几类组合问题中的简单应用,不定方程模型有下面两种情形.模型1不定方程x1 x2 … xm=n(其中m,n∈N ,且m≤n)有Cnm--11组正整数解.证明将n个相同小球排成一排,从球与球之间形成的n-1个空隙中,插入m-1个隔板,则把这n个小球分成m份,规定由隔板分成的从左至右     

Cauchy多边形数定理的一个简短证明

本文对下述事实给出一个简单的证明:每个自然数是m+2个m+2边形数之和. 设m≥1,一个m+2边形数是形如 Pm(k)=m/2(k2-k)+k,(k=0,1,2,…)的数.Fermat[3]断言:每一个自然数是m+2个m+2边形数之和.对于m=2,Lagrange[5]证明了每一个自然数是4个平方数P2(k)=k2之和.对于m=1,Gauss [4]证明了每一个自然数是3个三角数P1(k)=1/2(k2+k)之和,或等价的,每一个满足n≡3(mod 8)的正整数n都是3个奇数平方之和,Cauchy[1]对所有的m≥3证明了Fermat的断言,Legendre[6]进一步细化和推广了这一结果.对于m≥3且n≤120m,Pepin [8]给出了将n写成m+2个m+2边形数之和的显示表达的表,其中至少有m-2个取值于0或1.     

一个涂色问题的推广

文[1],[2]讨论了这样一个涂色问题(为了问题的严谨与简洁,这里对原题作了改写):题目将图1中n(n≥3)个扇形区域用三种不同颜色涂色,要求相邻的区域不能够同色,且三种颜色都要使用,求所有的涂色方法总数an.     

利用等可能性计算概率

许多通常要用全概公式或逆概公式来求解的问题事实上可以不用全概公式或逆概公式而直接利用等可能性。例 1　装有 m( m≥ 3 )个白球和 n个黑球的罐子中失去一球 ,但不知是什么颜色。为了猜测它是什么颜色 ,随机地从罐中摸取两个球 ,结果都是白球 ,问失去的球是白球的概率是什么 ?解法一　本题一般是利用全概公式和逆概公式来求解的。设 A={失去一球是白球 } ,B={随机地从罐中摸取两个球 ,结果都是白球 } ,由已知条件 P( A)= mm+n,P( A) =nm+n,P( B|A) =C2m- 1C2m+n- 1,P( B|A) =C2m C2m+n- 1,本题求的是 P( A|B)。由全概公式P( …     

C_n~(m-1),C_n~m,C_n~(m+1)何时成等差数列

职高数学课本中有这样一道习题; 已知C_n~(m-1)=C_n~m=C_n~(m+1),求n和m. 这个习题的答案是n=34,m=14和n=34,m=4 0.此题可演变出一个不定方程 2C_n~m=C_n~(m-1)+C_n~(m-1) (1)这个方程的解是怎样的呢?C_n~(m-1),C_n~(m+1)什么时候成为一个等差数列呢?让我们来研究一下这两个问题,作为复习上面习题的引伸. 探求方程(1)的解,即求n和m的值。(1)经过变形,可以写成一个关于m的二次方程