tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 数学 >>

从一道高考题说起


2000 年第 11 期           中学数学月刊                39  

从 一道 高考 题说 起
学生   刘亮环   指导老师   姚湄玲   ( 广州市十六中   510030)    1993 年全国普通高考数学卷 中有这样 一道题: 同室四人各写一张贺年卡, 先集中起来 , 然后每人从中拿一张别人送出的贺年卡 ,

则 四张贺年卡不同的分配方法有: (A ) 6 种 (B ) 9 种 (C ) 11 种 (D ) 23 种 这道题用穷举法不难得出答案 B. 现在要问: 当人数增大到难于用穷举法 时, 能否用其它方法解答呢? 答案是肯定的. 我们先将这类问题一般化: 问题: 将 a 1, a 2, a 3, … , a n , 共 n 个元素排 成一行, 要求元素 a i 不在第 i ( i ∈ N 且 1 ≤ i ≤ n ) 位上 , 问共有多少种排法? 解法 1  设这样 的排法 共有 f ( n ) 种, 则: ( 1) 显然 f ( 1) = 0; (2) 当 n ≥ 2 时 , 先将这 n 个元素任意排 成一行 , 共有 P n n 种排法, 再减去以下不合题 意的排法: 1) 恰有 1 个元素的位置不合题意, 从 n 个元素中任取一个元素 a k 排在第 k 位上 , 有 C1 1 个元素按原题条 n 种取法; 再将其余 n 件排列 ( 即这 n - 1 个元素中任一个元素 a i 不在第 i 位上 ) , 依题设有 f ( n - 1) 种排法, 故这种情况有 C 1 nf ( n 1) 种 . 2) 恰有 2 个元素 的位置 不合 题意 . 同 2 1) , 可知有 C nf ( n - 2) 种. …… n - 1 ) 恰有 n - 1 个元素的位置不合题 意, 有 C n ) 恰有 n 个元素的位置不合题意, 显然 有1种 . ∴n ≥ 2 时 , f (n ) = P n n C -n 1f ( n - 1 ) C2 n f (n 2) 1 …C nn f ( 1) - 1. n- 1 n

解法 2   设 A i 表示这样的集合: 将 a 1, a 2, a 3, …, a n 这 n 个元素排成一行, 并且元素
a i 排在第 i 位上的所有排列 . ?A i ? 表示集合 A i 的元素个数 . A i1 ∩ A i2 ∩ A i3 ∩ … ∩ ∑ ?
n

A ik ? 表示从 A 1~ A

中任取 k 个集合相交得

到的所有交集的元素个数总和 . 如 ∑ ?A i1 ∩ A i2 ? = ? A 1 ∩ A 2 ?+ ? A 1 + A 3 ?+ … + ? A1 ∩ A n ? + ?A 2 ∩ A 3 ? + ?A 2 ∩ A 4 ? + … + ? A 2 ∩A n ?+ ? A 3 ∩ A 4 ?+ … + … + ? A n∩ A n ?, 则有:
1 n- 1 ∑ ?A i1 ? = CnP n- 1 , 2 n- 2 ∑ ?A i1 ∩ A i2? = C nP n- 2, …… 1

∑ ?A i1 ∩ A i2 ∩ A i3 ∩ … ∩ A i (n1 1 C nn P1 ,

1)

?=

∑ ?A i1 ∩A i2 ∩ A i3 ∩ … ∩ A in? = 1 =
C P ( 为方便约定 P 0 0 = 1). 则依容斥定理 , 所求的排列方法种数为:
f ( n) = P n - ? A 1 ∪A 2 ∪ A 3 ∪ … ∪A n ?
n n n 0 0

= Pn n -

( ∑ ?A i1? -

A i1 ∩ A i2? + ∑ ?

k+ 1 ∑ ?A i1 ∩ A i2 ∩ A i3? - … + ( - 1)

∑ ?A i1 ∩ A i2 ∩ A i3 ∩ … ∩ A ik ? + … +
(- 1) n ∑ ?A i1 ∩ A i2 ∩ A i3 ∩ … ∩ A i (n - 1) ? + (- 1) n+ 1 ? A i1 ∩ A i2 ∩ A i3 ∩ … ∩ A in ?)
n= Pn C1 n nP n 1 1 n+ C2 n P n2 2 n- C3 n P n3 3

+ …+

f ( 1) 种.

(- 1) P

k

n- k n- k n

… + (- 1)

n- 1

C

n- 1 n

P + (- 1) n ?

1 1

0 i ( - 1 ) iC in P nCn n P0 = n- i . ∑ i= 0

上面两种方法最后结果的形式不同 , 但 实质却是一样的 . 显然当 n 较大时 , 解法 1 要 比穷举法好, 而解法 2 又要比解法 1 好. 容易 算出 f (4) = 9, f (5) = 44, f (6) = 265. 上面的解告诉我们, 解法 1 所得的递推 式可化为解法 2 的通项式, 这是题外话了 .

综上得排法总数的递推式为: f ( n ) = 0,    (n = 1) Pn n C1 nf ( n 1) - C 2 nf ( n 2)   … - C
nn 1

f ( 1) - 1.   ( n ≥ 2)


推荐相关:

高考题

2014年高考理科数学北京... 1/2 相关文档推荐 从一道高考题谈起 暂无评价 2页 ¥3.00 高考题 暂无评价 3页 免费 高考题 暂无评价 19页 1下载券 说点又...


高考题

从一道高考题谈起 暂无评价 3页 2.00元 高考题 2页 免费 高考题 暂无评价 18页 2财富值 由一道高考题说起 暂无评价 2页 1.00元 高考题 暂无评价 4页...


高考题

从一道高考题谈起 暂无评价 3页 2.00元 高考题 2页 免费 高考题 暂无评价 18页 2财富值 由一道高考题说起 暂无评价 2页 1.00元 高考题 暂无评价 4页...


高考题

2014年高考理科数学北京... 1/2 相关文档推荐 从一道高考题谈起 暂无评价 2页 ¥3.00 高考题 暂无评价 3页 免费 高考题 暂无评价 19页 1下载券 说点又...


高考题

从一道高考题谈起 暂无评价 3页 2.00元 高考题 2页 免费 高考题 暂无评价 18页 2财富值 由一道高考题说起 暂无评价 2页 1.00元 高考题 暂无评价 4页...


高考题

从一道高考题谈起 暂无评价 3页 2.00元 高考题 2页 免费 高考题 暂无评价 18页 2财富值 由一道高考题说起 暂无评价 2页 1.00元 高考题 暂无评价 4页...


高考题

从一道高考题谈起 暂无评价 3页 2.00元 高考题 2页 免费 高考题 暂无评价 18页 2财富值 由一道高考题说起 暂无评价 2页 1.00元 高考题 暂无评价 4页...


高考题

从一道高考题谈起 暂无评价 3页 2.00元 高考题 2页 免费 高考题 暂无评价 18页 2财富值 由一道高考题说起 暂无评价 2页 1.00元 高考题 暂无评价 4页...


高考题

从一道高考题谈起 暂无评价 3页 2.00元 高考题 2页 免费 高考题 暂无评价 18页 2财富值 由一道高考题说起 暂无评价 2页 1.00元 高考题 暂无评价 4页...


高考题

从一道高考题谈起 暂无评价 3页 2.00元 高考题 2页 免费 高考题 暂无评价 18页 2财富值 由一道高考题说起 暂无评价 2页 1.00元 高考题 暂无评价 4页...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com