高一数学竞赛讲义第1~7讲

高一数学竞赛讲义

目录

1.第一讲组合计数（1）.......................................................2

1.1.本讲概述................................................................2

1.1.1,加法原理与乘法原理.................................................3

1.1.2.无重排列与组合.....................................................3

1.1.3.可重排列与组合（仅给出结论，请自证之）...........................3

1.1.4.圆排列（仅给出结论，请自证之）....................................4

1.2,例题精讲.................................................................4

1.2.1.板块一利用加法、乘法原理以及枚举方法计数.........................4

1.2.2.板块二映射与对应方法..............................................9

2.第二讲组合计数（2）........................................................15

2.1.本讲概述................................................................15

2.2.例题精讲..............................................................15

2.2.1.板块一算两次....................................................15

2.2.2.板块二递推方法................................................18

2.2.3.板块三组合计数综合问题...........................................19

3.第三讲二项式定理与组合恒等式..............................................25

3.1.本讲概述..............................................................25

3.2.例题精讲..............................................................26

4.第四讲抽屉原理与存在性问题................................................34

4.1.本讲概述...............................................................34

4.2.例题精讲..............................................................35

5.第五讲容斥原理与极端性原理................................................45

5.1.本讲概述..............................................................45

5.2.例题精讲..............................................................46

5.2.1.板块一容斥原理..................................................46

5.2.2.板块二极端性原理...............................................50

6.第六讲染色问题与操作问题..................................................55

6.1.本讲概述...............................................................55

6.2.例题精讲..............................................................55

6.2.1.板块一染色问题..................................................55

6.2.2.板块二操作问题................................................59

第1页共82页

7.第七讲组合综合问题.........................................................64

7.1.本讲概述................................................................64

7.2.例题精讲................................................................64

1.第一讲组合计数（1）

1.1.本讲概述

组合数学是竞赛中最重要的一个板块，也是变化最多，最灵活，难以掌握,

至今还没有一个系统体系的学科.解决竞赛中的组合数学问题，往往不需要太多

专门的知识，而是要求深刻的洞察能力和强大的化归、转化能力.所谓”得组合

者得天下”，在联赛一二试乃至冬令营、集训队、IMO中，最后的胜者往往是

成功完成组合问题的同学.因此，学习组合数学对于竞赛获奖以及数学能力的培

养都有着十分重要的意义.

从本讲开始，我们将用七讲来对组合数学做一个大致的勾勒.通过这七讲的

学习，达到以下目的：1、掌握联赛一二试组合问题的特点与解法；2、对组合

数学这门学科有一个初步的认识，为进一步学习打下基础；3、了解部分冬令营

级别组合问题的难度与解题模式.

七讲内容分别为：

一、组合计数（1）比高考略难的基本计数问题

二、组合计数（2）需要较多技巧的专门计数问题

三、组合恒等式较为重要和有趣味的组合恒等式

四、抽屉原理与存在性问题

五、容斥原理与极端性原理

六、染色问题与操作问题

七、组合数学综合问题

本讲中，假定各位同学已经大致学完了高考难度的排列组合模块内容，对加

法原理、乘法原理等有一定的理解并能完成相关的问题.

教师备注：本讲可与下一讲打通讲述，也可本讲专门讲常规的枚举、基本的

组合问题，下一讲专门讲述一些较为高级的技巧.

首先给出一些相关的基本知识：

第2页共82页

1.1.1.加法原理与乘法原理

加法原理：完成一件事的方法可分成n个互不相交的类，在第1类到第n

类分别有叫,，々，…,"J种方法，则总共完成这件事有=町+m2+...+mn种

/=I

方法.

应用加法原理的关键在于通过适当的分类，使得每一类都相对易于计数.

乘法原理：完成一件事的方法有n个步骤，，在第1步到第n步分别有

班,网,...,加“种方法，则总共完成这件事有jɪ叫=，"]•机种方法•应用乘法

/=I

原理的关键在于通过适当的分步，使得每一步都相对易于计数.

由上可见，加法原理与乘法原理也是化归思想的应用，通过这两个原理以及

它们的组合，可以将一个复杂的组合计数问题分解成若干个便于计数的小问题.

1.1.2.无重排列与组合

阶乘:定义n!=n∙(n-l)∙(n-2)∙...∙2∙l,读作n的阶乘

无重排列：从n个不同元素中任取m个不同元素排成一列，不同的排列种

数称为排列数，记为(部分书中记为尸"),由乘法原理得到

M=---------=〃・(〃-D〃一机+1)

(n-fn)!

无重组合：从n个不同元素中任取m个元素并为一组，不同的组合种数称

为组合数，记为C其公式为

CY="PT”…∙("f+D=―d_

“mlm∖(n-ni)∖∙m∖

1.1.3.可重排列与组合(仅给出结论，请自证之)

可重排列：从n个不同元素中可重复地任取m个元素排成一列，不同的排

列种数有那种；

有限个重复元素的全排列：设n个元素由k个不同元素%,电,...,如组成，分

别有n1,%,…,々个(勺+%+…+%=〃)，那么这n个元素的全排列数为

n∖

HI!∙n1!•・・・•久!

第3页共82页

可重组合：从n个不同元素中，任意可重复地选取m个元素，称为n个不

同元素中取m个元素的可重组合，其种数为C'T

1.1.4.圆排列（仅给出结论，请自证之）

在"个不同元素中,每次取出m个元素排在一个圆环上，叫做一个圆排列（或

叫环状排列）.圆排列有三个特点：（i）无头无尾；（ii）按照同一方向转换

后仍是同一排列；（iii）两个圆排列只有在元素不同或者元素虽然相同，但元

素之间的顺序不同，才是不同的圆排列.

在A=1%,%,%，…，4｝的"个元素中，每次取出m个不同的元素进行圆排

Allt

列，圆排列数为A.

m

1.2.例题精讲

1.2.1.板块一利用加法、乘法原理以及枚举方法计数

联赛一试的填空题中出现的计数问题有接近一半的问题不需要用到很高深

的技巧，而是直接利用最基本的加法、乘法原理，以及枚举方法来计数.这主要

是考虑到有一部分参加联赛的同学并未经过专业的竞赛训练.虽然如此，这部分

计数问题枚举起来往往分类复杂，需要小心仔细.

从往年的联赛试题来看，枚举法解决计数问题是最主要的题型之一，其难点

在于做到''不重不漏”，这是加法原理的一个简单的应用•枚举过程中，采用恰

当的分类、分步形式，往往会收到化难为易的效果.

【例1】（高考难度的热身问题）

（1）等腰三角形的三边均为正整数.它们周长不大于10.这样不同的三角

形的种数为

A.8B.9C.IOD.11

（2）有两排座位，前排11个座位，后排12个座位，现安排2人就座,

规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种

数是

第4页共82页

A.234B.346C.350D.363

【解析】(1)设三边为x,y,z,则x+y+z≤10,由三边关系共有(1,1,1),(1,2,

2),(1,3,3),(1,4,4),(2,2,2),(2,2,3),(2,3,3),(2,4,4),(3,3,3),[3,

3,4)共10种.

(2)B前排中间的3个座位不能坐，有排法A，。，其中相邻的分三类，在前排的其中的4个座位有

3封；则符合条件的排法种数中A务-3度-3A"11度=346,故选B(这是正难则反的思想，

从总体中除去不符合要求的)

另解：分三类：①两人坐在前排，按要求有4•6+4•5=44种坐法.

②两人坐在后排，按要求有：A：="。种坐法.

③两人分别坐在前后排，有8×12×2=I92种

二共有346种排法.

【例2】(1)有多少个能被3整除而又含有数字6的五位数？

(2)集合｛1,2,...,100｝的子集中共有多少个至少包含一个奇数？

【解析】(1)按照上题正难则反的思想，可以先找出所有的五位数，共有90000

个，其中可被3整除的有30000个，下面研究这30000个数中不含数

字6的数，最高位有8种选择，千、百、十位各有9种选择，个位数除

不能为6外，还应满足恰各位数之和可被3整除，这恰有3种选择，例

如当前四位除以3余2时，个位应为1,4,7之一；故能被3整除且不含

数字6的有8χ9χ9χ9χ3=17496个，故所求五位数有

30000-17496=12504个

(2)显然全部子集数为2ωo个，不包含任何奇数的子集即

｛2,4,6,...,98,100)的子集共有25°个，故所求子集个数为2⑼-250个.(思

考：请用最简洁的方法确定为何n元集合子集数为2"个)

【例3】设ABCDEF为正六边形，一只青蛙开始在顶点4处，它每次可随意地跳

到相邻两顶点之一.若在5次之内跳到。点，则停止跳动；若5次之内

不能到达。点，则跳完5次也停止跳动，那么这只青蛙从开始到停止，

可能出现的不同跳法共种

【解析】这是标准的联赛风格的枚举问题，所谓杀鸡焉用牛刀，用递归方法来解

这类问题就太麻烦了.

第5页共82页

显然青蛙不能跳1,2,4次到达D点，于是青蛙的跳法只有以下两种：

（1）青蛙跳3次后到达D点，有2种跳法；

（2）青蛙跳5次后停止，跳3次有23-2种，后两次有22种，共计24

种；

所以，合计有26种跳法

注本题为1997年联赛试题

【例4】从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染

色，每面恰染一种颜色，每两个具有公共棱的面染成不同的颜色。则不

同的染色方法共有种。（注：如果我们对两个相同的正方体

染色后，可以通过适当的翻转，使得两个正方体的上、下、左、右、前、

后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案

相同。）

【解析】因为有公共顶点的三个面互不同色，故至少要用3种颜色，下面分四种

情形来考虑.

（1）6种颜色都用时，现将染某种固定颜色的面朝上，从剩下5种颜色中

取一种颜色染下底面有种方法，余下4种颜色染四个侧面（应是4种颜色的

圆排列）有3!种方法.所以不同的染色方案有3!=30种.

（2）只用5种颜色时，从6种颜色中取5种颜色有种方法，这时必有

一组对面同色.从5种颜色中取一种颜色染一组对面,并将它们朝上和朝下,有C；

种方法，其余4种颜色染四个侧面（应是4种不同颜色的链排列）有Lχ3!种

2

方法.所以不同的染色方案有C；∙C][∙3!=90种.

（3）只用4种颜色时，从6种颜色中取4种颜色有C：种方法，这时必有

两组对面同色，另一组对面不同色，将不同色的一组对面朝上和朝下，并从4

种颜色中取两种颜色染上、下底面，有种方法，其余两种颜色染四个侧面且

使两组对面同色（应是两种不同颜色的链排列），只有1种方法.所以不同的染

色方案有C：∙C>1=9O种.

第6页共82页

(4)只用3种颜色时，从6种颜色中取3种颜色有C；种方法，这时三组

对面都同色，用三种颜色去染它们只有1种方法.所以不同的染色方案有

C>1=20种.

综上可知，不同的染色方案共有30+90+90+20=230种.

注本题为1996年联赛试题，是历年来一试计数问题中最复杂的一道，其背景

与波利亚群论计数原理有关，这远远超出了高中范围，此处略去

【例5】将24个志愿者名额分配给3个学校，则每校至少有一个名额且各校名

额互不相同的分配方法共有222种.

【解析】用4条棍子间的空隙代表3个学校，而用*表示名额.如

I****I**∣**∣

表示第一、二、三个学校分别有4,18,2个名额.

若把每个“*"与每个"|”都视为一个位置，由于左右两端必须是“I”，故不同

的分配方法相当于24+2=26个位置(两端不在内)被2个“I”占领的一种"占位

法

"每校至少有一个名额的分法"相当于在24个"*”之间的23个空隙中选出2

个空隙插入"I",故有C⅛=253种.

又在"每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分

配方法有31种.

综上知，满足条件的分配方法共有253—31=222种.

［解法二］设分配给3个学校的名额数分别为由,x2,鼻，则每校至少有一个名额的

分法数为不定方程

xl+x2+X3=24.

的正整数解的个数，即方程%+々+退=21的非负整数解的个数，它等于3个不

同元素中取21个元素的可重组合：

H；=《；=《=253.

又在“每校至少有一个名额的分法”中“至少有两个学校的名额数相同”的分

配方法有31种.

综上知，满足条件的分配方法共有253—31=222种

第7页共82页

注本题为2008年联赛试题，从近年来联赛一试组合问题来看，组合计数问题

难度明显降低了.本题所应用的插空法是一种在高考和竞赛中常用的计数方法

【例6】将2个α和2个b共4个字母填在4x4方格表内，每个小方格内至多填

1个字母，若使相同字母既不同行也不同列，则不同的填法共有

种（用数字作答）。

【解析】使2个α既不同行也不同列的填法有GM42=72种，同样，使2个b既

不同行也不同列的填法也有C4242=72种，故由乘法原理，这样的填法

共有722种，其中不符合要求的有两种情况：2个α所在的方格内都填

有b的情况有72种；2个α所在的方格内仅有1个方格内填有b的情

况有Ci6M92=16χ72种。所以，符合题设条件的填法共有

722-72-16×72=3960种。

注本题为2007年联赛第12题

【例7】设三位数〃=诙，若以a,b,c为三条边的长可以构成一个等腰（含等

边）三角形，则这样的三位数n有（）

A.45个B.81个C165个D.216个

【解析】本题是标准的枚举问题，情况繁多.

a,b,c要能构成三角形的边长，显然均不为0。即α,b,c∈{l,2,...,9}

（1）若构成等边三角形，设这样的三位数的个数为〃「由于三位数中三个数码

都相同，所以，々=C；=9。

（2）若构成等腰（非等边）三角形，设这样的三位数的个数为〃2,由于三位数

中只有2个不同数码。设为a、b,注意到三角形腰与底可以置换，所以可取的

数码组（a,b）共有2C；。但当大数为底时，设a>b,必须满足A<α<乃。此

时，不能构成三角形的数码是

a987654321

4,34,33,23,2

b1,21,211

2,12,111

共20种情况。

第8页共82页

同时，每个数码组（a,b）中的二个数码填上三个数位，有C；种情况。

故4=C；（2C；-20）=6（C；-IO）=I56。综上，n=nl+n2=∖65o

注本题为2004年联赛试题

1.2.2.板块二映射与对应方法

由一一映射的定义可知，若存在从集合M到N的一一映射，则IMl=IM.于是

在难以直接计算集合M中元素个数时，我们可以设法构造这样一个映射，将问

题转化为计算较为容易计算的集合N的元素个数.基于这种两集合元素一一对应

的特点，也称为“配对法”

【例8】（1）试用对应方法证明可重组合公式：从n个不同元素中，任意可重

复地选取m个元素，称为n个不同元素中取m个元素的可重组合，其

种数为C2τ

（2）证明：不定方程占+当+…+4="（k,n为正整数）的非负整数解

组数为

【解析】（1）设n个元素为1,2,并设取出的m个元素为

l

∖≤ax≤a2≤...≤am≤n,^J⅛l<<2l+0<α2+l<...<am+m-∖≤n+m-∖,

作对应

（01,a2,...,am）÷÷（αl+0,a2+l,...,am+m-↑）,易证明它为---

对应

后者为从〃+〃2-1个元素中取m个元素的组合数a，-,故得证

（2）将n个圆圈与k-l个竖线排成一排，k-1个竖线将n个圆圈依次

分成k个部分：x,,x2,...,xk,易见不同的排列对应不定方程不同的解，易证它为

一个一一对应，而在n+k-1个元素中取出k-l个的全排列数为,故得证.

【例9】凸n边形的任意3条对角线不相交于形内一点，求其对角线在形内的交

点总个数.

第9页共82页

【解析】任一形内交点对应两条对角线Lm;反之，任意两条对角线唯一确定形内

一个交点P,从而P与(ɪ,m)构成一一对应；又任一对角线对应形内2

顶点，n边形中任取4顶点即可唯一确定两对角线，于是有如下一一对

应：点P<→(/,加)—(A,B,CO)

于是交点总个数=四顶点组个数=C：

注本题为组合数学一个重要分支一一组合几何中的非常重要的一个结论，可以

利用它解决一些高难度的组合几何计数问题

【例10】将集合A中的n个元素排成一行，若某个子集中任意两元素不相邻，则

称此子集为不好的，试证明：k元的不好的子集个数为c3.∣

【解析】设n个元素排成一行依次为为1,2,并设取出的k个元素为

1≤Z1<Z2<...<4≤n,

显然有2≤

作变换l≤i∣<i2T<i3-2∙∙∙<%-(A-l)W"-k+l,并取序列：

(il,i2-l,i3-2,...,it-(k-l))r它是1,2,n-k+1中的一个严格上升的序列

作对应--

—(z1,∕2l,ʃɜ2,...,ZA.—(⅛—1)),

易证明它为一一对应，且后者的种数为从〃-Z+1个元素中取k个元素

的组合数CM…故得证

注本题为第16届普特南竞赛题

Q大显身手

1.(1)在100件产品中有6件次品，现从中任取3件产品，至少有1件

次品的不同取法的种数是

A.CgCg4B.C：C；9

C∙G'oo—C94D.AOO-A94

(2)从4名男生和3名女生中选出4人参加某个座谈会，若这4人中

必须既有男生又有女生，则不同的选法共有

第10页共82页

A.140种B.120种C35种D.34种

【解析】（1）C任取3件产品有Ca）种方法，其中无次品有C；4种方法，故至少有1件次品的

方法数为q%）-Cg4∙

（2）D既有女生又有男生，可以分类表示，三男一女有或•以种选法，二

男二女有盘或种，

一男三女有以•或种选法，则总的不同的选法有

c∣∙cj+c^∙cf+cj∙=34（种）

2.由三个数字1、2、3组成的5位数中，1、2、3都至少出现1次,

这样的5位数共有多少个？

【解析】在5位数中，若1只出现1次，有Ge+C：+C：）=70个；

若1只出现2次，有C；（C；+C；）=60个；

若1只出现3次，有=20个.则这样的五位数共有150个.故

填150个.

注本题为05年江苏省预赛试题

3.已知集合A=N5x-a<θ},B—{Λ∣6X-⅛>θ},a,b∈N,且

AnfinTV={2,3,4）-则整数对（。,劝的个数为

A.20B.25C.30D.42

【答】（）

Z7b_

【解析】由5x-a<0=x<-；6x-Z?>0=>x>—。要使ACBCN={2,3,4},

56

《<2

6≤b<∖2

则即《所以数对（α,乃共有Ce=30。

4个52Q≤a<25

注本题为2006年联赛试题

4.记集合T={O,1,2,3,4,5,6},M=[4+⅛→与+2q∈T,i=l,2,3,4,将M

77^TT

中的元素按从大到小顺序排列，则第2005个数是

第11页共82页

“5563c5562cli04n

a∙~+ψ+ψ+ψB.-+ψ+ψ+ψC.-+ψ+ψ+ψD.

1103

7+7τ+7y+7τ

【解析】用Ua2…41P表示k位P进制数，将集合M中的每个数乘以7，

得

r32

M={«,∙7+a2∙7+α3∙7+(a4Iɑʃ∈T,z=：1,2,3,4}={[αlα2π3π4]7∖ai≡T,i-1,2,3,4).

M'中的最大数为[6666b=[24001。。

在十进制数中，从2400起从大到小顺序排列的第2005个数是

2400-2004=396;

而[396Lo=U网7,将此数除以7t便得到M中的数：,*+*+*故

选Co

注本题为2005年联赛试题，题目形式提示我们，要采用进制转换.事实上，这

类题目在小学和初中是极为常见的.

5.已知两个实数集合A={αι,α2,…,Qioo}与8={历,历,…力5θ},若从A到B的映

射/使得B中每个元素都有原象，且

f[aι)≤∕(Q2]≤∙∙∙≤∕[0ιoo)

则这样的映射共有

网端(B)喘(C)瑞(D)噫

【解析】不妨设bι<b2<…<b50,将A中元素aι,a2,…，aιoo按顺序分为非空

的50组，定义映射f：A-B,使得第i组的元素在f之下的象都是bi

(i=l,2,…,50),易知这样的f满足题设要求，每个这样的分组都一一对应

满足条件的映射，于是满足题设要求的映射f的个数与A按足码顺序分

为50组的分法数相等，而A的分法数为则这样的映射共有C；；,

故选D。

注本题为2002年全国联赛试题

第12页共82页

6.在世界杯足球赛前，F国教练为了考察Ai,A2,…,A7这七名，准备让他们

在三场训练比赛(每场90分钟)都上场，假设在比赛的任何时刻，这些

中有且仅有一人在场上，并且Ai,A2,A3,A4每人上场的总时间(以分钟为

单位)均被13整除，如果每场换人次数不限，那么按每名队员上场的总

时间计算，共有多少种不同的情况。

【解析】设第i名队员上场的时间为Xi分钟(i=123,…,7),问题即求不定方程

Xl+X2+…+X7=270

①

在条件7∣Xi(IWiW4)且13∣Xj(5≤jW7)下的正整数解的级数。

若(XI,X2,…,X7)是满足条件①的一组正整数解，则应有

47

Z∙x,.=7mZXj=I3nm,n∈N

i=1j=5

.∙.m,n是不定方程

7m+13n=270

②

在条件m>4且n≥3下的一组正整数解。.......

10分

'/7(m-4)+13(n-3)=203

令m,=m-4n,=n-3有

7m'+13n,=270

③

求②满足条件mN4且n≥3的正整数解等价于求③的非负整数解。

易观察到7•2+13•(-1)=1

,7•406+13-(-203)=203

即mo=4O6no=-203是③的整数解

/.③的整数通解为

m,=406-13kn,=-203+7kk∈Z

令m,20n,20,解得29≤k≤31..................

20分

取k=29,30,31得到③满足条件的三组非负整数解：

第13页共82页

m,=29mf=16m,=3

n,=On,=7n—14

从而得到②满足条件的三组正整数解：

m-33[m-20∖m-7

\1\................30

〃=3[n=10[〃=17

分

1)在m=33,n=3时，显然X5=X6=X7=13仅有一种可能，

又设Xi=7yi(i=L2,3,4),于是由不定方程yι+y2+y3+y4=33有C数=Cf2=4960

组正整数解。

，此时①有满足条件的《2=4960组正整数解。

2)在m=20,n=10时，设Xi=7yi(i=l,2,3,4),xj=13yj(j=5,6,7)

由yi+y2+y3+y4=20,有G*9组正整数解；以及y5+y6+y7=10,有组正整数

解。

.∙.此时①有满足条件的C：9•《=34884组正整数解。

3)在m=7,n=17时，设Xi=7yi(i=l,2,3,4),xj=l3yj(j=5,6,7)

由y1+y2+y3+y4=7,有Ci组正整数解；以及y5+y6+y7=17,有G；组正整数

解。.......40分

综上所述，①满足条件的正整数解的组数为

Cl2+Cf9∙Cɜ+eð∙Gi=4960+34884+2400=42244................50分

注本题为2002年联赛二试最后一题，是一道不是很难的组合数论问题.问题求

解过程中多次用到了我们的例8的结论.

第14页共82页

2.第二讲组合计数（2）

2.1.本讲概述

组合计数的方法很多，除了上一讲的枚举、对应方法之外还包括：算两次、

递推方法、容斥原理、利用恒等式、母函数方法等；容斥原理的方法将在第四

讲讲述，递推方法我们在数列部分单独讲述.本讲主要讨论利用算两次方法计数

的问题以及较为简单的递推方法（因为我们暂不具备完善的递推数列知识）；

另外，本讲还将涉及到组合计数的二试与冬令营级别难度的少数问题.

首先给出本讲问题中要用到的知识（虽然这些知识可能暂时没有学到，但本

讲只需会用即可）：

二项式定理：（χ+y）"=2c*iy",特别地，（l+χ）"=NGW,其中〃∈W

Jl=Ok=0

特征方程与数列通项：

记一列数卬,。2,……为数列｛aj，如果它满足a”+2=Pan+1+qall,（n≥V）,那

么称χ2=pχ+q为此数列的特征方程，（1）当有两互异实根时，数列通项为

Clll=GC-X∣'+β∙χ'1↑

（2）当有二等根时,数列通项为％=（α+以）*

其中α,4为根据初值确定的待定系数

2.2.例题精讲

2.2.1.板块一算两次

算两次是一种非常重要的思想方法，在代数、组合、几何中都有涉及.组合

问题中，组合极值、组合不等式也常常涉及到算两次.组合计数中，在直接计算

第15页共82页

非常复杂甚至无从入手时，我们常常利用算两次方法.顾名思义，算两次是指用

不同的方法或者从不同的角度对同一个量进行计算，当两次都得到精确值时，

我们就得到一个等式，当为估计式时，我们就得到一个不等式.事实上，数学中

有相当大一部分定理就是利用算两次思想对原有的问题进行剖析，得到新的内

在关系式.

【例11】设…，4,为1，2,…，n的一个排列，人是集合„<α*,i>k｝元

素的个数，而g*是集合｛q∣4>%,i<左｝元素的个数（左=1,2,…，证

明Szt=SW

k=lk=∖

【解析】考虑集合S=｛（q,%）∣q∙<%,i>左｝的元素个数网。一方面，固定攵先对i

求和，然后再对左求和，得IS卜t∕t；另一方面，固定i先对左求和，

k=∖

然后再对i求和，又得到∣s∣=fg产5gi所以得力Z=E>一

/=I⅛=1A=Ik=l

注本题只是为了说明算两次的基本思想和方法，这里的计数是抽象的，这种方

法相当于考虑各个分量对总体的“贡献”，因此也有人把它叫做“贡献法”.请

参考习题第一题

【例12】有n粒小球，任意将其分成两堆，求出两堆球数之积，再将其中一堆任

意地分成两堆，求出此两堆之积，如此下去，直至将小球分成n堆（每

个球1堆）为止.记此过程中所有的乘积之和为S,求S的所有可能值.

【解析】以n=8为例，不论如何分，最后总得到S=28=Cj,于是猜想对一般情

形总有S=C3即n粒小球中任取两个组成小球对的个数；另一方面，

每将一些小球分成两堆，就将原来的一些小球对（假设只有同一堆才能

组成小球对）拆开，拆开的数目恰为两堆个数之积，最终的小球对个数

为0,从而乘积之和即为最初的小球对个数，故得证.

注本题构造了一种巧妙的对应，使原来无法下手的问题变得有章可循.事实上,

组合问题，特别是算两次问题最关键的就是寻找算两次的对象，本题中就是对

第16页共82页

小球对进行算两次，使得问题清晰明了.

【例13】一张正方形纸片内有IOOO个点，这些点及正方形的顶点中任意3点不

共线.在这些点及正方形的顶点间连一些线段将正方形全部分成小三角

形(它们都以所连线段及正方形的边为边，且所连线段除端点外两两无

公共点).问一共连有多少条线段，一共得到多少个三角形？

【解析】设一共连有/条线段，得到k个三角形.

首先对角度和进行计数：一方面,所得k个三角形的内角和为Z∙18O；

另一方面，计算IOOO个内点及4个正方形顶点处内角和为

1000∙360+4.90,从而算得k=2002;

其次，对边数进行计数：k个三角形共3k条边，另一方面，每条线段

是两个三角形的公共边，正方形的每条边被计算1次，共2/+4条边，

从而2/+4=3左，得到/=3001

注本题的背景是计算机图形学中著名的三角面片分划问题，这类问题在冯康先

生的有限元中也有应用.

从本题及习题2可以得到计算这类问题的一般方法，即对边、角乃至同色角、

异色角等元素进行计数.

【例14](选讲)能否把1,1,2,2,3,3,…，1986,1986这些数排成一行，使得

两个1之间夹着1个数，两个2之间夹着2个数，两个1986之间夹着

1986个数？

【解析】设能将上述数字排成一行满足题设，这是每一个数i(l≤i≤1986)可赋予

它一对有序实数(与上)作为坐标，这里坐标值分别为它第一次与第二次

出现的位置序号.显然有关系：χ=x,.+z+l.

现用两种方法计算全体数的坐标和：

2x1986

一方面，直接从整体看，坐标和为Zk=I986x(2x1986+1)为偶数；

k=∖

另一方面，就某一个i,两坐标和为2x,∙+i+l,从而所有坐标和为

198619861986

Z(2x,.+ι+l)=2∑x,.+∑z+l986=偶数+993×1987为奇数.此两者显

Z=IZ=I/=1

第17页共82页

然矛盾

注本题为第二届冬令营的一道很难的问题,方法较多，上面给出的方法是一个

很巧妙的解法，利用奇偶性导出了矛盾，是命题人所没有想到的.

2.2.2.板块二递推方法

当所计数对象按从1到n有规律出现时，可视之为一个数列并考察其相邻项

之间关系，得到递推关系式,进而利用数列知识进行求解.一般来说，这类问题

的关键在于如何得到递推关系式.对于竞赛选手而言，由组合问题的递推关系式

得到通项总是很简单的，因为组合问题的特性决定了递推关系式不会太过复杂.

由于我们没有详细讲述数列通项求法，所以这里只给出较为简单的问题.

注：建议教师主要讲述如何由题目条件得到递推式，至于递推式求解可以淡

化或者让学生自行求解

【例15】（FibOnaCCi数列）假设一对兔子每隔一月生一对小兔，每对小兔两个

月后也逐月生一对小兔，如年初时放一对成年兔，那么一年以后兔房中

有多少只兔子？

【解析】用%表示第n个月初的小兔对数,易得到“∣=l,α2=2,。3=3,…

一般地，第n个月初的小兔分为两部分：第n-1个月的兔子数与第n个

月初出生的小兔对数，

即得到递推式由特征方程的结论及初值，可得到

"13=377

注关于斐波那契数列的进一步知识我们到数列部分再详细讲述

【例16】用1,2,3来构造一个n位数，但不允许数位中出现两个连续的1,问这

样的数有多少个？

【解析】设有α“个，显然。产3,。2=8，讨论：

若n位数第一位不是1,那么后面可以随便写，于是这样的有20,τ个,

若第一位是1,第二位写2或3,第三位后可以随便写，于是这样的有

第18页共82页

2α,τ个，

得到递推式“z,=2α,ι+2α.2,"N3,由特征方程的结论及初值，化简得

到

+22

βn=^((l+√3Γ-(l-^Γ)

注一般写出原始结果即可，或者把化简结果同时写出

2.2.3.板块三组合计数综合问题

【例17】设r,SJ为整数，集合伍|。=2，+2'+2，,03<5<厂｝中的数由小到大组

成数列｛七｝：7,11,13,14,…，则=131。

【解析】•；r,s,t为整数且O≤f<s<r,.∙.r最小取2,此时符合条件的数有C；=1

厂=3,SJ可在0,1,2中取，符合条件有的数有C；=3

同理，r=4时，符合条件有的数有C：=6

r=5时，符合条件有的数有C；=10

r=6时，符合条件有的数有C；=15

r=7时，符合条件有的数有C；=21

因此，/6是尸=7中的最小值，即—=2°+2∣+2,=131

注本题为2005年四川预赛题，事实上此题源自2003年全国高考理科试卷压

轴题，用二进制方法求解最为方便，可参考左晓明《2003年高考理科数学压轴

题的一种巧妙解法及其推广》中学教研2003.12

【例18】如果自然数α的各位数字之和等于7,那么称。为“吉祥数”.将所有“吉

祥数”从小到大排成一列，…，若可=2005,则。5"=-

【解析】准确理解“吉祥数”的定义是解题的前提，根据题意，可将此计数问题

转化为考虑不定方程的非负整数解的个数.

∙.∙方程m+/+∙∙∙+4=机的非负整数解的个数为eɪɪ.而使

项》,工工0(摩2)的整数解的个数为。黑_2-现取机=7,可知，攵位“吉祥数”

第19页共82页

的个数为P(Z)=C3∙

∙.∙2005是形如五反的数中最小的一个“吉祥数”，且

P(I)=C；=1,P(2)==7,P(3)==28,

对于四位“吉祥数”嬴，其个数为满足α+匕+c=6的非负整数解个数，即

%τ=28个.

.∙.2005是第1+7+28+28+1=65个“吉祥数”,即-=2005.从而

n—65,5〃=325.

5

又P(4)=《=84,R5)=Cf0=210,而EP(k)=330.

k=∖

•••从大到小排列的最后六个五位“吉祥数”依次是：70000,

61000,60100,60010,60001,52000.

,第325个“吉祥数”是52000,即a5n=520∞.

注1、本题为2005年全国联赛试题

2、很多计数问题都可以转化为求不定方程的解的组数，一般地，有

(1)不定方程内+/+…+%=加的非负整数解的组数为

^n-∖_「"I

tι+m-∖-n+m-∖；

(2)不定方程x∣+%+…+%=加的正整数解的组数为C；；O

【例19】若四位数〃="〃的各位数码α,"c,d中，任三个数码皆可构成一个三

角形的三条边长，则称〃为四位三角形数，试求所有四位三角形数的个

数.

【解析】三个数构成三角形的三条边长的充要条件是任意两个数之和大于第三

个数.本题需要根据四个数码的各种可能情况分类进行分析，按照四个

数码取值个数的不同进行分类比较容易入手一些.

称Q"c,d)为〃的数码组，则α,"c,deM={l,2,,9}.

(1)当数码组只含一个值，为(α,α,α,α),α=1,2,,9,共得9个〃值.

(2)当数码组恰含二个值a,。(a>b).

①数码组为(a,a,a,。)型，则任取三个数码皆可构成三角形，对于每个

第20页共82页

a∈{2,,9),人可取a-1个值，则数码组个数为苫5-1)=36,对于每组

a=2

(a,a,a,b),人有4种占位方式，于是这种〃有36x4=144个.

②数码组为(。力力，加型(a>∕?),据构成三角形条件，有b<a<2b,

力的取值1234^5^6789

(b,2h)M中a的个012343210

数

共得16个数码组，对于每组(a,份，。有4种占位方式，于是这种〃有

16x4=64个.

③数码组为(a,a,b,。)型Qa>b),据构成三角形条件，有A<a<如，同上

得16个数码组，对于每组(a,a力力)，两个。有C；=6种占位方式，于是这种〃有

16x6=96个.

以上共计144+64+96=304个.

(3)当数码组恰含三个值a,"c(a>b>c).

①数码组为3"c,c)型，据构成三角形条件，则有c<8<a<2c,这种

(a,"c∙,c)有14组，每组中a/有A：=12种占位方式，于是这种〃有14x12=168

个.

②数码组为(a,。,。,C)型，c<b<a<b+c,此条件等价于M={1,2,,9}中

取三个不同的数构成三角形的方法数，有34组，每组中。力有A；=12种占位方

式,于是这种〃有34x12=408个.

③数码组为(a,a,。,C)型，c∙<"<a<0+c,同情况②，有34A：=408个〃值.

以上共计168+408+408=984个〃值.

(4)a,8,c,d互不相同，WJWd<c<b<a<c+d>这种a,b,c,d有16组,

每组有4!种排法，共得16X4!=384个〃值.

综上，全部四位三角形数