则由A、B之间存在一一对应，故|A|=|B|=Crn+r－1.
Ⅱ．枚举法
所谓枚举法就是把集合A中的元素一一列举出来，从而计算出集体A的元素个数。
它是最基本，也是最简单的计算数方法。
应用枚举法计数的关键在于一一列举集合中的元素时必须做到既不重又不漏。
Ⅲ．映射法（略，见第一讲）
Ⅳ．分类计数原理与分步计数原理
分类计算原理完成一件事，有几种方式，第一种方式有m种方法，第二种方式有n种方法，……最后一种方式有r种方法.不管采取哪一种方法都能完成这件事，则完成这件事的方法总数为m+n+…+r.
分步计数原理完成一件事，有几个步骤，第一步有m种方法，第二步有n种方法，…，最后一步有r种方法，要完成这件事，必须通过每一步，则完成这件事的方法总数为m·n……r.
应用分类计数原理的关键在于分划，即把一个所要计数的集合S分划成一些两两不交的小集合，且使每个小集合都便于计数.
应用分步计数原理的关键在于分解，即把一个所要计数的集合S分解成若干个集合的乘积.
对一个集合S的分划或分解，没有一般方法，应由具体问题而定，而这正是应用两个原理解题的难点与技巧所在.
Ⅴ．递推方法
将与正整数有关的数字问题，通过寻求递推公式，或通过递推公式，而使问题得到解决的方法，叫做递推方法.
递推方法几乎对所有数学分支都具有重要的作用，当然对组合计数就更不例外了，它是组合计数的常用方法.
应用递推方法解题，会遇到如下两类问题：
一是如何找到满足题设条件的递推公式，二是推理计算.详见例题.
Ⅵ．母函数法
母函数是一种非常有用的方法.这种方法的最早系统叙述见于Laplace在1812年出版的名著《概率解析理论》中.这种方法思想简单，把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成幂级数间的运算关系，最后由幂级数来确定离散数列的构造。
简要地说，母函数方法是将一个有限或无限的数列
{ak}={a0,a1,a2,…,ak,…}
和如下形式的多项式
f（x）=a0+a1x+a2x2+…+akxk+…
联系起来，构成对应关系{ak}←→f（x）
这个f（x）就称为{ak}的母函数或生产函数.意思是这个数列{ak}是由多项f（x）产生的.
例如：
组合数列
的母函数是
.因为由二项式定理可得
=
是最常见的母函数.
设{an}与{bn}是两个结定的数列，为了确定它们之间的某种关系，可分别写出二者所对应的母函数，再研究这两个母函数间的某种关系从而确定两个数列之间的关系，这便是母函数方法解题的基本思想.
Ⅶ．子集类
一个n元素合X有2n个子集A1，A2，…
，如果以它的部分子集作为元素，又可得到一个集合F={A1，A2，…，Ak}（1≤k≤2n），这个集合F的称为原来集合X的一个子集类.
应用子集类知识可以帮助我们解决如下二类问题：
a．什么时候可以把一个整数（集合）写成若干个满足一定条件的整数（子集）之和（并）.
b．在可以写的情况上有多少种写法.前者是存在性问题，后者组合计数问题.
Ⅷ．数学归纳法
塞题精讲
例1数1447，1005和1231有某些共同点，即每个数都是首位为1的四位数，且每个四位数中恰有两个数字相同，这样的四位数共有多少个？
（第1届AIME试题，1983年）
【解】符合条件的四位数必含有一个1或者两个1.
（1）含有两个1的情形
从除1之外的其余9个数字中任取两个，有C29种取法，再与其中的一个1组成任意排列的三位数，有P33种，这样构成的首位为1的四位数共有N1=C29P33（个）.
（2）只含有一个1的情形
从其余的9个数字中任取两个，有C29种取法，其中一个数字被重复选出，有C12种，这样的三个数字组成的三位数共有
，这样构成的首位为1的四位数共有
（个）.
因此，符合题意的四位数共有N=N1+N2=432（个）.
例2在xy平面上，顶点的坐标（x,y）满足1≤x≤4，1≤y≤4，且x,y是整数的三角形有多少个？
（第44届AHSME试题，1993年）
【解】由题设知，在xy平面上有16个整点，共有C316=560个三点组，要从中减去那些三点共线的.
平面上有4条垂直线和4条水平线，每条上有4个点，这8条线上含有8C43=32个三点共线的三点组（如图I—3—3—1）.
类似的，在斜率为±1的线上三点共线的三点组有2C43+4C33=8+4=12（个）（如图I—3—3—2）.
此外，没有其他的三点共线的三点组，所以，组成的三角形的个数是
560－32－12=516（个）.
例3方程2x1+x2+x3+…+x10=3有多少个非负整数解.
【解】设（x1,x2,…,x10）是原方程组的一个非负整数解，由于xi≥0（i=1,2,10），
因此，
2x1≤2x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=3
即2x1≤3，所以x1=0，1.下面分两种情形：
（1）x1=0，则x2+x3+…+x10=3,所以xi=0,1,2,3（i=2,3,…，10）.
如果有某个xi=3，则其他xi=0，这样解有C19=9（个）.
如果某个xi≠3，若某个xi=2，则必有一个xj=1，i≠j，2≤i,j≤9，这样解有C19·C18=72（个）.
如果对每个xi≠2，3，则x2,x3，…，x10中必有三个xi（2≤i≤10）为1，这样解有C93=84（个）.
（2）x1=1，则x2+x3+…+x10=1,因此x1，x2，x3…x10中仅有一个是1，这样解有C19=9（个）.
于是原方程组有
个非负整数解.
例4设S={1，2，…，n}，A为至少含有两项的、公并非为正的等差数列，其项部都在S中，且添加S的其他元素等于A后均不能构成与A有相同公差的等差数列，求这种A的个数（这里只有两项的数列也看做等差数列）.
（全国高中数学联赛，1991年）
【解】构造具有如下要求的集合A：
把A中的元素按从小到大的次序排好后，在其最大元素后面添上S的任何元素均不能构成具有原公差的等差数列。
这时，当A的首项与公差一旦确定，其整个集合A也即确定，不妨设A的首项为a，公差为d，则
a=1,d=1,2,…,n－1时的集A有n－1个；
a=2,d=1,2,…,n－2时的集A有n－2个；
……
a=n－1，d=1时的集A有1个.
因此，所求A的总个数为1+2+…+（n－1）=
例5在扔硬币时，如果用Z表示正面朝上，F表示反面朝上，那么扔硬币的序列就表示为用Z和F组成的串，我们可以统计在这种序列中正面紧跟着反面（ZF）的出现次数，正面紧跟着正面（ZZ）的出现次数……，例如序列
ZZFFZZZZFZZFFFF
是15次扔币的结果，其中有5个ZZ，3个ZF，2个FZ，4个FF.
问：
有多少个15次扔硬币的序列，恰好有2个ZZ，3个ZF，4个FZ，5个FF？
（第4届AIME试题，1986年）
【解】符合题意的序列具有如下两种可能形式：
（1）F带头的：
F…FZ…ZF…；
（2）Z带头的：
Z…ZF…FZ…ZF…F.
由于题设要求的序列恰有3个ZF，则序列属于第（ii）类的，应具有如下形式
Z…ZF…FZ…ZF…FZ…ZF…F.
其中只有2个FZ，达不到4个FZ，故不可能，所以符合题设的序列只能是第（i）种形式.
由于序列恰有4个FZ，则在考虑序列中恰有两个ZZ的情况下可分为如下两类：
ZZZZZZ，①
ZZZZZZ. ②
以及Z的不同位置，其中的空格之处应填F.
设每个空格处填F的个数依次为x1,x2,x3,x4，则
x1+x2+x3+x4=9
这相当于求其正整数解的个数，显然有C38=56.
另一方面，对于①，ZZZ的位置有4种，对②，ZZ，ZZ，Z，Z的排列方法有6种，所以Z的排列方法有10种.
所以，符合题意的序列有10×56=560（个）.
例6△ABC的顶点为A=（0，0），B=（0，420），C=（560，0），一个骰子的六个面分别标上两个“A”，两个“B”，两个“C”.从△ABC内部选出一点P1=（k,m），重复扔骰子，依下列法则选出点P2，P3，…：
如骰子露出标记L的那面L∈{A，B，C}，且刚刚选为Pn，那么Pn+1选为
的中点，已知P7=（14，92），问k+m=?
（第11届AIME试题，1993年）
【解】首先应注意到因P1在△ABC内，则以后的所有Pk在△ABC内.下面，我们将证明一旦任何后继的Pk给出，则可惟一地确定P1.
假定PK=（xk,yk），因Pk在△ABC内，则有
00<420xk+560yk<420·560.
若掷出A，则
于是Pk+1所在的可能范围被限制在原三角形的
之内（图I—3—3—3中的一部分），显然Pk+1在I内，从而有
420xk+1+560yk+1<
×420×560.
同样掷出B，则Pk+1在II内，yk+1>210.
若掷出C，则Pk+1在Ⅲ内，xk+1>280.
所以，对k≥2，Pk必在I，II，III之一内，
且由它的前一点惟一确定.
例如，若Pk（xk,yk），位于II内，则Pk必为BPk－1的
中点，这时Pk－1=2Pk－B=（2xk,2yk－420）.
所以，若k≥2，Pk=（xk,yk），有
下面，我们可以由P7推出P1：
P7=（14，92）
P6=（28，184）
P5=（56，368）
P4=（112，316）
P3=（224，212）
P2=（448，4）
P1=（336，8）.
∴k+m=336+8=344.
例7已知定义在非负整数集上的函数f（n）由下列条件确定：
f（0）=0,f
（1）=0,f（2n）=2f（n）+1（n>0）及f（2n+1）=f（2n）－1,求最小正整数m，使f（m）=21990+1.
【说明】本题的函数由递推关系给出，由递推关系求出函数表达式往往不是一件容易的事，通常情况下，求自变量为某一值时的函数值，只要按递推关系式计算而不必求出函数关系，可现在的问题是已知函数值，要求自变量的最小正整数值，问题就显得难了，复杂了，在此我们可直接借助于递推关系而避开求函数表达式的麻烦.
【解】因为f（2n）=2f（n）+1,
f（2n+1）=f（2n）－1=（2f（n）+1）－1=2f（n）
所以偶数的函数值为奇数，奇数的函数值为偶数.
因为21990+1是奇数，而f（m）=21990+1，
所以m为偶数，可设m=2n1，则
f（m）=f（2n1）=2f（n1）+1=21990+1，
得f（n1）=21989,从而可知n1是奇数，可设n1=2n2+1,则f（n1）=2f（n2）=21989,
f（n2）=21989,从而可知n2是奇数，可设n2=2n3+1,……，可得关系式
m=2n1,f（n1）=21989,
n1=2n2+1,f（n2）=21989,
……
nk=2nk+1,f（nk+1）=21989－4,
……
n1988=2n1998+1,f（n1989）=2.
因为f（0）=1,f
（1）=0,
f（2n）=2f（n）+1,f（2n+1）=f（2n）－1,n>0.
所以当n=1时，
f（2×1）=2f
（1）+1=1,
f（2×1+1）=f（2×1）－1=1－1=0.
当n=2时，
f（2×2）=2f
（2）+1=2×1+1=3,
f（2×2+1）=f（5）=f（4）－1=3－1=2.
因为满足f（n1989）=2的最小正整数是
n1989=2×2+1=5△3·2－1，
递推而上可知
n1988=2n1989+1=2×5+1=11△3·22－1，
n1987=2n1988+1=2×11+1=23△3·22－1
即满足f（n1988）=22的最小正整数是
n1988=3×22－1，
……
满足f（nk+1）=21989－k的最小正整数是
nk=3·21989－k－1
……
满足f（n1）=21989的最小正整数是
n1=3·21989－1.
所以，满足f（m）=21990+1的最小正整数是
m=2n1=3·21990－2.
例8从{1，2，…n}中选出k项的严格递增数列，每相邻两项的差≤m,m（k－1）【解】设第一个数为x1+1，
第二个数为（x1+1）+（x2+1），
……
第i个数为（x1+1）+…+（xi+1）,
……
第k个数为（x1+1）+…+（xk+1）
其中0≤xi≤m－1（2≤i≤k）①
设x2+x3+…+xk=r②
则（x1+1）+…+（xk+1）≤n，
得0≤x1≤n－k－r,
所以x1可取n－k－r+1个值.
把（1+x+…+xn－1）k－1展开，则xr的系数ar就是方程②的，满足条件①的整数解（x2,x3,…，xk）的个数，即
（1+x+…+xm－1）k－1=
③
所求的选法共有
ar（n－k－r+1）种.
因为
ar（n－k－r+1）=（n－k+1）
ar－
rar④
所以只要求出
ar与
rar即可.在③中令x=1可得
ar=mk－1⑤
在③中令x=1+y，则③的右边成为
ar（1+y）r=
ar（1+ry+a
y2+…），⑥
由
rar就是上式中y的系数.
别外，③的左边成为
⑦
比较⑥、⑦可得
⑧
由④、⑤、⑧可得本题答案
例9设n>1，两个自然数的集合
{a1,a2,…,an}≠{b1,b2,…,bn},
而集
{ai+aj|1≤i≤j≤n}={bi+bj|1≤i≤j≤n}①
这里的相等计数及元素的重数，即如果元素S在①的左边出k次（用k种方法表示成ai+aj的形式），那么S也在①的右边出现k次，证明存在自然数h，使n=2h.
【解】考虑母函数
（注意，这里的ai与bi不是母函数的系数，而是指数）
②
同样
③
②、③中系数表示和
出现的次数，由题设知
即
④
由于f
（1）－g
（1）=n－n=0,所以（x－1）|（f（x）－g（x））,从而存在自然数h1,使
⑤
因此
⑥
即
令
.
由于n>1，所以h1>1,h1－1为某一自然数，从而有n=2h.
例10设A1，A2，A3是集合{1，2，…，n}的具有如下性质的分划：
（1）若将每个子集的元素按递增顺序排列，则每两个相邻元素的奇偶性不同；
（2）A1，A2和A3中恰有一个最小元素是偶数.
试求这种分划的个数.
提示集合的分划是由一族集合A1，A2，A3确定的，它们满足：
A1∪A2∪A3={1，2，…，n}，
A1∩A2=A2∩A3=A3∩A1=φ.
集合的另一排列，如A2，A3，A1和A1，A2，A3是同一划分.
（第28届IMO预选题，1987年）
【解】显然，题目中的条件
（1）和
（2）等价于对每个分划集决定可能放入该集的下一个数的奇偶性，而且，如果是还没有放进元素的，则由
（2）可知放进它的第一个数必是与A中的最小数有不相同的奇偶性；而对非空子集，下一个数的奇偶性由
（1）决定.
不失一般性.假设1∈A1，而A2的最小元素小于A3的最小元素，于是2有两种放法：
或放入A1，或放入A2.更进一步地，一旦k－1被放入A2后，则k就有两种可能的放法：
或放入A2，或放入A3.假设在某一步，k－1可放入Ai1或Ai2，不仿放入Ai3（i1,i2,i3是集合{1，2，3}的一种排列）.因为k－1与k有不同的奇偶性，所以Ai3成为可放入的，而Ai2却不能放入，而且k放入Ai1也是可能的。
如此继续下一步及有两种可能放法.以上给出了归纳推理的步骤.
综上，除1以处，每个数k均有两种放法。
所以分划的个数为2n－1.
例11试确定具有下述性质的最小正整数A：
把从1001至2000的所有正整数任作一个排列，都可以其中找出连续的10项，使这10项之和大于或等于A.
（中国台北第1届数学奥林匹克试题）
【解】设b1,b2,…b1000是1001,1002, …,2000的任一个排列.
则
下面，把1001至2000这1000个自然数排成10行，每行100个数，奇数列从左到右，偶数行从右到左排可得下表：
100110021003…10991100
120011991198…11021101
120112021203…12991300
……
180118021803…18991900
200019991998…19021901
从左到右按列的顺序，每一列又从上到下记上述数为a1,a2，…，a1000。
令Si=ai+ai+1+…+ai+9,（i=1,2,…，991），则S1=15005，S2=15006,而且容易证明，当i为奇数时,Si=15005，当i为偶数时，Si=15006.
所以可得A=15005.
例12（如图I—3—3—4）将边长为正整数m、n
的矩形划分成若干个边长均为正整数的正方形，每个正方
形的边长平行于矩形的相应边.试求这些正方形边长之和的最小值.
（2001年全国高中联赛二试试题3）
【解法1】记所求最小值为f（m,n）可以证明
f（m,n）=m+n－（m,n）.
其中（m,n）表示m和n的最大公约数.
事实上，不妨设m≥n.
（1）关于m归纳，可以证明存在一种合乎题意的分法，使所得正方形边长之和恰为
m+n－（m,n）
当m=1时命题显然成立.
假设当m≤k时，结论成立（k≥1）.当m=k+1时，若n=k+1，则命题成立，若n由归纳假设矩形A1BCD1有一种方法使得所得正方形边
长之和恰为m－n+n－（m－n,n）=m－（m,n）.
于是原正方形ABCD有一种分法使得所得正方
形边长之和为m+n－（m,n）.
（2）关于m归纳可以证明（*）成立.
当m=1时，由于n=1，显然f（m,n）=1=m+n－（m,n）.
假设当m≤k时，对任意1≤n≤m有f（m,n）=m+n－（m,n）.
若m=k+1，当n=k+1时显然f（m,n）=k+1=m+n－（m,n）.
当1≤n≤k时，设矩形ABCD按要求分成了P个正方形，其边长分别为a1,a2,…,ap.
不妨设a1≥a2≥…≥ap.
显然a1=n,或a1若a1m+n－（m,n）.
若a1=n，则一个边长分别为m－n和n的矩形可按题目要求分成边长分别为a2,…,ap的正方形，归纳假设
a2+…+ap≥m－n+n－（m－n,n）=m－（m,n）
从而a1+a2+…+ap≥m+n－（m,n），
于是当m=k+1时，f（m,n）≥m+n－（m,n）.
再由
（1）可知f（m,n）=m+n－（m,n）.
【解法2】所求正方形边长之和
的最小值为m+n－d，的最大公约数，即d=（m,n）.下面给出证明，分两步：
第一步是证明：
≥m+n－d.对矩形的较大边长max{m,n}用数学归纳法，约定“平行于原矩形的某边的正方形边长之和”中包括该边本身.
（1）当max{m,n}=1时，结论显然成立.
（2）假设当max{m,n}①所有正方形的边长均小于n时，全体正方形的平行于AB的边长之和≥4m，而平行于BC的边长之和≥4n.故周长之和≥4（m+n）>4（m+n－d）,从而，
≥m+n－d.
②有一个正方形的边长等于n时，将正方形交换位置，使边长为n的正方形以AD为其一
升级会员 