文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 错排问题的递推求解
侵权投诉

错排问题的递推求解

初数方圆

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[云一击+……+与茅]

这就是咒个不同元素错排问题的解.

第1页

你可能喜欢

热门文档

相关文档

  • 解排列组合题的一个递推公式及其应用

    1D84,=5Dl9, 解: 这是 5个 元素 的错位 排列 问题 , 设这样 的五位 数 的个数 为D5 由递推 公式( ).4得 D1,=1D3,=9D5( :0D2,=2D4,=5—1...

  • 递推求解问题2

    递推求解问题2 用来 递推求解用来 递推求解隐藏>> ACM程序设计 程序设计 ...递归式:d[n]= (n-1)*( d[n-1] + d[n-2]) 这就是著名的错排公式...

  • 【论文】递推问题的求解方法

    递推问题的求解方法_专业资料。递推是计算机科学和数学中很重要的工具。阐述了求解递推问题的一般方法,通过实例详细介绍了具体的求解过程,并给出了相应的程序。...

  • (lecture_03)递推求解090429

    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递推求解

    201303版_04递推求解_工学_高等教育_教育专区。...2014-7-1 11 例:(2050)折线分割平面问题描述: ...( d[n-1] + d[n-2]) 这就是著名的错排...

  • E09.关于错排问题的思考与讨论

    5 三.求出这一数列的递推式: 设对于 n 个数的错排方法数为 a n 现对... 显然,该问题可分步解决: r S1 :考虑哪 r 个元素是错排: m1 = Cn ? ...

  • (HDUACM2010版_03)递推求解

    2011-9-16 11 2050) 例:(2050)折线分割平面问题...思考:如何用递推解决? 结论—— 结论 F(n)=F(n...( d[n-1] + d[n-2]) 这就是著名的错排...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email