haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

数学基础(B层次)

发布时间:2014-02-03 11:04:43  

数 学

基 础

江苏省华罗庚中学 杨志军 2009.7

常用数学公式 排列、组合及其应用 数学归纳及推导

Catalan数

常用数学公式
n(n ? 1) (即 C 2 ) 1、 1 ? 2 ? 3 ? ? ? n ? n ?1 2 n(n ? 1)( 2n ? 1) 2、 1 ? 2 ? 3 ? ? ? n ? 6
2 2 2 2

1 2 3、 1 ? 2 ? 3 ? ? ? n ? n (n ? 1) 2 4
3 3 3 3
n ?1 q ?1 2 3 n 4、 1 ? q ? q ? ? ? q ? (q ? 1) q ?1

常用数学公式
1 1 1 1 1 ? ??? ? 1? 5、 ? 2 2 ?3 3? 4 n(n ? 1) n ?1
1 1 1 ? 6、 ? p p ? 1 p( p ? 1)
7、1 ? 3 ? 5 ? ? ? (2n ? 1) ? (n ? 1) 2

常用数学公式
例1、求三角形个数。

0

1

2

??

n

n ? 1 , f (1) ? 1
n ? 2 , f (2) ? 1 ? 2 ? 3

??

n(n ? 1) f ( n) ? 2

常用数学公式
例2、求三角形个数。 1 2 ?? n

1 2 3 ?? m 三角形的形状分为两种:

(m ? 1)m (n ? 1)n ?n ? ?m 2 2

常用数学公式
例3、近似求圆锥体体积。

h h h h

r1 r2
r3 rn

? (r12 ? r22 ? r32 ? ? ? rn2 )h

常用数学公式
例4、将正整数n分成k个部分(k≤n),使其乘积最大 (最小)。 设:分成 P 1, P 2 ,? P k 满足 P 1?P 2 ??? P k ?n

max( P 1, P 2 , ?, P k ) ? min( P 1, P 2 ,? P k ) ?1
例:n ? 18, k ? 4, 则分为5,5,4,4

常用数学公式
证明:假设 Pj ? max( P 1, P 2 , ?, P k ), P i ? min( P 1, P 2 , ?, P k)

Pj ? Pi ? 2
乘积 Pj Pi ? ? Pj ( Pj ? 2)? ? ( Pj2 ? 2Pj )? ①

又设 Pj ? Pj ? 1 ,则 Pi ? Pj ? 1

( Pj ? 1)( Pj ? 1)? ? ( Pj2 ? 2Pj ? 1)?
得出①<② 同样,乘积最小:1 ,? 1,? ? ,? 1,1, n ? k ? 1 ? ?
k ?1



常用数学公式
幂集计数的公式

例5:整数3的幂集有多少个?

?? ?1?, ?2?, ?3? ?1,2?, ?1,3?, ?2,3? ?1,2,3?
n的幂集计数公式为 2 n

常用数学公式 排列、组合及其应用 数学归纳及推导

Catalan数

排列、组合及其应用
1、排列 全排列 选排列 重复排列 条件排列 错位排列

排列、组合及其应用
(1)全排列

如:1,2,3的全排列 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 共6种
计数公式:Pn ? 1? 2 ? 3? n ? n !

排列、组合及其应用
方法一:生成法

① 生成第一个排列 for i:=1 to n do a[i]:=i;
② 从后向前找到一个顺序 a j ?1 ? a j ③ 从 a j , a j ?1 ,?, an 中找出一个比 a j ?1 大的最小数 ak ④ a j ?1 ? ak 交换

⑤ a j , a j ?1 ,?, an 从小到大排序
⑥ 返回②

排列、组合及其应用
方法二:回溯法 readln(n); else if not(k in s) s:=[]; then begin top:=0; top:=top+1; k:=0; stack[top]:=k; while top>=0 do s:=s+[k]; begin k:=0; k:=k+1; if k>n if top=n then begin then 输出; k:=stack[top]; end; s:=s-[k]; end; top:=top-1;

end

排列、组合及其应用
(2)选排列

从m个元素中,任选n个进

行排列(n≤m) n Pm ? m(m ? 1) ?(m ? n ? 1)
(3)重复排列 例:3个黄球,2个蓝球,4个白球,排成一排, 问有多少种排法? (3 ? 2 ? 4) ! P? 3! ? 2! ? 4!

排列、组合及其应用
(4)条件排列

例:将1,2,3,4,5这5个数进行排列,要求4必
须排在2的前面。

(5)错位排列

f (n) ? (n ? 1)[ f (n ? 1) ? f (n ? 2)] n ? 1, f (1) ? 0 n ? 2, f (2) ? 1 n ? 3, f (3) ? 2

??

排列、组合及其应用
例6、工作安排问题。
工作1 工作2 工作3 工作4 第1人 工作n

… 12 20 9 11 3 … … 第2人 19 2 5 2 23 … … 第3人 23 34 4 3 21 … … 第4人 2 32 5 66 4 … 每一行表示某人对应每一项工作(列)的工作效 … … … … … … 率,要求每人选择一项工作使得总工作效率最大。 … … … … … … … 第n人 45 1 43 23 12 …

排列、组合及其应用
2、组合
n Cm 表示从m个元素中,任取n个的组合数

m(m ? 1) ? (m ? n ? 1) C ? n(n ? 1) ?1
n m

0 Cn ?1 1 Cn ?n

C

2 n ?1

(n ? 1)n ? ? 1? 2 ??? n 2

排列、组合及其应用
组合的生成方法

readln(m,n); for i:=0 to n do b[i]:=i; 输出; while b[0]=0 do begin j:=n; while b[j]=m-n+j do j:=j-1;

b[j]:=b[j]+1; for i:=j+1 to n do b[i]:=b[i-1]+1; 输出; end;

排列、组合及其应用
组合的应用 例7、密码锁,某单位有m个人,只有n个人到场时才能 打开门,有三个问题: 1、门上装多少锁? 2、每人分配多少个key?

3、如何分配? 设m=4,n=2,则门上装4个锁,每人3个key。
1号锁 2号锁 3号锁 4号锁

第1人 第2人 第3人 第4人

1 1 1

2 2 2

3
3 4 4

3

4

排列、组合及其应用
答案:
n ?1 C 1、门上装 m 锁; n ?1 C 2、每人分配 m ?1 个key; n ? n ?1 3、分配按照 Cm 的全排列

再如:m=6,n=3
1 1 2 3 ★ ★ ★ 2 ★ ★ ★ ★ ★ 3 ★ ★ ★ 4 ★ ★

C62 ? 15 C52 ? 10
5 ★ ★ 6 ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ 7 ★ 8 ★ 9 ★ 10 ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ 11 12 13 14 15

4
5 6



★ ★
★ ★ ★ ★

★ ★


★ ★ ★

★ ★
★ ★

常用数学公式 排列、组合及其应用 数学归纳及推导

Catalan数

数学归纳及推导
例8、平行线线段交点问题 L2 上分别有n,m个点,不在 设有两条平行线 L1, 一直线的任意两点,可连一条直线(线段),且无 三线(或三线以上)相交于一点。 当n,m给出后,有多少个交点?

n?3

m?4

数学归纳及推导
1 结论: f (m, n) ? C C ? m(m ? 1)n(n ? 1) 4 如n=3,m=4 1 f (4,3) ? ? 4 ? 3 ? 3 ? 2 ? 18(个点) 4
2 m 2 n

(A)

对n进行归纳证明
n=1

f (m,1) ? 0

(A)0

数学归纳及推导

n=2

1 m ? 1 ? m ? 2 ? m ? 3 ? ? ? m(m ? 1) 2

1 (A) m(m ? 1) ? 2 ?1 4

数学归纳及推导
设对n=k,(A)成立 1

f (m, k ) ? m(m ? 1)k (k ? 1) 4 对n=k+1

m 增加 k ? 2k ? 3k ? ? ? (m ? 1)k ? (m ? 1)k 2 1 m 1 2 2 m(m ? 1)k (k ? 1) ? (m ? 1)k ? m(m ? 1)( k ? 1)k ? Cm Ck ?1 4 2 4 证毕。

数学归纳及推导
例9、上楼梯问题 有一个n级楼梯(4≤n≤18),某人一步可走1级、2 级、3级,问此人从底到顶有多少种不同的走法? (1)无坏级

f (1) ? 1
f (2) ? 2 , 2 ? 1 ? 1 ? 2 f (3) ? 4 , 3 ? 1 ? 1 ? 1 ? 1 ? 2 ? 2 ? 1 ? 3
一般公式 f (n) ? f (n ? 1) ? f (n ? 2) ? f (n ? 3)

数学归纳及推导
(2)有坏级 将坏的台阶级数记录到一个集合中,然后分别 处理。 for i:=4 to n do if i in s then f:=0 else begin f:=f1+f2+f3; f1:=f2; f2:=f3; f3:=f; end;

数学归纳及推导
例10、2×n的骨牌问题 有2行n列的方格,请你用1×2的骨牌摆放铺满方格, 问:有多少种不同的摆法? n=6 2

f (1) ? 1 f (2) ? 2
一般 f (n) ? f (n ? 1) ? f (n ? 2) ,即Fibnacci数列

常用数学公式 排列、组合及其应用 数学归纳及推导

Catalan数

Catalan数
1、Catalan数的基本形式

(1)递推数列

f (0) ? 1 f (1) ? f (0)(0) ? 1 f (2) ? f (0) f (1) ? f (1) f (0) ? 1 ? 1 ? 2 f (3) ? f (0) f (2) ? f (1) f (1) ? f (2) f (0) ? 2 ? 1 ? 2 ? 5
一般公式: f (n) ? ? f (i ) f (n ? i ? 1)
i ?0 n ?1

Catalan数
(2)组合公式
n C2 f ( n) ? n n ?1

f (0) ? 1
1 C2 f (1) ? ?1 2 2 C4 f (2) ? ?2 3 3 C6 f (3) ? ?5 4

Catalan数
(3)组合公式2
n C n n ?1 2n 证明: C2 ? C ? n 2n n ?1

n n ?1 f ( n) ? C2 ? C n 2n

n n n ?1 n nC2 ? C ? ( n ? 1 ) C ? C n 2n 2n 2n n n ?1 nC2 ? ( n ? 1 ) C n 2n

(2n)! (n ? 1)( 2n)! ? n!n! n(n ? 1)!(n ? 1)!

Catalan数
2、Catalan数的应用

(1)二叉树计数
二叉树有n个结点,问二叉树能组成多少种不同形态?

n ? 1, f (1) ? 1 n ? 2, f (2) ? 2 n ? 3, f (3) ? 5

Catalan数
一般n …… ……

n C2 f (0) f (n ? 1) ? f (1) f (n ? 2) ? ? ? f (n ? 1) f (0) ? n n ?1

Catalan数
(2)A、B排列,有n个A,n个B排列一排,从1开 始计数,任何位置B的个数不超过A的个数。

n ? 1 , AB , f (1) ? 1 n ? 2 , AABB , ABAB , f (2) ? 2 n ? 3 , AAABBB , AABABB , AABBAB , ABAABB , ABABAB , f (3) ? 5

Catalan数
(3)乘法加括号 对于连乘:a0 ? a1 ? a2 ??? an ,加了括号后 可改变它的运算顺序。问:有多少种不同的运 算顺序?

n ? 1 , a0 ? a1 , f (1) ? 1 n ? 2 , a0 ? a1 ? a2 , a0 ? (a1 ? a2 ) , f (2) ? 2 n ? 3 , a0 ? a1 ? a2 ? a3 , a0 ? (a1 ? a2 ) ? a3 , a0 ? a1 ? (a2 ? a3 ) ,

a0 ? (a1 ? a2 ? a3 ) , a0 ? (a1 ? (a2 ? a3 )) , f (3) ? 5

Catalan数
(4)火车出站 ①②③…… 栈 问题:有多少种不同出站顺序?

n ? 1 , (1) , f (1) ? 1 n ? 2 , (1)( 2)

, (2)(1) , f (2) ? 2 n ? 3 , (1)( 2)(3) , (1)(3)( 2) , (2)(1)(3) , (2)(3)(1) , (3)( 2)(1) , f (3) ? 5

Catalan数
(5)凸多边形的三角形划分

……

n+2边的凸多边形有多少种划分三角形的方案?

Catalan数
n ? 1 , f (1) ? 1 n ? 2 , f (2) ? 2

n ? 3 , f (3) ? 5


网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com