错位排列.ppt

《错位排列.ppt》由会员分享，可在线阅读，更多相关《错位排列.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 错位排列问题错位排列问题一、一、预备知识预备知识 1.1.一个子集的情形一个子集的情形 用于计算不具备某一性质用于计算不具备某一性质P P的集合的大小的集合的大小2 2、两个子集、两个子集多除少补多除少补证明：证明：+11-(0+0)+0=+1 思路：逐个挑选元思路：逐个挑选元素放入左右两边素放入左右两边证明：证明：+01-(1+0)+0=+0 思路：逐个挑选元思路：逐个挑选元素放入左右两边素放入左右两边证明：证明：+01-(0+1)+0=0 思路：逐个挑选元思路：逐个挑选元素放入左右两边素放入左右两边证明：证明：+01-(1+1)+1=+0 思路：逐个挑选元思路：逐个挑选元素放入左右两边素

2、放入左右两边3 3、三个子集、三个子集多除少补多除少补4 4、一般情况、一般情况定理定理1 1（容斥原理）（容斥原理）对所有对所有1-1-组合组合求和求和对所有对所有2-2-组合组合求和求和对所有对所有3-3-组合组合求和求和推论推论2 2（容斥原理（容斥原理2 2）1010人的帽子存放后，随机取走。若没有任何人拿人的帽子存放后，随机取走。若没有任何人拿到自己的帽子，有多少种取法？到自己的帽子，有多少种取法？二二、问题的引出、问题的引出 V-8V-8发动机的发动机的8 8个火花塞清洗后放回。若没有任何个火花塞清洗后放回。若没有任何一个火花塞放回原气缸，有多少种放法？一个火花塞放回原气缸，有多少

3、种放法？写给写给n n个人的个人的n n封信，装进封信，装进n n个写好地址的信封内。个写好地址的信封内。若没有任何一封信能与地址匹配，有多少种放法？若没有任何一封信能与地址匹配，有多少种放法？8 8个非攻击车放在国际象棋棋盘上，规定对角线上个非攻击车放在国际象棋棋盘上，规定对角线上不能放子。有多少种放法？不能放子。有多少种放法？三三、数学化描述、数学化描述错位排错位排列列 定义定义 错位排列可以错位排列可以用非攻击车的用非攻击车的位置表示位置表示 X X X X X X X X 2121 231231，312312 21432143，23412341，24132413 31423142，34

4、123412，34213421 41234123，43124312，43214321 定理定理 1 1 证明：证明：(应用容斥原理）应用容斥原理）四四、性质、性质 性质性质1 1 性质性质3 3 性质性质2 2 性质性质4 4 例例1 1 10 10 个人在舞会后随机取走他们寄存的帽个人在舞会后随机取走他们寄存的帽子。求没有任何一个人拿对帽子的概率。子。求没有任何一个人拿对帽子的概率。满足如下各种递推关系：满足如下各种递推关系：例例2 2 舞会上有舞会上有1010男男1010女参加。女参加。第一支舞曲：女士有多少种方法选择男舞伴？第一支舞曲：女士有多少种方法选择男舞伴？第二支舞曲：如果要求必须

5、换舞伴，女士有多少第二支舞曲：如果要求必须换舞伴，女士有多少种方法选择男舞伴？种方法选择男舞伴？例例3 3 舞会有舞会有1010男男1010女戴帽子，结束时随机返还。女戴帽子，结束时随机返还。（1 1）求男士得到男帽，女士得到女帽的概率；）求男士得到男帽，女士得到女帽的概率；（2 2）男士得到男帽，女士得到女帽的概率且每个）男士得到男帽，女士得到女帽的概率且每个人都没有得到自己的帽子的概率。人都没有得到自己的帽子的概率。解：解：随机取走帽子的方法随机取走帽子的方法:(2n):(2n)！A:A:表示事件表示事件“男士得男帽、女士得女帽男士得男帽、女士得女帽”B:B:表示事件表示事件“每人都没有得

6、到自己的帽子：每人都没有得到自己的帽子：例例2 2 舞会上有舞会上有1010男男1010女参加。女参加。第一支舞曲：女士有多少种方法选择男舞伴？第一支舞曲：女士有多少种方法选择男舞伴？第二支舞曲：如果要求必须换舞伴，女士有多少第二支舞曲：如果要求必须换舞伴，女士有多少种方法选择男舞伴？种方法选择男舞伴？例例3 3 舞会有舞会有1010男男1010女戴帽子，结束时随机返还。女戴帽子，结束时随机返还。（1 1）求男士得到男帽，女士得到女帽的概率；）求男士得到男帽，女士得到女帽的概率；（2 2）男士得到男帽，女士得到女帽的概率且每个）男士得到男帽，女士得到女帽的概率且每个人都没有得到自己的帽子的概率。人都没有得到自己的帽子的概率。解：解：随机取走帽子的方法随机取走帽子的方法:(2n):(2n)！A:A:表示事件表示事件“男士得男帽、女士得女帽男士得男帽、女士得女帽”B:B:表示事件表示事件“每人都没有得到自己的帽子：每人都没有得到自己的帽子：