组合几何计数问题

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

明：k元的不好的子集个数为Cn?k?1

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

显然有2?ij?1?ij(j?1,2,...,k?1)；

k

2...k?i作变换 1?i1?i2?1?i3?

?k(?1)?n?k，并取序列：?1

(i1,i2?1,i3?2,...,ik?(k?1))，它是1,2，n-k+1中的一个严格上升的序列

作对应(i1,i2,...,ik)?(i1,i2?1,i3?2,...,ik?(k?1))，

易证明它为一一对应，且后者的种数为从n?k?1个元素中取k个元素的组合数Cn?k?1，故得证

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

k

大显身手

1． （1）在100件产品中有6件次品，现从中任取3件产品，至少有1件次品的不同取法的种数是

A．C6C94 B．C6C99 C.C100

3

333?C94 D．A100?A941

2

1

2

（2）从4名男生和3名女生中选出4人参加某个座谈会，若这4人中必须既有男生又有女生，

则不同的选法共有

A.140种 B．120种 C 35种 D．34种

333

【解析】 （1） C 任取3件产品有C100种方法，其中无次品有C94种方法，故至少有1件次品的方法数为C100?C94. 3122

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

3313213

一男三女有C14?C5种选法，则总的不同的选法有C4?C3?C4?C3?C4?C3=34(种)

3

2． 由三个数字 1、2、3 组成的 5 位数中, 1、2、3 都至少出现 1 次, 这样的 5 位数共有多少个？ 【解析】 在 5 位数中, 若 1 只出现 1 次，有 C5(C4?C4?C4)?70 个；

若 1 只出现 2 次，有 C5(C3?C3)?60 个；

若 1 只出现 3 次，有 C5C2?20 个． 则这样的五位数共有 150 个． 故填 150个． 注 本题为05年江苏省预赛试题

3

12

1

2

1

1

2

3

3． 已知集合A?x5x?a?0，B?x6x?b?0,a,b?N，且A?B?N??2,3,4?，则整数对?a,b?的个数为

A. 20 B. 25 C. 30 D. 42 【答】 （ ）

????

?b1??2?ab?6

【解析】 由5x?a?0?x?；6x?b?0?x?。要使A?B?N??2,3,4?，则?，即

a56?4??5?5?

6

高一·联赛班·寒假第1讲·教师版

?6?b?1211

。所以数对?a,b?共有C6C5?30。 ?

?20?a?25

注 本题为2006年联赛试题

4． 记集合T??0,1,2,3,4,5,6}，M??

到小顺序排列，则第2005个数是

?a1a2a3a4?

?2?3?4ai?T,i?1,2,3,4?，将M中的元素按从大

77?77?

5563556211041103

?2?3?4 B. ?2?3?4 C. ?2?3?4 D. ?2?3?4 7777777777777777

4

【解析】 用[a1a2?ak]p表示k位p进制数，将集合M中的每个数乘以7，得

A.

M??{a1?73?a2?72?a3?7?a4|ai?T,i?1,2,3,4}?{[a1a2a3a4]7|ai?T,i?1,2,3,4}.

M? 中的最大数为[6666]7?[2400]10。

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

4

而[396]10?[1104]7, 将此数除以7，便得到M中的数：

1104

?2?3?4.故选C。 7777

注 本题为2005年联赛试题，题目形式提示我们，要采用进制转换.事实上，这类题目在小学和初中是极

为常见的.

5． 已知两个实数集合A={a1,a2,?,a100}与B={b1,b2,?,b50}，若从A到B的映射f使得B中每个元素

都有原象，且

f(a1)≤f(a2)≤?≤f(a100) 则这样的映射共有

50504949

(A)C100 (B) C99 (C) C100 (D) C99

【解析】 不妨设b1<b2<?<b50，将A中元素a1, a2, ? , a100按顺序分为非空的50组，定义映射f：A→B，

使得第i组的元素在f之下的象都是bi (i=1,2,?,50)，易知这样的f满足题设要求，每个这样的分组都一一对应满足条件的映射，于是满足题设要求的映射f的个数与A按足码顺序分为50组的

分法数相等，而A的分法数为C99，则这样的映射共有C99，故选D。

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

6． 在世界杯足球赛前，F国教练为了考察A1,A2,?,A7这七名，准备让他们在三场训练比赛(每场90

分钟)都上场，假设在比赛的任何时刻，这些中有且仅有一人在场上，并且A1,A2,A3,A4每人上场的总时间(以分钟为单位)均被13整除，如果每场换人次数不限，那么按每名队员上场的总时间计算，共有多少种不同的情况。

【解析】 设第i名队员上场的时间为xi分钟(i=1,2,3,?,7)，问题即求不定方程

x1+x2+?+x7=270 ①

在条件7|xi (1≤i≤4)且13|xj (5≤j≤7)下的正整数解的级数。 若(x1,x2,?,x7)是满足条件①的一组正整数解，则应有

4949

?x

i?1

4

i

=7m

?x

j?5

7

j

=13n m,n∈N

∴m,n是不定方程

7m+13n=270 ② 在条件m≥4且n≥3下的一组正整数解。 ????10分 ∵ 7(m-4)+13(n-3)=203

高一·联赛班·寒假第1讲·教师版

7

令 m′=m ?4 n′=n ?3 有

7m′+13n′=270 ③ ∴ 求②满足条件m≥4且n≥3的正整数解等价于求③的非负整数解。 ∵易观察到 7·2+13·(-1)=1

∴ 7·406+13·(-203)=203 即 m0=406 n0= ?203是③的整数解 ∴ ③的整数通解为

m′=406 ?13k n′= ?203+7k k∈Z

令 m′≥0 n′≥0,解得 29≤k≤31 ????20分 取k=29,30,31得到③满足条件的三组非负整数解：

?m??29 ?

?n?0??m?33

n?3?

?m??16

??n?7??m??3

??n?14?

?m?7

????30分 ?n?17?

4?1

3

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

?m?20

?n?10?

1)在m=33,n=3时，显然x5=x6=x7=13仅有一种可能，

又设xi=7yi (i=1,2,3,4)，于是由不定方程y1+y2+y3+y4=33有C33?1?C32?4960组正整数解。 ∴此时①有满足条件的C32=4960组正整数解。

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

由y1+y2+y3+y4=20，有C19组正整数解；以及y5+y6+y7=10，有C9组正整数解。 ∴此时①有满足条件的C19?C9=34884组正整数解。 3) 在m=7,n=17时，设xi=7yi (i=1,2,3,4)，xj=13yj (j=5,6,7)

由y1+y2+y3+y4=7，有C6组正整数解；以及y5+y6+y7=17，有C16组正整数解。????40分 综上所述，①满足条件的正整数解的组数为

C32?C19?C9?C6?C16=4960+34884+2400=42244 ????50分

注 本题为2002年联赛二试最后一题，是一道不是很难的组合数论问题.问题求解过程中多次用到了我们

的例8的结论.

3

3

3

3

2

3

2

3

2

3

2

3

8

高一·联赛班·寒假第1讲·教师版

第二讲 组合计数（2）

本讲概述

组合计数的方法很多，除了上一讲的枚举、对应方法之外还包括：算两次、递推方法、容斥原理、利用恒等式、母函数方法等；容斥原理的方法将在第四讲讲述，递推方法我们在数列部分单独讲述.本讲主要讨论利用算两次方法计数的问题以及较为简单的递推方法（因为我们暂不具备完善的递推数列知识）；另外，本讲还将涉及到组合计数的二试与冬令营级别难度的少数问题.

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

二项式定理：(x?y)?特征方程与数列通项：

记一列数a1,a2,...,an,...为数列{an}，如果它满足an?2?pan?1?qan,(n?1)，那么称x?px?q为此数列的特征方程，（1）当有两互异实根时，数列通项为an???x1???x2；

（2）当有二等根时，数列通项为an?(???n)?x1 其中?,?为根据初值确定的待定系数

nn

n

n

?C

k?0

n

k

n

x

n?k

kk

y，特别地，(1?x)??Cnx，其中n?N? k

n

k?0

n

2

例题精讲

板块一 算两次

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

不等式也常常涉及到算两次.组合计数中，在直接计算非常复杂甚至无从入手时，我们常常利用算两次方法.顾名思义，算两次是指用不同的方法或者从不同的角度对同一个量进行计算，当两次都得到精确值时，我们就得到一个等式，当为估计式时，我们就得到一个不等式.事实上，数学中有相当大一部分定理就是利用算两次思想对原有的问题进行剖析，得到新的内在关系式.

【例11】 设a1,a2,…,an为1，2，?，n的一个排列，fk是集合aiai?ak,i?k元素的个数，而gk是集

合aiai?ak,i?k元素的个数（k?1,2,…,n），证明

??

??

?f??g

kk?1

k?1

nn

k

【解析】 考虑集合S?(ai,ak)ai?ak,i?k的元素个数S。一方面，固定k先对i求和，然后再对k求

和，得S?

n

??

?f

k?1k

n

kn

；另一方面，固定i先对k求和，然后再对i求和，又得到S?。

?g??g

ii?1

k?1

nn

k

，

所以得

?f??g

k?1

k?1

k

注 本题只是为了说明算两次的基本思想和方法，这里的计数是抽象的，这种方法相当于考虑各个分量对总体的“贡献”，因此也有人把它叫做“贡献法”.请参考习题第一题

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

高一·联赛班·寒假第1讲·教师版

9