当前位置:首页 >> 学科竞赛 >> 清北学堂 2012年暑假数学高端班(精品班、特训一)组合导学

清北学堂 2012年暑假数学高端班(精品班、特训一)组合导学


北京清北学堂教育科技有限公司

电话:010-88400806,010-88400903

网址:www.topschool.org

组合导学 一、 组合计数
知识点:
(1)几种特殊的排列、组合 1.圆排列 定义 1:从几个元素中任取 r 个不同元素仅按元素之间的相对位置而不分首尾排 成一个圆圈,

这种排列称为 n 个不同元素的 r——圆排列。r——圆排列数记为

K nr .

r 定理 1: K n ?

Pnr r

2.重复排列 定义 2:从 n 个不同元素中允许重复的任取 r 个元素排成一列,称为 n 个不同元 素的 r——可重复排列. 定理 2:n 个不同元素的 r——可重排列数为 n r . 3.不全相异元素的全排列 定义 3:设 n 个元素可分为 k 组,每一组中的元素是相同的,不同组间的元素是 不同的,其中第 i 组的元素个数为 ni(i=1, 2, ?, k ), n1 ? n2 ? ? ? nk ? n . 则 这 n 个元素的全排列称为不全相异元素的全排列.
n! n1 !n2 !? nk !

定理 3:n 个元素的不全相异元素的全排列个数为

4.多组组合 定义 4:将 n 个不同的元素分成 k 组的组合称为 n 个不同元素的 k——组合.

1

北京清北学堂教育科技有限公司

电话:010-88400806,010-88400903

网址:www.topschool.org

定理 4: 对于一个 n 个不同元素的 k——组合, 若第 i 组有 ni 个元素 (i=1, 2, ?, k),则不同的分组方法数为
n! n1 !n2 !? nk !

5.重重组合 定义 5:从 n 个不同元素中任取 r 个允许元素重复出现的组合称为 n 个不同元素 的 r——可重组合.
r 定理 5:n 个不同元素的 r——可重组合的个数为 Cn ? r ?1 .

(2)枚举法 所谓枚举法就是把集合 A 中的元素一一列举出来, 从而计算出集体 A 的元素个数。 它是最基本, 也是最简单的计算数方法。应用枚举法计数的关键在于一一列举集 合中的元素时必须做到既不重又不漏。 (3)分类计数原理与分步计数原理 分类计算原理 完成一件事,有几种方式,第一种方式有 m 种方法,第二种方式 有 n 种方法,??最后一种方式有 r 种方法.不管采取哪一种方法都能完成这件 事,则完成这件事的方法总数为 m+n+?+r . 分步计数原理 完成一件事,有几个步骤,第一步有 m 种方法,第二步有 n 种方 法,?,最后一步有 r 种方法,要完成这件事,必须通过每一步,则完成这件事 的方法总数为 m·n??r. 应用分类计数原理的关键在于分划, 即把一个所要计数的集合 S 分划成一些两两 不交的小集合,且使每个小集合都便于计数. 应用分步计数原理的关键在于分解, 即把一个所要计数的集合 S 分解成若干个集 合的乘积. 对一个集合 S 的分划或分解,没有一般方法,应由具体问题而定,而这正是应 用两个原理解题的难点与技巧所在. (4)递推方法 将与正整数有关的数字问题,通过寻求递推公式,或通过递推公式,而使问题得 到解决的方法,叫做递推方法. 递推方法几乎对所有数学分支都具有重要的作用, 当然对组合计数就更不例外了, 它是组合计数的常用方法.
2

北京清北学堂教育科技有限公司

电话:010-88400806,010-88400903

网址:www.topschool.org

应用递推方法解题, 会遇到如下两类问题:一是如何找到满足题设条件的递推公 式,二是推理计算.详见例题. (5)母函数法 母函数是一种非常有用的方法.这种方法的最早系统叙述见于 Laplace 在 1812 年出版的名著《概率解析理论》中.这种方法思想简单,把离散数列和幂级数一 一对应起来, 把离散数列间的相互结合关系对应成幂级数间的运算关系,最后由 幂级数来确定离散数列的构造。 简要地说,母函数方法是将一个有限或无限的数列 { ak }={ a0 , a1 , a2 ,?, ak , ?} 和如下形式的多项式

f ( x) ? a0 ? a1 x ? a2 x 2 ? ? ? ak x k ? ?
联系起来,构成对应关系

? ak ? ?

f ( x)

这个 f(x)就称为{ ak }的母函数或生产函数.意思是这个数列{ ak }是由多项 f(x) 产生的. 例如:组合数列的母函数是.因为由二项式定理可得
0 1 n n (1 ? x)n ? Cn ? Cn x ? ? ? Cn x

(1 ? x)n 是最常见的母函数.
Ⅶ.子集类 一个 n 元素合 X 有 2 n 个子集 A1 , A2 ,?, A2n ,如果以它的部分子集作为元素, 又可得到一个集合 F={ A1 , A2 ,?, Ak }(1≤k≤ 2 n ),这个集合 F 的称为原来 集合 X 的一个子集类. 应用子集类知识可以帮助我们解决如下二类问题:

3

北京清北学堂教育科技有限公司

电话:010-88400806,010-88400903

网址:www.topschool.org

a.什么时候可以把一个整数(集合)写成若干个满足一定条件的整数(子集) 之和(并). b.在可以写的情况上有多少种写法.前者是存在性问题,后者组合计数问题.

模拟真题:
题 1:设 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)= 题 2:设 n>1,两个自然数的集合 { a1 , a2 , ?, an }≠{ b1 , b2 , ?, bn }, 和集 ai ? a j 1 ? i ? j ? n ? bi ? b j 1 ? i ? j ? n
n( n ? 1) 2

?

? ?

?



这里的相等计数及元素的重数, 即如果元素 S 在①的左边出 k 次(用 k 种方法表 示成 ai ? a j 的形式),那么 S 也在①的右边出现 k 次,证明存在自然数 h,使 n=

2h .
解析:考虑母函数

4

北京清北学堂教育科技有限公司

电话:010-88400806,010-88400903

网址:www.topschool.org

f ( x) ? xa1 ? xa2 ? ? ? xan
又 g ( x) ? xb1 ? xb2 ? ? ? xbn (注意,这里的 ai 与 bi 不是母函数的系数,而是指数)

( f ( x))2 ? f ( x2 )
? ( x a1 ? x a2 ? ? ? x an )2 ? ( x 2 a1 ? x 2 a2 ? ? ? x 2 an ) ? 2

1?i ? j ? n

?

x

ai ? a j



同样 ( g ( x))2 ? g ( x 2 ) ? 2

1?i ? j ? n

?

xi

b ?b j



②、③中系数表示和 ai ? a j , bi ? b j 出现的次数,由题设知

f 2 ( x ) ? f ( x 2 ) ? g 2 ( x) ? g ( x 2 )
即 f 2 ( x) ? g 2 ( x) ? f ( x 2 ) ? g ( x 2 )



由于 f(1)-g(1)=n-n=0,所以(x-1)|(f(x) -g(x)),从而存在自然数 h1 ,使

f ( x) ? g ( x) ? ( x ?1)h1 p( x), p(1) ? 0
因此 f ( x2 ) ? g ( x2 ) ? ( x2 ?1)h1 p( x2 )
( x ? 1) h1 p ( x 2 ) p( x)





即 f ( x) ? g ( x) ?

令 x=1,得 2n ? 2h1 ,即 n ? 2h1 ?1 由于 n>1,所以 h1 ? 1, h1 ? 1 为某一自然数,从而有 n= 2 h . 题 3: ( 第 41 届 IMO 中 国 队 选 拔 赛 试 题 ) 设 n 为 正 整 数 , 记 集 合

M ? ?? x, y ? x, y是整数, 1 ? x, y ? n? ,定义在 M 上的函数 f 具有性质:
5

北京清北学堂教育科技有限公司

电话:010-88400806,010-88400903

网址:www.topschool.org

(a )

f ( x, y ) 取值于非负整数;

(b )
(c )

1 ? x ? n 当时,有 ? f ( x, y ) ? n ? 1
y ?1

n

若 f ( x1 , y1 ) f ( x2 , y2 ) ? 0 ,则 ( x1 ? y1 )( x2 ? y2 ) ? 0

试计算这样的函数 f 的个数 N(n) ,并指出 N(4)的具体数值. 解析:设对给定 xi ?[1, n], f ( x0 , y)(1 ? y ? n) 中不为 0 的最大 y 为 yi 则由条件 ( c ) ,如若 f ( x0 , y) ? 0 ,则必有 y ? yi ,故而因数表来表示为如图

a1
0 0 0

?

ay1

0
?

0

0 0 0
a ? y1
i ?1 n ?1

0 0 0
?

0 0 0
a ? y1
i ?1 n

0 0 0

ay1?1
0 0

ay1? y2
?

0 0

0

其中 ai 为非负整数, a y1 , a y1 ? y2 ,?, a y1 ? y2 ?? y1n 不为 0.每行数之和为 n ?1 ,而对固定 的 r ,有 a1 +a2 ? ? ? ar ? n ? 1
r ?1 其中 ar ? 0, a1 , a2 ,?,ar 均为非负整数的解有 Cn ?2? r 组

故 f 函数的个数

N ( n) ?

y1 ? y2 ?? yn ? 2 n ?1 yi ?0, yi ?Z

?

yn ?1 y2 ?1 1 ?1 Cny? 2? y1 ? Cn ? 2? y2 ? ? Cn ? 2? yn

再利用

i ? j ?t ij?Z ,ij ? 0

?

j Cri Csj ? Cri ? ?s

n2 ?1 知 N (n) ? Cn ?1 2 ? 455 特殊地,有 N (4) ? C15

二、组合几何及应用
知识点:
6

北京清北学堂教育科技有限公司

电话:010-88400806,010-88400903

网址:www.topschool.org

(1) 凸图形与凸包 平面图形是平面上点的集合,就其性质而言,可分离散点集与连续点 集, 比如, 一个有限 n 点组就是离散点集; 而一条曲线则是连续点集。 定义 1:如果对于平面图形 M 中的任意两点 A,B 线段 AB 上的每一点 均属于 M,则称图形 M 为凸. 定义 2:包含点集(图形)M 的最小凸图形称为点集(图形)M 的凸 包. 定理 1:两个凸图形的交仍是凸图形. 定理 2:任意个凸图形的交仍是凸图形. (2) 组合方法 在组合几何问题中常用的组合方法有:计数、原理、算两次、抽屉原 理、极端原理等. (3) 构造法处理几何中某些存在性命题 存在性命题,要求证明存在某个事物具有问题中所要求的性质,构造 性论证就是直接,具体地造出这样的事物. (4) 两种论证法 类似于传统的平面几何,组合几何中,也有不少问题,基于集合的想 法和代数的工具都能给予论证和解答. (5) 方法的变通 组合几何的内容较为复杂,这正是组合几何的特点:问题灵活多样, 解法千差万别,虽有某些“基本招式” ,但确无“定法定则” ,所以解 这类问题时必须通变灵活,最忌执一.
7

北京清北学堂教育科技有限公司

电话:010-88400806,010-88400903

网址:www.topschool.org

模拟真题: 题 1:设 M 为坐标平面上坐标为(p·2002,7p·2002)的点,其中 p 为素数,
求满足下列条件的直角三角形的个数: (1)三角形的 3 个顶点都是整点,而且 M 是直角顶点; (2)三角形的内心是坐标原点. 解 析 :如图 3 所示,关于 OM 的中点 Q 作中心对称,满足 条件的直角三角形变为以 O 为直角顶点、M 为内心的直角 三角形 OAB,A、B 仍是整点. 直线 OM 的斜率为 tan ? ? 7 ,直线 OA 斜率为
tan ? ? tan( ? ? 45 ? ) ? tan ? ? 1 3 直线 OB 的斜率为 ? , 1 ? tan ? 4
图3 O y B M Q A

x

?

4 . 3
由此可设点 A 的坐标为 (4t ,3t ) ,点 B 的坐标为(-3s,4s) ,从而知 t ? 4t ? 3t ,

s ? ?3s ? 4s 都是整数.
设 ?ABC 的内切圆半径为 r ,则
r? 2 2 OM ? p ? 2002 ? 12 ? 7 2 ? 5 p ? 2002 . 2 2

又如 OA ? 5t , OB ? 5s, AB ? 5 t 2 ? s 2 , OA ? OB ? AB ? 2r ,所以

5 t 2 ? s 2 ? 5t ? 5s ? 2 ? 5 p ? 2002 ,
即 t 2 ? s 2 ? (t ? s) 2 ? 4 p ? 2002 ? (t ? s) ? 4 p 2 ? 2002 2 ,整理得

(t ? 4004 p)(s ? 4004 p) ? 2 p 2 ? 2002 2 ? 23 ? 7 2 ? 112 ? 13 2 ? p 2 , 由于 5t ? 2r ,5s ? 2r , 所以 t ? 4004 p ? 0, s ? 4004 p ? 0 .
所以所求三角形个数等于 23 ? 7 2 ? 112 ? 13 2 ? p 2 的正因子个数. 当 p ? 2,7,11,13 时,有 (3 ? 1)(2 ? 1)(2 ? 1)(2 ? 1)(2 ? 1) ? 324 个直角三角形符合 题意; 当 p ? 2 时,有 (5 ? 1)(2 ? 1)(2 ? 1)(2 ? 1) ? 162 个直角三角形符合题意. 当 p ? 7 ,或 11,或 13 时,均有(3+1) (4+1) (2+1) (2+1)=180 个直角 题 2:证明不可能在平面上放有限个点,使得每一条过其中两点的直线都过第三 点,除非这些点全在一条直线上。
2 解析:过平面上 n 个点,最多 Cn 条直线,如果每条直线外都有点,则点到直线

8

北京清北学堂教育科技有限公司

电话:010-88400806,010-88400903

网址:www.topschool.org

的诸距离中必定有最小值,如图,点 P 到直线 l 的距离 PQ 最小,直线 l 上有 3 个 不同点,则必有两个点在 Q 的同侧,从而可以知道 P2 到直线 PP 1 最小。矛盾。
P

P1

P2

Q

l

注:这类问题的解法是考虑极端情形。 题 3: 平 面 上 给 定 五 个 点 , 其 中 无 三 点 共 线 , 试 证 每 三 点 确 定 的 三 角 形面积中,最大与最小的比不小于
5 ?1 2

, 考虑其凸包(这只能是三角形,凸 解 析 : 设 五 个 点 为 A1 , A2 , A3 , A4 , A5 ,
四边形、凸五边形). ( 1) 凸 包 为 三 角 形 或 凸 四 边 形 的 情 形 一 并 处 理 .此 时 必 有 一 个 点 落 在某个三角形内部(凸包为三角形时显而易见,凸包为四边形 时,可作一条对角线). 不 妨 设 A4 在 三 角 形 A1 A2 A3 中 ,则 三 角 形 A1 A4 A2 、 A2 A4 A3 、 A3 A4 A1 中 面 积 最 小 者 , 设 为 A1 A4 A2 , 不 超 过
?A1 A2 A3 5 ?1 ?3? ?A1 A4 A2 2
1 ?A1 A2 A3 , 即 3

( 2 ) 若 凸 包 为 凸 五 边 形 A1 A2 A3 A4 A5 , , 在 对 角 线 A1 A3 及 A1 A4 上 依 次 取 点 P、 Q, 使 得
A1 P A1Q 5 ?1 ? ? PA3 QA4 2

则 直 线 PQ / / A3 A4 ( 请 读 者 自 己 画 一 个 图 ) 。 如 果 A2 、 A5 中 有 一 个 与 点 A3 、 A4 位 于 同 侧 , 不 妨 设 为 点 A2 , 则

9

北京清北学堂教育科技有限公司

电话:010-88400806,010-88400903

网址:www.topschool.org

?A1 A3 A4 A1 A3 AP ? ? 1? 1 ?A2 A3 A4 PA3 PA3 ? 1? 5 ?1 5 ?1 ? 2 2

如 果 A2 、 A5 与 点 A1 位 于 直 线 PQ 的 同 一 侧 , 对 角 线 A2 A5 与 A1 A3 必 相 交 ,

? A1P ( 我 们 用 到 了 五 边 形 A1 A2 A3 A4 A5 , 的 凸 性 ) 设 交 点 为 O , 则 AO ,于 1

?A2 A3 A4 OA3 PA3 2 5 ?1 . ? ? ? ? ?A1 A2 A5 A1O A1P 2 5 ?1

10


更多相关文档:

2012年五一数学集训二几何导学

组合特训一导学 12页 2财富值 数论特训一导学 13页 2财富值 清北学堂2011年全国高中数... 9页 2财富值 2011年全国高中数学联赛模... 6页 1财富值如要投...

几何特训一导学

北京清北学堂数学竞赛导学材料几何特训一导学一、几个重要定理: 1、梅涅劳斯定理...2012年暑假数学高端班(特... 16页 1下载券 暑期高中数学特训课程几... 暂无...

...化学(一)《关于晶胞》 (适合特训一、VIP精品班)_免...

2011 暑期化学导学资料——结构化学(一) 《关于晶胞》 (适合特训一、VIP 精品班)晶胞概念是晶体学基本概念,本应在建立点阵概念后再作讨论,但点阵概念较抽象,许...
更多相关标签:
精品导学案 | 高端精品超市 | 高端精品酒店 | 融创 高端精品 | 高端精品 | 邓老师高端摄影精品课 | 小悦高端外设精品店 | 高端精品酒店品牌 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com