错位排列

错位排列 《全错位排列》研究一得 《全错位排列》研究一得 10个人有相应的10个指纹档案，每个指纹档案中某人把手指按在键钮上，并由检测指示灯和检测时的手指键钮。10个人中的某个人把手指按在键钮上若是他的档案，则指示灯出现绿色，否则红色。现在这10个人把手指按在10个指纹档案的键钮上去检测，并且两个人不能在同一个档案上去检测。如果指示灯全部出现红色，这样的情况有多少种, 理科实验班 黄回銮 徐博强 刘益佳 指导教师 史立莉 一,问题的引入 课余,我们看排列组合问题时,常遇到受限元素,受限位置的简单问题.如5个学生站成一排,甲不站在排头,乙不站在排尾有多少种不同排法,或上午5节课,数学,体育,政治,语文,化学.体育不排在第一节,数学不排在最后一节,有多少种不同排法.对这类问题的解决,我们已很熟练. 甲,乙或体育,数学是受限元素,排头,排尾或第一节,第五节是受限位置,用排除法较简明,只须重视排除时重复排除就可以了. 如图: 不考虑受限元素,受限位置时,5个人站成一排有P55种不同排法.要除去甲在排头的P44种不同排法,此时已含乙站在排尾的P33种排法,然后再排除乙站在排尾的P44种不同排法.再加上重复排除的P33种不同排法,故可得出结论: 不同的排法有 P55-2P44+P33=78种 二,课题的提出 5个元素有2个元素受限,有2个位置受限,我们考虑若将此题深化,若5个元素都受限,都分别受限在不同的位置上.即5个编号分别为1,2,3,4,5的学生排成一排,1不站在1号位,2不站在2号位… 5不站在5号位,即每人均不站在与其编号相对应的位置上,我们称符合这样限制条件的排列为全错位排列,那这样的全错位排列有多少种 如果有n个受限元素,又该如何解呢 我们用排除法去解,很难得出正确结论,重复的情况很复杂,很难理出头绪,我们三人决心研究《全错位排列》排列数计算问题.带着这个问题我们请教了指导老师史立莉. 三,课题研究 史老师指导我们学习排列,组合数学归纳法及数列有关知识,鼓励我们大胆探究.课余我们在一块探讨研究,用不完全归纳法试图找出规律,经推理演绎,初步得出一个不成熟的结论,供大家探讨,以期抛砖引玉. 四,构建命题 命题:设n个编号为1,2,3,… i… j…n的不同元素a1,a2,a3…ai…aj…an, 站在一排,且每个元素均不站在与其编号相对应的位置,这样的全错位排列数为Tn . 则 Tn= (n-1) ( Tn-1+Tn-2) 说明:Tn-1, Tn-2 分别示n-1个或n-2个不同元素全错位排列数. 证明:在n个不同元素中任取一个元素ai其不站在与其编号相对应的i 位,必站在剩下n-1 个位置上,ai有n-1 种站法. 对ai每一种站法,如ai站在 j位,对应j位的元素aj的站位总有两种情况: 第一种情况: 如图:位置: 1 2 3 … i … j … n aj ai ai站在 j 位,aj站在 i 位,元素ai,aj站位已定,还剩 n-2个元素,每个元素均有一个不能站的位置,它们的站位问题就转化为n-2 个元素全错位排列数,应有 Tn-2种. 第二种情况: 如图:位置: 1 2 3 … i … j … n ai ai仍站在j位,aj不能站在 i位(第一种情况aj已站 i 位),此时只有ai一个元素站位确定除ai外,还有个 n-1元素,每个元素均有一个不能站的位置,问题就转化为n-1个元素全错位排列,有Tn-1种.由乘法原理和加法原理可得: Tn=(n-1)(Tn-1+Tn-2) (n?3) 这样命题得证. 有这样的递推公式就很容易解决上面提出的问题. 显然T1=0 两个不同元素全错位排列只有一种排法 T2=1 叁个不同元素全错位排列有二种不同排法 T3=(3-1)(1+0)=2 四个不同元素全错位排列有T4=(4-1)(2+1)=9 (种) (写出九种站位情况,只写元素下标编 号:2143,2341,2413,3142,3412,3421,4123,4312,4321). 五个不同元素全错位排列有 T5=(5-1)(T4+T3)=4(9+2)=44 (种) 依此递推我们可解决n个不同元素均不站在与其编号相对应的位置上全错位排列数这个问题. 五,研究的意义 "把复杂的问题弄简单了——贡献".在数学领域内有很多复杂问题,很难一次性建模,解模,这就要切块,细化,分类,分层解决.就象有些定理的证明往往通过引理1,2……进行铺垫,分解,使原定理变的简单可证.我们推出求n个元素的全错位排列数的一个递推公式,就将n个元素全错位排列数转化为求n-1,n-2个元素全错位排列数,而初始数T1,T2,T3为已知,这样就解决了求n个元素全错位排列数的问题.掌握这种数学思想,思维方式,对于我们这些中学生十分必要,有利于我们学会学习,有利于我们将来在激烈竞争中多一些生存的本领. 课本,大纲历来是教育者,受教育者的依据.尤其是数学学科,中学生中不少感到高深莫测难以驾驭,我们此举也是向中学生朋友们呼吁