初数方圆
g季’45
错排问题的递推求解
200040
上海市五四中学朱常中
一、错排问题
现有五件球衣分属五个运动员,现问五个运动员都不穿自己的球衣,而穿其它球员的球
衣,这样的穿法有几种?
这就是5个元素的错排问题.
就一般而言,有几个不同的元素,它们一一对应于几个位置,如果这九个元素都不排在自身对应的位置上,这种排列的方法称为几个元素的一个错排.现要计算这种错排的个数.
大数学家欧拉曾用容斥原理求出了n个元素的错排个数为:
眈一,z:[,一矗十六一击+……+£茅]
这是运用容斥原理解决问题的一个典范.现从另一个角度出发,运用错排问题自身的递推规律,求错排问题的解.
二、错排问题的递推规律
设有72个不同的元素al,口2,口3……口。,并设元素口i其对应的位置是(i)(i一1,2,3,……竹),
并将忌个元素的错排的个数计为晚(忌一1,2,
……以),行个元素的一个错排可分成二个步骤:
1、先决定元素口1的排法
(1)
(2)
(3)
……
(,z)
由于口1不能排在与其对应的位置(1)上,但可以排在(2)至(咒)的任何一个位置上,故共
有咒一1种排法.
2、元素口1排定后,其他元素的排法
对于元素口1排在(2)至(行)位置上的每种错排法,其错排数都相同.因此,不妨着重考察元素口1位于位置(2)时.其他元素的排法,对于这种情况又可以分两类:
(1)元素n2在位置(1)上,此时,元素口i不能排在位置(i)上,(i一3,4……竹)因此其排法数
为D。一2.
(2)元素口2不排在位置(1)上,此时,口2不排在位置(1)上,元素口i不排在位置(i)上(i一3,4……n),而这种情况实际上恰恰就是胆一1个元素的错排(我们只要把位置(1)看作是元素n2的对应位置),其排法数为D。.一1.
万
方数据根据加法原理可知,在元素口1排定的情况下,其他元素的排法数为:D。+2+D。一1
综合以上二个步骤,根据乘法原理得到错排问题的递推规律:D。一(咒一1)(D—I+
D。~2)(咒≥2)
另外根据错排的定义显然有D1=O,D2=l,因此,根据以上的递推规律,已经可以求出任意多个不同元素的错排问题的解,但需逐个推算,才能得到问题的解.
三、用错排问题的的递推规律求咒个元素错排问题的解
下面根据D。一(行一1)(D。一l+D。一2)求D。关于行的表达式.
由D。一(以~1)(D。一1+D。一2)
故西:=导三舌‰一一1于是又有
可得D。一行D—l
一一[D。一l一(n—1)D。一2],
D。一1一(n一1)D。一2.
1
D。一2一(n一2)D。一3
i
D3—3D2.
1
D2—2Dl
而D2—2D1—1
将以上咒一1个式子相乘得
D。一,lD。一l一(一1)”一2一(一1)n
设眈=忌!n(是一1,2……n)
便有竹!L一以(行一1)!L—l一(一1)n
故L—L—l=£暑旦于是有
竹!
k,一%=杀崭
L,z一1,!
i
,f2一n一者
T1一O
将以上几个式子相加便可得:
T。=刍一寺+..…+警
而B一以zL—n
z[云一击+……+与茅]
这就是咒个不同元素错排问题的解.
1D84,=5Dl9, 解: 这是 5个 元素 的错位 排列 问题 , 设这样 的五位 数 的个数 为D5 由递推 公式( ).4得 D1,=1D3,=9D5( :0D2,=2D4,=5—1...
递推求解问题2 用来 递推求解用来 递推求解隐藏>> ACM程序设计 程序设计 ...递归式:d[n]= (n-1)*( d[n-1] + d[n-2]) 这就是著名的错排公式...
递推问题的求解方法_专业资料。递推是计算机科学和数学中很重要的工具。阐述了求解递推问题的一般方法,通过实例详细介绍了具体的求解过程,并给出了相应的程序。...
ACM程序设计第三讲 递推求解 先来看一个例题: ? 有5人坐在一起,当问第5...说明2:“Z”的两条射线规定为平行的 2013-11-29 19 错排问题编号为 1,2 ...
巧用递推公式求解四类计数问题_理学_高等教育_教育专区。献给热爱此类问题的人...设 n”素 的错 位排列数为 ,则数列{} 4元 满足c lfn时,A一1C×+ e,...
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入阅读会员!获取下载券 递推法解排列组合问题 隐藏>> 递推法解...
递推求解问题2 36页 2财富值 第三讲 递推求解 15页 免费 6求解递推关系 ...递归式:d[n]= (n-1)*( d[n-1] + d[n-2]) 这就是著名的错排公式...
201303版_04递推求解_工学_高等教育_教育专区。...2014-7-1 11 例:(2050)折线分割平面问题描述: ...( d[n-1] + d[n-2]) 这就是著名的错排...
5 三.求出这一数列的递推式: 设对于 n 个数的错排方法数为 a n 现对... 显然,该问题可分步解决: r S1 :考虑哪 r 个元素是错排: m1 = Cn ? ...
2011-9-16 11 2050) 例:(2050)折线分割平面问题...思考:如何用递推解决? 结论—— 结论 F(n)=F(n...( d[n-1] + d[n-2]) 这就是著名的错排...
热门文档