1、错位排列 10 10人的帽子存放后,随机取走。若没有任何人拿人的帽子存放后,随机取走。若没有任何人拿到自己的帽子,有多少种取法?到自己的帽子,有多少种取法?问题的引出问题的引出 V-8 V-8发动机的发动机的8 8个火花塞清洗后放回。若没有任何个火花塞清洗后放回。若没有任何一个火花塞放回原气缸,有多少种放法?一个火花塞放回原气缸,有多少种放法?写给写给n n个人的个人的n n封信,装进封信,装进n n个写好地址的信封内。个写好地址的信封内。若没有任何一封信能与地址匹配,有多少种放法?若没有任何一封信能与地址匹配,有多少种放法?8 8个非攻击车放在国际象棋棋盘上,规定对角线上个非攻击车放在国际象
2、棋棋盘上,规定对角线上不能放子。有多少种放法?不能放子。有多少种放法?三三、数学化描述、数学化描述错位排错位排列列 定义定义 错位排列可以错位排列可以用非攻击车的用非攻击车的位置表示位置表示 X X X X X X X X 2121 231231,312312 21432143,23412341,24132413 31423142,34123412,34213421 41234123,43124312,43214321 定理定理 证明:证明:(应用容斥原理)应用容斥原理)四四、性质、性质 性质性质1 1 性质性质3 3 性质性质2 2 性质性质4 4 例例1 1 10 10 个人在舞会后随机取
3、走他们寄存的帽个人在舞会后随机取走他们寄存的帽子。求没有任何一个人拿对帽子的概率。子。求没有任何一个人拿对帽子的概率。满足如下各种递推关系:满足如下各种递推关系:例例2 2 舞会上有舞会上有1010男男1010女参加。女参加。第一支舞曲:女士有多少种方法选择男舞伴?第一支舞曲:女士有多少种方法选择男舞伴?第二支舞曲:如果要求必须换舞伴,女士有多少第二支舞曲:如果要求必须换舞伴,女士有多少种方法选择男舞伴?种方法选择男舞伴?例例3 3 舞会有舞会有1010男男1010女戴帽子,结束时随机返还。女戴帽子,结束时随机返还。(1 1)求男士得到男帽,女士得到女帽的概率;)求男士得到男帽,女士得到女帽的
4、概率;(2 2)男士得到男帽,女士得到女帽的概率且每个)男士得到男帽,女士得到女帽的概率且每个人都没有得到自己的帽子的概率。人都没有得到自己的帽子的概率。解:解:随机取走帽子的方法随机取走帽子的方法:(2n):(2n)!A:A:表示事件表示事件“男士得男帽、女士得女帽男士得男帽、女士得女帽”B:B:表示事件表示事件“每人都没有得到自己的帽子:每人都没有得到自己的帽子:例例2 2 舞会上有舞会上有1010男男1010女参加。女参加。第一支舞曲:女士有多少种方法选择男舞伴?第一支舞曲:女士有多少种方法选择男舞伴?第二支舞曲:如果要求必须换舞伴,女士有多少第二支舞曲:如果要求必须换舞伴,女士有多少种方法选择男舞伴?种方法选择男舞伴?例例3 3 舞会有舞会有1010男男1010女戴帽子,结束时随机返还。女戴帽子,结束时随机返还。(1 1)求男士得到男帽,女士得到女帽的概率;)求男士得到男帽,女士得到女帽的概率;(2 2)男士得到男帽,女士得到女帽的概率且每个)男士得到男帽,女士得到女帽的概率且每个人都没有得到自己的帽子的概率。人都没有得到自己的帽子的概率。解:解:随机取走帽子的方法随机取走帽子的方法:(2n):(2n)!A:A:表示事件表示事件“男士得男帽、女士得女帽男士得男帽、女士得女帽”B:B:表示事件表示事件“每人都没有得到自己的帽子:每人都没有得到自己的帽子: