石向阳
许多组合问题看似与方程无关，若能去伪存真，转换思维角度，转化为不定方程整数解的模型，则往往能化繁为简、柳暗花明.1不定方程整数解的有关结论
定理1不定方程x1+x2+…+xk=n（k，n∈N+）的非负整数解的个数为Cnn+k-1.
证法1将不定方程x1+x2+…+xk=n的任意一组非负整数解（x1，x2，…，xk）对应于一个由n个圆圈“○”和k-1个“+”组成的如图○…○x1个+○…○x2个+…+○…○xk个所示的排列，每段圆圈“○”的个数即为原方程的一组非负整数解，易证对应关系是一对一的.
所以不定方程x1+x2+…+xk=n的非负整数解的个数就是n个圆圈“○”和k-1个“+”组成的直线排列数，即在n+k-1个位置中选k-1放置“+”（或选n个位置放置圆圈“○”），因此共有不同的排法种数为Ck-1n+k-1=Cnn+k-1.
证法2对不定方程x1+x2+…+xk=n的任意一组非负整数解（x1，x2，…，xk），令y1=x1+1，y2=x1+x2+2，…，yk=x1+x2+…+xk+k，则1≤y1 定理2不定方程x1+x2+…+xk=n（k≥2，n≥2，k≤n）的正整数解的个数为Ck-1n-1. 证法1设想将n个1排成一排，这n个1之间有n-1个空档，从n-1个空档中选k-1个放入k-1个“+”，共有Ck-1n-1种放法，这k-1个“+”把n个1分成k段，各段1的个数即为原方程的一组正整数解，这样“+”的每一种放法就对应着原不定方程的一组正整数解，所以原不定方程共有Ck-1n-1组解. 证法2令yi=xi-1，其中xi≥1，不定方程x1+x2+…+xk=n的正整数解与不定方程y1+y2+…+yk=n-k非负整数解之间建立了一一对应关系，所以不定方程x1+x2+…+xk=n的正整数解组（x1，x2，…，xk）的组数与不定方程y1+y2+…+yk=n-k非负整数解组（y1，y2，…，yk）的组数相等，由定理1知，方程y1+y2+…+yk=n-k有Cn-k（n-k）+k-1=Cn-kn-1=Ck-1n-1个非负整数解，所以方程x1+x2+…+xk=n有Ck-1n-1个正整数解.2利用不定方程整数解的结论解有限制条件的不定方程或不定方程组的整数解的个数问题 例1求方程2x1+x2+x3+…+x10=3的非负整数解的个数. 解析由题意，x1=0，1，故分情况讨论如下： 若x1=0，则x2+x3+…+x10=3，该方程非负整数解的个数为：C39+3-1=165； 若x1=1，则x2+x3+…+x10=1，该方程非负整数解的个数为：C19+1-1=9. 综上，非负整数解的个数为：165+9=174个. 例2求方程x+y+z=2010满足x≤y≤z的正整数解x，y，z的个数. 解析首先由定理2知，方程x+y+z=2010的正整数解的个数为C22009=2009×1004. 把x+y+z=2010满足x≤y≤z的正整数解分为三类： 1x，y，z均相等的正整数解的个数显然为1； 2x，y，z中有且仅有两个相等的正整数解的个数，易知为1003个； 3x，y，z两两均不相等的正整数解个数为k. 易知1+3×1003+6k=2009×1004，解得k=335671，从而方程x+y+z=2010满足x≤y≤z的正整数解的个数为1+1003+335671=336675 例3在世界杯足球赛前，F国教练为了考察A1，A2，…，A7这七名队员，准备让他们在三场训练比赛（每场90分钟）中都上场.假设在比赛的任何时刻，这些队员中有且仅有一人在场上，且A1，A2，A3，A4每人上场的总时间（以分钟为单位）均能被7整除，A5，A6，A7每人上场的总时间（以分钟为单位）均能被13整除.如果每场换人次数不限，那么，按每名队员上场的总时间计算，共有多少种不同的情况. 解析设第i名队员上场的时间为xi分钟（i=1，2，3，…，7），问题即求不定方 程x1+x2+…+x7=270在条件7xi（1≤i≤4）且13xj（5≤j≤7）下的正整数解的组数.由条件，设x1+x2+x3+x4=7m，x5+x6+x7=13n（m≥4，n≥3）.于是m、n即是不定方程7m+13n=270的一组正整数解.由m=270-13n7≥4，易得3≤n≤18，（n∈N）.进而得到方程的三组正整数解： m=33， n=3，m=20， n=10，m=7， n=17，设xi=7yi（1≤i≤4），xj=13yj（5≤j≤7）. 所以本题转化为求方程组y1+y2+y3+y4=33， y5+y6+y7=3，y1+y2+y3+y4=20， y5+y6+y7=10， y1+y2+y3+y4=7， y5+y6+y7=17，的正整数解的组数.由分步乘法计数原理和分类加法计数原理及定理2知共有正整数解C332C22+C319C29+C36C216=42244组.3利用不定方程整数解的结论解排列组合中的计数问题 利用不定方程整数解的结论解决排列组合中的计数问题，一般用于相同元素的有序分配问题，如指标数、个数、人数等相同的事物的数量分配问题.
3.1投球入盒问题
例4把2016个不加区别的小球分别放在10个不同的盒子里，使得第i个盒子里至少有i个球（i=1，2，…，10），问不同放法的总数是多少？
解析先在第i个盒子里放入i个球（i=1，2，…，10），即第1个盒子里放入1个球，第2个盒子里放入2个球，…，这时共放了1+2+3+…+10=55个球.还剩余2016-55=1961个球.故问题转化为把1961个球任意放入10个盒子里（允许有的盒子里不放球），即为不定方程x1+x2+…+x10=1961的非负整数解的个数，由定理1知有C19611961+10-1=C91970种不同放法.
3.2名额分配问题
例5将24个志愿者名额分配给3个学校，则每校至少有一个名额且各校名额互不
相同的分配方法共有多少种？解析设分配给3个学校的名额数分别为x1，x2，x3，则每校至少有一个名额的分法数为不定方程x1+x2+x3=24的正整数解的个数，由定理2得不定方程x1+x2+x3=24的正整数解的个数为C223=253.又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分配方法有31种.
综上知，满足条件的分配方法共有253-31=222种.
3.3染色问题
例6用红、橙、黄、绿、青、蓝、紫七种颜色的一种，或两种，或三种，或四种，分别涂在正四面体各个面上，一个面不能用两色，也无一个面不着色的，问共有几种着色法？
解析设红色涂了x1个面，橙色涂了x2个面，…紫色涂了x7个面，则x1+x2+…+x7=4，正四面体着色方法与方程的非负整数解建立了一一对应的关系.由定理1知该不定方程有C47+4-1=210组非负整数解，所以正四面体共有210种着色方法.
3.4掷骰子问题
例7三粒骰子同时掷出，有多少种不同的结果？
解析设掷出1点的有x1粒，设掷出2点的有x2粒，…，设掷出6点的有x6粒，则有x1+x2+…+x6=3.掷骰子的结果与方程的非负整数解建立了一一对应的关系.由定理1知该不定方程有C36+3-1=C38=56组非负整数解，所以共有56种不同的结果.
3.5进站问题
例8某民航站共有1到4个入口，每个入口处每次只能进一个人，一小组4个人进站的方案数有多少种.
解析设第1，2，3，4个入口分别进x1，x2，x3，x4人，则xi≥0且x1+x2+x3+x4=4，由定理1知不定方程x1+x2+x3+x4=4的非负整数解的个数C44+4-1=C37即为4个人进站的分组方法数；由于每个入口处每次只能进一个人，按第1，2，3，4个入口顺序同时通过入口排成一列，就每一分组方法将四个人全排列有A44种方法，所以共有不同进站方法C37·A44=840种.
3.6开关灯问题
例9街道上有10盏路灯，要求晚上关掉其中4盏，且为了方便行人，相邻的路灯不允许关掉.问共有多少种关灯的方法？
解析先考虑关着的灯，再考虑开着的灯，如图：○○○○，有4盏灯关着，它们之间形成了5个空，这5个空共要插进6盏灯作为开着的灯，设从左到右第i个空共有xi（i=1，2，3，4，5）盏灯开着，则有x1+x2+x3+x4+x5=6，等价于（x1+1）+x2+x3+x4+（x5+1）=8（x1+1，x2，x3，x4，x5+1≥1，且xi∈N），由定理2知，共有C47=35种方法，所以共有35种开关灯的方法.
3.7在线性规划中整点个数问题
例10在直角坐标系xOy中，已知△ABC三边所在直线方程分别为x=0，y=0，x+y=4，则在△ABC内部（包括边界）的整点个数是多少？
解析此类题常见解法是画图描出整点，然后数一下.实际上满足题意的整点（x，y）必有x+y≤4，且x≥0，y≥0.若令z=4-（x+y）则z≥0且z为整数.所以x+y+z=4，该方程非负整数解的组数即为整点个数.所以整点个数是C44+3-1=C26=15.
3.8n项展开式的项数问题
例11试问（a+b+c）10的展开式共有多少项？
解析（a+b+c）10展开式每一项均可表示为ax1·bx2·Cx3，其中xi≥0（i=1，2，3）且x1+x2+x3=10.因此，求展开式中共有多少项，即求不定方程x1+x2+x3=10共有多少组非负整数解.由定理1知，此不定方程解的个数为C1010+3-1=C212=66，所以展开式共有66项.
同理可得（a1+a2+…+an）m展开式共有Cmn+m-1项.
3.9广告问题
例12电视台在n天内共播出r次商业广告，问若每天至少播p次广告（np≤r），就每天播出广告的次数而言，共有几种播出方法？
解析设第i天播出广告xi次，由题设知：x1+x2+…+xn=r，xi≥p（i=1，2，…，n），令yi=xi-p，则y1+y2+…+yn=r-np≥0，故问题转化为求上述不定方程的非负整数解的个数，由定理1知广告播放的方法数为Cr-np（r-np）+n-1.
3.10有条件的环形排列问题
例138个女孩和25个男孩围成一圈，任意两个女孩之间至少站两个男孩，那么，共有多少种不同的排列方法.（只要把圈旋转一下就重合的排法认为是相同的）.
解析以8个女孩为组长，将25个男孩分入该8组，每组内男孩数记为x1，x2，…，x8，
则x1+x2+…+x8=25，（xi≥2，i=1，2，…8），设xi-1=yi（i=1，2，…，8），即得y1+y2+…+y8=17，（yi≥1，i=1，2，…，8），于是由定理2可求出符合条件的方程组的解的个数为C8-117-1=C716，即25个男孩分入8组，每组至少2人的分组方法有C716种.
8个组排成每组以女孩为头的圆排列有（8-1）！=7！（一个8个元素的圆排列包括8个不同的线性排列，设8个元素的圆排列数为N，则8N=A88，所以N=A77）种排列方法，再将25个男孩站入的方法数为25！.
所以总的排列数为C716·7！·25！=16！·25！9！.
3.11比赛过程的种数问题
例14甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛.双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，……直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程.求所有可能出现的比赛过程的种数.
解析先考虑甲队获胜的比赛过程，设甲队队员第i号队员胜了xi场，（i=1，2，…，7），则x1+x2+…+x7=7，于是甲队获胜的比赛过程与方程x1+x2+…+x7=7的非负整数解组（x1，x2，…，x7）构成一一对应，由定理1知方程x1+x2+…+x7=7有C67+6=C613组非负整数解，所以甲队获胜的比赛过程有C613种，同理乙队获胜的比赛过程也有C613种，故不同的比赛过程共有2C613=3432种.
3.12集合、映射个数问题
例15已知两个实数集合A={a1，a2，…，a100}与B={b1，b2，…，b50}.若从A到B的映射f使得B中每个元素都有原像，且f（a1）≤f（a2）≤…≤f（a100），求这样的映射的个数.
解析不妨设b1 例16设集合M={1，2，3，…，14}，Ma={a1，a2，a3}，Ma为M的子集，且满足a1+6≤a2+3≤a3，求Ma的个数. 解析由a1≥1，a2-a1≥3，a3-a2≥3，14-a3≥0，令a1=x1，a2-a1=x2，a3-a2=x3，14-a3=x4，则x1+x2+x3+x4=14，问题即求不定方程在x1≥1，x2≥3，x3≥3，x4≥0下的整数解的组数，又方程转化为x1+（x2-2）+（x3-2）+（x4+1）=11.令x1=y1，x2-2=y2，x3-2=y3，x4+1=y4，而y1+y2+y3+y4=11的正整数解的组数是C310.所以符合条件的Ma的个数有C310=120个. 以上问题虽然背景各异，但经充分挖掘后发现本质是相同的，其结果均与不定方程的整数解有一一对应的关系.解题的关键是建立不定方程模型.问题一般有三类，第一类是中间的可以一个也没有，用定理1求解（如例4、例6、例7、例8、例10、例11、例14）；第二类是中间的个数至少有一个，用定理2求解（如例5、例9、例15）；第三类是中间的个数多于1个，这类有约束条件的相同元素的有序分配问题，相对来讲破解较难，需要通过转化问题才能用不定方程来处理.转化的关键是使问题变成第一个类型（如例12），当然也可以转化第二个类型（如例13、例16）.4不定方程非负整数解与重复组合数的关系 从k个不同的元素中，取n个允许重复的元素而不考虑其次序，被称为从k个不同元素中取n个允许重复的组合，简称为n-重复组合，允许重复的组合数常常记作Hnk. 设（a1，a2，…，an）是取自{1，2，…，k}中的任一n-可重复组合，并设a1≤a2≤…≤an，令bi=ai+i-1（1≤i≤n），从而b1=a1，b2=a2+1，b3=a3+2，…，bn=an+n-1，显然下面两组数是一对一的： a1≤a2≤…≤an，1≤a1 设A={（a1，a2，…，an）|ai∈{1，2，…，k}，a1≤a2≤…≤an}， B={（b1，b2，…，bn）|bi∈{1，2，…，k+n-1}，b1 其一、上述证明，与定理1的证法2大同小异，请仔细体味其中小异妙在何处. 其二、设n-可重复组合a1，a2，…，an中含有x1个1，x2个2，…，xk个k，则x1+x2+…+xk=n（k，n∈N+），显然（a1，a2，…，an）与不定方程x1+x2+…+xk=n的解（x1，x2，…，xk）一一对应. 其三、允许重复的组合的典型模型是把n只相同颜色的球放到k个编号不同的盒子中，而且每个盒子放球数不加限制，xi代表第i（i=1，2，3，…，k）个盒子中所放的球的个数，那么就有x1+x2+…+xk=n（k，n∈N+），不同的放法就对应该方程的不同的解. 对例6我们用重复的组合数来理解，易知，正四面体的相关位置，没有先后顺序，即先涂或后涂哪个面，没有什么不同，所以是组合问题；这四个面可以分别用一种，或两种，或三种，或四种颜色，故是一个重复组合问题，即可归结为4只相同颜色的球放到7个编号不同的盒子中，每个盒子放球数不加限制，故有着色法H47=C47+4-1=210. 对例7我们用重复的组合数来理解，因为掷三粒骰子等价于从六个数1，2，3，4，5，6中允许重复的选取三个数，故不同结果的数目是H36=C36+3-1=C38=56. 从重复的组合数来理解不定方程的非负整数解，对于培养思维的深刻性、逻辑性大有裨益.
