满射观点下的排列组合问题第3稿_「金点文库网」分享知识创造价值

许昌学院图书馆-临别赠言

《高中数学研究性学习案例》
映射观点下的一些组合问题及其计数公式

王跃进

用映射的观点研究高考中的一些排列组合问题，将它们统一
为映射和满射问题并进行推广，得出关于满射个数的计数公式等
结果，可以帮助我们用较高的理论观点统一看待和理解这些问题
的本质及其一般解法．
一、映射
例1（06年高考湖南理科卷）某外商计划在4个候选城市投
资3个不同的项目,且在同一个城市投资的项目不超过2个,则该
外商不同的投资方案有种．
例2（07年高考陕西文科卷）安排3名教师去4所学校任教， 每校至多2人，则不同的分配方案共有种．
评析用映射的观点看，设X为 3个不同项目（3名教师）的
集合，Y为4个候选城市（4所学校）的集合，则例1、例2可统
一为：从X向Y作映射，不能将X中3个元素全映射到Y中同一
个元素上的映射有多少个？因为从X到Y的映射共有
4
3
个，其中3
1
个元素全映射到Y中同一个元素上的映射有 C
4
= 4个，故例1、例
2的解均为
4
3
－4=6 0种．用映射的观点可将两例推广为：
定理1设集合X为
n
元集合，集合Y为
m
元集合，从X向Y

作映射，不能将X中
n
个元素全映射到 Y中同一个元素上，则这样
1
的映射共有
m
n
C
m
=
m
n
m
个．
二、单射
例（08年上海中等职业学生高考题第4题）某校设有6个不
同的兴趣小组，每名学生限报一个组，现有3名学生报名，假设
每名学生报每个组的可能性相同，则任何两名学生不报同一个组
的概率为
3
33
P
6
3
P
C
6
C
6
6(A)
6
； (B)
6
； (C)
3
； (D)
3
.
3
6
3
6
解问题为从3元集合到6元集合的单射有多少种。满足条件
的报名方法有
C3!
=
P
3
6
3
而6
种，3名同学的报名方法共有
6
3
种（样
P
6
3
5
本空间中的样本点总数）。故所求概率为
3
=。选C。
9
6
说明：排列组合，概率，高中课程标准先讲概率再讲组合，
目的？
三、满射
例3 (04年高考全国文科卷) 将4名教师分配到3所中学任教，
每所中学至少一名教师，则不同的分配方案共有种．
解由题意知，3所中学必恰有一所分到2名教师，另外2所
各分1名教师，用“捆绑法”得所求分配方案共有
C
4
3!
=36种．
评析用映射的观点看，例3 实质上是从4元集合到3元集合
的满射个数问题．利用容斥原理可得关于满射个数的一般计数公
式：
2

n
,
m
N

，定理2 设集合X为
n
元集合，集合Y为
m
元集合，
nm
，则由X 到Y的满射共有
k
(mk)
n

f(n,m)
=

(1)
k
C
m
k0
m1
n1n2nm1
=
mC
m
(m1)C
m
(m2)
－„
(1)
m1
C
m

个．
,b
m
}
，
Ω
为X到Y的所有映射构成的集合，证明设 Y=
{b
1
,b
2
，
A
i
{
f

f：XY
,
b
i

f(X)
}
,
i1,2,,m
，即
A
i
为使
b
i
没有原
象的
Ω
中所有映射
f
构成的集合，则
n
|

|m
n
；
|A
i
|(m1)
，
1im
；
|A
i
A
j
|(m2)
n
，
1ijm
；„，
一般地，有

|A
i
1
A
i
2
A
i
k
|(m k)
n
，
1i
1
i
2
i
km
，
k1,2,,m
．
则
Ω
中不是满射的映射共有
|A
1
A
2
A
m
|
个，根据容斥原
理，所求满射个数
f(n,m)
为

f(n ,m)
=
|Ω||A
1
A
2
A
m
|

=
m

|A
i
|
n
i 1
m
1ijm

|AA
ij
|
„
k
(1)
+
1i
1
i
2


i
k
m

|A
i
1
A
i
2
A
i
k
|

+ „ +
|A
1
A
2
A
m
|

=
m
n
C(m1)C(m2)
n
1
m
n2
m
n

k
(mk)
－„
(1 )
k
C
m
m1
(1)
m1
C
m

kkn
(1)C(mk)
m
=

． k0
m1
例4（08年湖北理6题）将5名志愿者分配到3个不同的奥
运场馆参加接待工作，每个场馆至少分配一名志愿者的方案种数
为
A.540 B.300 C.180 D.150
解：为从5元集合到3元集合的满射个数问题．由定理2得所
求分法种数为
f(5, 3)
=

(1)
k
C
3
k
(3k) n

k0
2
25
515
C1
3C2
=+
3

3
=150．
选D。用“捆绑法”同样可得所求结果为
3
C
5
3 ！
1
22
C
5
C
3
3 ！
=60+90=150
2
例5 (06年高考全国文科卷) 5名志愿者分到3所学校支教，
要求每所学校至少有1名志愿者，则不同的分法共有种.
解为从5元集合到3元集合的满射个数问题．由定理2得所
求分法种数为
f(5, 3)
=

(1)
k
C
3
k
(3k) n

k0
2

=
3
5
C2
+
C1

1
3
5
2
3
5
=150．

例 6（0７年高考宁夏等理科卷）某校安排5个班到4个工厂
进行社会实践,每个班去一个工厂,每个工厂至少安排一个班,不
同的安排方法共有种.
解问题为求从5元集合到4元集合的满射个数问题．由定理
2得所求安排方法共有
f(5,4)
=

( 1)
k
C
4
k
(4k)
n
=240种．（若用“ 捆
k0
3
绑法”同样可得结果为
C
5
2
4! =240）
例7 (07年高考湖北文科卷）将5本不同的书全发给4名同学,
每名同学至少有一本书的概率是．
解满足条件的分书方法与例4完全相同，都是从5元集合到
4元集合的满射问题，故分书方法也是240种；因为从5元集合到
4元集合的映射共有
4
5
24015
种，故所求概率为
5

．
64
4
例8（06年高考重庆理科卷）将5名实习教师分配到高一年
级的３个班实习，每班至少１名，最多２名，则不同的分配方案 有种.
解问题为：从5元（5名教师）集合X向3元（３个班）集
合Y作满射，不能将X中3个元素映射到Y中同一个元素上的满
射有多少个？同例4得，从5元集合到3元集合的满射共有150
个，其中X中有3个元素映射到Y中同一个元素上的满射有

C

3!
=60个，故所求方案有150-60=90种.
221
注：用“捆绑法”也可得结果为
C
5
C
3
C
1
C
3
=90．
3
5
1

三、一个元素入盒问题的推广
例9（95年全国高考题）将4个不同的小球放入编号为1，2 ，
3，4的4个盒子中，则恰有1个空盒的放法共有种．
1
C
解从4个盒子中选出1个作为空盒，有
4
种方法；对选定的
1个空盒，将4个不同的小球放入其余的3个盒子且每个盒子都不
空，为从4元集合到3元集合的满射问题，同例3，这样的满射共 有
f(4,3)
=36个．由乘法原理即得所求放球方法共有
1
C4

f(4,3)
=144种．
评析例9也可看成是恰有一个元素没有原象的映射问题．用
3
2
C
“捆绑法”也可得解为
4
C 4

3！=144，但是在一般情形下如何解？
利用定理2和乘法原理可得例9 在一般情形下的推广与计数公式：
定理3 将
n
个不同的小球放入编号为1，2，„ ，
m
的
m
个盒
子中，则恰有
r
个盒子
(0 rm)
是空盒的放球方法共有
rr
C
m

f(n,m r)C
m
mr1

k0
kn
(1)
k
C
m
(mrk)
r

种．
例10 从6元集合X向5元集合Y作映射，Y中恰有2个元
素没有原象的映射有多少个？
解由定理3，所求映射共有

Cf(6,3)
=
C
2
5
2
5
kk6
(1)C(3k)


3
2
k0
=5400
个．
参考文献
[1]李少辅,王跃进等.组合分析的原理方法
南大学出版社,1994,32-47.

技巧[M].开封:河

平凡网名-罗恩老师的奇迹教育

庄心妍好听的歌-雪地里的小画家教学设计

致运动员加油稿-初中英语教师述职

胎教歌曲大全-家长寄语大全

哈尔滨师范大学分数线-暑期实践个人总结

中学生假期打工-温柔

拔丝香蕉怎么做-科幻小说排行榜完本

这件事真让我难忘-吃掉那只青蛙