资源简介

第十六讲 组合数字
二、抽屉原则、容斥原理
知识、方法、技能
I．抽屉原则
10个苹果放入9个抽屉中，无论怎么放，一定有一个抽屉里放了2个或更多个苹果.这个简单的事实就是抽屉原则.由德国数学家狄利克雷首先提出来的.因此，又称为狄利克雷原则.
将苹果换成信、鸽子或鞋，把抽屉换成信筒、鸽笼或鞋盒，这个原则又叫做信筒原则、鸽笼原则或鞋盒原则.抽屉原则是离散数学中的一个重要原则，把它推广到一般情形就得到下面几种形式：
原则一：把m个元素分成n类（m>n），不论怎么分，至少有一类中有两个元素.
原则二：把m个元素分成n类（m>n）
（1）当n|m时，至少有一类中含有至少个元素；
（2）当n|m时，至少有一类中含有至少[]+1个元素.
其中n m表示n是m的约数，n m表示n不是m的约数，[]表示不超过的最大整数.
原则三：把个元素分成n类，则存在一个k，使得第k类至少有个元素.
原则四：把无穷多个元素分成有限类，则至少有一类包含无穷多个元素.
以上这些命题用反证法极易得到证明，这里从略.
一般来说，适合应用抽屉原则解决的数学问题具有如下特征：新给的元素具有任意性.如10个苹果放入9个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着. 问题的结论是存在性命题，题目中常含有“至少有……”、“一定有……”、“不少于……”、“存在……”、“必然有……”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果.
对一个具体的可以应用抽屉原则解决的数学问题还应搞清三个问题：
（1）什么是“苹果”？
（2）什么是“抽屉”？
（3）苹果、抽屉各多少？
用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确.
用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律.
用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律.
用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”.
Ⅱ. 容斥原则
当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明智的选择.将整体分解为部分也就是将有限集X表示成它的一组两两互异的非空真子集A1，A2，…An的并集，即叫做集合X的一个覆盖.一个特殊情况是，集族中的任意两个集合都不相交，这时我们称集族为集合X的一个（完全）划分.如为集合X的划分，则对集合X的计数可通过熟知的加法公式
①
进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事. 我们可以考虑通过对任意的集族中的子集的计数来计算|X|，当集族中至少存在两个集合的交非空时，我们称这个覆盖为集合X的不完全划分. 对于集合X的不完全划分，显然有有
②
因为在计算|Ai|时出现了对某些元素的重复计数，为了计算|X|，就得将②式右边重复计算的部分减去，如果减得超出了，还得再加上，也就是说我们要做“多退少补”的工作.完成这项工作的准则就是容斥原理. 是十九世纪英国数学家西尔维斯提出的. 容斥原理有两个公式.
1．容斥公式
定理1 设
③
证明：当由加法公式有

结论成立.
若n=k时结论成立，则由

知，
时结论成立.
由归纳原理知，对任意自然数n，公式③成立.
公式③称为容斥公式，显然它是公式①的推广.
如果将看成具有性质的元素的集合，那么就是至少具有n个性质之一的元素的集合. 因此，容斥公式常用来计算至少具有某几个性质之一的元素的数目.
2．筛法公式
与容斥公式讨论的计数问题相反，有时需要计算不具有某几个性质中的任何一个性质的元素的个数，即. 为此，我们先引入下面的引理.
引理1 设A关于全集I的补集为，则
引理2
引理简单证略. 利用二引理改写公式③便是
定理2 设为有限集I的子集，则
④
赛题精讲
例1设ABC为一等边三角形，E是三边上点的全体. 对于每一个把E分成两个不相交子集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点？（第24届IMO第4题）
【证明】如图I—3—2—1，在边BC、CA、AB上分别取三点
P、Q、R，使显然
△ARQ，△BPR，△CQP都是直角三角形. 它们的锐
角是30°及60°.
设E1，E2是E的两个非空子集，且
由抽屉原则P、Q、R中
至少有两点属于同一子集，不妨设P、Q∈E1. 如果BC边上除P之外还有属于E1的点，那么结论已明.
设BC的点除P之外全属于E2，那么只要AB上有异于B的点S属于E2，设S在BC上的投影点为Ｓ′，则△SS′B为直角三角形.
再设AB内的每一点均不属于E2，即除B之外全属于E1，特别，R、A∈E1，于是A、Q、R∈E1，且AQR为一直角三角形. 从而命题得证.
【评述】此例通过分割图形构造抽屉. 在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个或几个抽屉进行讨论，使问题得到解决.
例2：在1，4，7，10，13，…，100中任选出20个数，其中至少有不同的两组数，其和都等于104，试证明之. （第39届美国普特南数学竞赛题）
【证明】给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个不相交的集合.
{1}，{52}，{4，100}，{7，97}，…{49，55}.
且把它们分作是18个抽屉，从已知的34个数中任取20个数，即把前面两个抽屉中的数1和52都取出，则剩下的18个数在后面的16个抽屉中至少有不同的两个抽屉中的数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是104.
【评述】此例是根据某两个数的和为104来构造抽屉. 一般地，与整数集有关的存在性问题也可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而构成抽屉.

第十四讲 组合数学
一、集合与映射
知识、方法、技能
这一讲主要介绍有限集的阶，有限集上的映射及其性质，这些在与计数有关的数学竞赛问题中应用极广，是参赛者必不可少的知识
Ⅰ.有限集元素的数目
1．有限集的阶
有限集A的元素数目叫做这个集合的阶，记作|A|[或n(A)].
2．集族的阶
若M为由一些给定的集合构成的集合，则称集合M为集族.
设A为有限集，由A的若干个子集构成的集合称为集合A的一个子集族，求满足一定条件的集族的阶是一类常见的问题.
显然，若|A|=n，则由A的所有子集构成的子集族的阶为2n.
Ⅱ.映射，映射法
定义1 设X和Y是两个集合（二者可以相同）.如果对于每个，都有惟一确定的与之对应，则称这个对应关系为X到Y的映射.记为这时,称为的象,而x称为y的原象,特别当X和Y都是数集时，映射f称为函数.
定义2 设f为从X到Y的一个映射.
(1)如果对于任何x1、
（2）如果对于任何，都有，使得f(x)=y，则称f为满射;
（3）如果映射f既为单射又为满射，则称f为双射；
（4）如果f为满射且对任何，恰有X中的m个元素x1、x2、…xm，使得
定理1 设X和Y都是有限集，f为从X到Y的一个映射,
（1）如果f为单射，则|X|≤|Y|
（2）如果f为满射，则|X|≥|Y|
（3）如果f为双射，则|X|=|Y|
（4）如果f为倍数为m的倍数映射，则|X|=m|Y|.
这个定理的结果是显然的.
定理2 设有限集是A到A上的映射，
则f是一一映射（即双射）的充要条件是：对任意
证明：必要性.若f是双射，则（此时mi=1）,或者在后一种情形下，不可能有否则，ai1在A中有两个原象ai和ai1，与f是双射不合，而只可能有，则依同样的道理，不可能有
.如此等等.
因为A是有限集，所以经过有限次（设经过m次）后，有
这表明当f是双射时，对任一都存在着映射圈:
在这个映射圈中，诸元素互异，且
充分性.如果对任意
，这说明从A中任一元素ai出发，都可以得到一个包含mi个互异元素的映射圈，显然f是双射.
定理3 在命题1的条件下，若对，则对任意
这是明显的事实，证明从略.
赛题精讲
例1：设集合
.
【解】形如4k+1的数的数可分三类：
，其中只有形如12l+5的数是形如3k-1的数.
例2：有1987个集合，每个集合有45个元素，任意两个集合的并集有89个元素，问此1987个集合的并集有多少个元素.
【解】显然，可以由题设找到这样的1987个集合，它们都含有一个公共元素a，而且每两个集合不含a以外的公共元素.但是，是否仅这一种可能性呢？
由任意两个集合的并集有89个元素可知，1987个集合中的任意两个集合有且仅有一个公共元素，则容易证明这1987个集合中必有一个集合中的元素a出现在A以外的45个集合中，设为A1，A2，…，A45，其余的设为A46，A47，…，A1996.
设B为A46，…，A1996中的任一个集合，且，由题设B和A，A1，A2，…，A45都有一个公共元素，且此46个元素各不相同，故B中有46个元素，与题设矛盾，所以这1987个集合中均含有a.
故所求结果为1987×44+1=87429.即这1987个集合的并集有87429个元素.
例3：集合为A的非空子集族，并且当
求n的最大值.
【解】首先考虑至多含三个元素的A的非空子集族，它们共有个，这说明
下证，事实上，设D为满足题设的子集族，若
则B与B-{b}不能同时含于D，以B-{b}代B，则D中元素数目不变.仿此对D中所有元素数目多于4的集合B作相应替代后，集族D中的每个集合都是元素数目不多于3的非空集合，故.
所以，
在许多问题中，计数对象的特征不明显或混乱复杂难以直接计数，这时可以通过适当的映射将问题划归为容易计数的对象，然后再解决，从而取得化难为易的效果.
例4：设A为至少含有两项的公差为正的等差数列，其项都在S中且当将S的其他元素置于A中之后，均不能构成与A有相同公差的等差数列.求这种A的个数（只有两项的数列也视为等差数列）
【解】当为偶数时，满足题中要求的每个数列A中必有连续两项，使其前一项在集{1,2,…,k}和{k+1,k+2,…,2k}中各任取一数，并以二数之差作为公差可以作出一个满足要求的数列A.容易看出，这个对应是双射.故知A的个数为
当n=2k+1为奇数时，情况完全类似.惟一的不同在于这时第二个集合
有k+1个元素.故A的个数为

第十九讲
三、组合计数
知识、方法、技能
组合计数就是计算集合的元素个数。它是组合数学的重要组成部分.
在具体问题中给出的集合各式各样，都具有实际意义，而且集体中的元素是由某些条件所确定的，要判定一个元素是否属于某集合A，已非易事，要确定A的元素个数就更难了.这正是研究计算问题的原因。
解决组合计算问题虽然不需要高深理论知识，却需要重要的计算原理与思想方法.
Ⅰ．几种特殊的排列、组合
1．圆排列
定义1：从几个元素中任取r个不同元素仅按元素之间的相对位置而不分首尾排成一个圆圈，这种排列称为n个不同元素的r——圆排列。r——圆排列数记为.
定理1：
证：对n个不同元素取r个的任一圆排列，均有r种不同的方式展开成r个不同的直线排列，且不同的圆排列展开的直线排列也彼此不同，故有r·=Prn，得正.
2．重复排列
定义2：从n个不同元素中允许重复的任取r个元素排成一列，称为n个不同元素的r——可重复排列.
定理2：n个不同元素的r——可重排列数为nr.
证：在按顺序选取的r个元素中，每个元素都有n种不同的选法，故由乘法原理有，其排列数为nr.
3．不全相异元素的全排列
定义3：设n个元素可分为k组，每一组中的元素是相同的，不同组间的元素是不同的，其中第i组的元素个数为ni(i=1, 2, …, k ), n1+n2+…+nk=n . 则这n个元素的全排列称为不全相异元素的全排列.
定理3：n个元素的不全相异元素的全排列个数为
证：先把每组中的元素看做是不相同的，则n个不同元素的全排列数为n!，然后分别将每个组的元素还其本来面目看成是相同的，则在这n!个全排列中，每个排列都重复出现了n1！n2!……nk！次，所以不全相异元素的全排列数
4．多组组合
定义4：将n个不同的元素分成k组的组合称为n个不同元素的k——组合.
定理4：对于一个n个不同元素的k——组合，若第i组有ni个元素（i=1, 2, …，k），则不同的分组方法数为
证：我们把分组的过程安排成相继的k个步骤.第一步，从n个不同元素中选n1个，有种方法；第二步，从n－n1个元素中选n2个有种方法；…；第k步，从n－（n1+n2+…+nk－1）个元素中选nk个元素，有－（n1+n2+…+nk－1）种方法，再由乘法原理得证.
5．重重组合
定义5：从n个不同元素中任取r个允许元素重复出现的组合称为n个不同元素的r——可重组合.
定理5：n个不同元素的r——可重组合的个数为Crn+r－1 .
证：设（a1 , a2 ,…，ar）是取自{1，2，…，n}中的任一r可重复组合，并设a1≤a2≤…≤ar .令 bi=ai+i－1(1≤i≤r).
从而b1=a1 , b2=a2+1 , b3=a3+2,…, br=a+r－1r .
显然下面两组数是一对一的：a1≤a2≤a3≤…≤ar ,
1≤a1设 A={（a1 , a2 ,…，ar）|ai∈{1，2，…，n}，a1≤a2≤…≤ar }，
B={（b1, b2,…，br）|bi∈{1，2，…，n+r－1}，b1< b2<…则由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 +a2 x2+…+ 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”
精讲
例1 数1447，1005和1231有某些共同点，即每个数都是首位为1的四位数，且每个四位数中恰有两个数字相同，这样的四位数共有多少个？
（第1届AIME试题，1983年）
【解】符合条件的四位数必含有一个1或者两个1.
（1）含有两个1的情形
从除1之外的其余9个数字中任取两个，有C29种取法，再与其中的一个1组成任意排列的三位数，有P33种，这样构成的首位为1的四位数共有N1= C29 P33（个）.
（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的情况下可分为如下两类：
ZZZ Z Z Z，①
ZZ ZZ Z Z.　②
以及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+560 yk<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=(2 xk , 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=2 n1989+1=2×5+1=11△ 3·22－1，
n1987=2 n1988+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.

第二十一讲 组合计数“续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+ay2+…）， ⑥
由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或A i2，不仿放入Ai3（i1, i2 , i3 是集合{1，2，3}的一种排列）.因为k－1与k有不同的奇偶性，所以Ai3成为可放入的，而A i2却不能放入，而且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个数，奇数列从左到右，偶数行从右到左排可得下表：
1001 1002 1003 … 1099 1100
1200 1199 1198 … 1102 1101
1201 1202 1203 … 1299 1300
……
1801 1802 1803 … 1899 1900
2000 1999 1998 … 1902 1901
从左到右按列的顺序，每一列又从上到下记上述数为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为其一边，则全体正方形的边长之和不变.
当m=n时，只此一个正方形，边长为n；
当m>n时，矩形ABCD中的其余部分是一个边长分别为n和m－n的矩形，其较大边长max{n, m － n }这就证明了当max{m , n }=k 时结论亦成立.
故对任何边长为正整数的矩形，其边长为正整数的正方形分割满足≥m+n－d.
第二步，构造出原矩形的满足=m+n－d的边长为正整数的正方形分割.如图I—3—3—6.
设m=q1n+r1,
n=q2r1+r2,
r1=q3r2+r3,
……
rk－2=qk rk－1+d,
rk－1= qk+1d,其中q1, q2 ，……，qk+1为非负整数，r1,
r2,…, rk－1为正整数，n>r1>r2>…>rk－1>d，从AD边开始，依次排列q1个边长为n的正方形，剩下边长为n和r1的矩形A1BCD1.再从新矩形的边D1C开始，夜次排列q2个边长为r1的正方形，剩下边长为r1和r2的矩形A1BC1D2.再从新矩形的边A1D2开始，依次排列q3个边长为r2的正方形，……，如此继续，第k步剩下边长为rk－1和d的矩形，将其分割为qk+1个边长为d的正方形，结束操作，全体正方形的边长之和为
=q1n+q2r1+q3r2+…qk rk－1+ qk+1d.
=(m －r1)+(n－r2)+(r1－r3)+…+(rk－2－d)+ rk－1
=m+n－d .
即矩形ABCD确有满足=m + n －d的边长为整数的正方形分割.

展开更多......

收起↑