魔方吧·中文魔方俱乐部

标题: 很有意思的一道題目 [打印本页]

作者: 录 时间: 2009-5-19 19:01:55 标题: 很有意思的一道題目

先看這樣一道題：七個人排成一排，甲不站在中間，乙不站在排尾﹐問有多少種不同的排法？這題是高中排列組合書上的一道練習題，不是很難
然後再看這樣一道題：七個人去七個個地方旅遊，甲不去a地，乙不去b地，丙不去c地，丁不去d地，問有多少種不同的旅遊方案？
看完這兩題忍不住想把它推廣﹐七個人換成n個人(n>8)，四個制限換成五個制限，六個限制...n個限制，能否找到它的通項？

作者: juventus66 时间: 2009-5-19 19:15:25

1. 七個人排成一排，甲不站在中間，乙不站在排尾﹐問有多少種不同的排法？ (2400种)

2, 七個人去七個個地方旅遊，甲不去a地，乙不去b地，丙不去c地，丁不去d地，問有多少種不同的旅遊方案？ (2790种)

[ 本帖最后由 juventus66 于 2009-5-19 19:40 编辑 ]

作者: 铯_猪哥恐鸣 时间: 2009-5-19 19:24:27

设a[i,j]表示一共有j个人，其中有i种限制。不妨将有限制的地点放在第一个。考虑第一个地点谁去，根据加法、乘法原理有：
a[i,j]=(j-i)*a[i-1,j-1]+(i-1)*a[i-2,j-1]
a[0,j]=j!
只能给出递推式。。。具体表达式还得等待高手来求。。。

作者: 无限正义 时间: 2009-5-19 20:21:03

两种解法。一种是原始的叠加，另一种是排除法

作者: 录 时间: 2009-5-19 20:52:45

呃..我也是想到了遞推關係..不過還沒具體算出來..只是七人旅遊的一二三四個限制的算出來而已..

作者: kexin_xiao 时间: 2009-5-19 21:21:48

数学专业的来给解答吧

录最近魔方练的如何？别天天练算术把魔方荒废了啊

作者: 录 时间: 2009-5-19 21:59:54

已經廢了..唉..沒時間練啊

作者: 斯芬克斯之谜 时间: 2009-5-22 19:54:12

作者: 达达达 时间: 2009-5-22 19:55:08

哈哈排列组合问题看看

作者: 达达达 时间: 2009-5-22 20:01:11

第一题 (6+5*5)*5!=3720

第二题我仔细想想先

作者: 达达达 时间: 2009-5-22 20:17:33

终于算完了第二题用枚举法做的

4!+4*4!+4*4!+4*4*3*3!+5*4!+5*4!+5*3*3*3!+5*4!+5*3*3!+3*4!+4*4*4!+3*4*4!+3*4*4*3*3!=2708

不知道LZ有答案么验证下我的是否正确

作者: Alexwildchild 时间: 2009-5-22 20:33:26

我想起了错装信封问题。。。具体的解法忘记了。。。

作者: lulijie 时间: 2009-5-23 13:51:02

用电脑编程计算了一下：
n个人分别去n个地方，其中有m个人被限制不能去某一个地方（被限制去的地方都不相同）。总共方案数为S。
结果如下：
n=7
   m=0    S=5040
   m=1    S=4320
   m=2    S=3720
   m=3    S=3216
   m=4    S=2490       <-----------此处抄错了，应为S=2790
   m=5    S=2428
   m=6    S=2119
   m=7    S=1854
-----------------------------------
n=8
   m=0    S=40320
   m=1    S=35280
   m=2    S=30960
   m=3    S=27240
   m=4    S=24024
   m=5    S=21234
   m=6    S=18806
   m=7    S=16687
   m=8 S=14833
--------------------------------------------
从中大家找找，能不能找出规律，得到通项公式。

[ 本帖最后由 lulijie 于 2009-5-23 14:20 编辑 ]

作者: yq_118 时间: 2009-5-23 13:57:42

用点集合论的知识就简单了。
七個人排成一排，甲不站在中間，乙不站在排尾﹐問有多少種不同的排法？
7！-6！-6！+5！=3720

七個人去七個個地方旅遊，甲不去a地，乙不去b地，丙不去c地，丁不去d地，問有多少種不同的旅遊方案？
7！-6！*4+5!*6-4!*4+3!=2790

看完這兩題忍不住想把它推廣﹐七個人換成n個人(n>8)，
同问题1答案是n!-2*(n-1)!+(n-2)!

四個制限換成五個制限，六個限制...n個限制，能否找到它的通項？
哎，用求和符号写些吧。

好像这个叫什么逐步淘沙定理来的。

[ 本帖最后由 yq_118 于 2009-5-23 14:10 编辑 ]

作者: yq_118 时间: 2009-5-23 14:07:07

原帖由 Alexwildchild 于 2009-5-22 20:33 发表
我想起了错装信封问题。。。具体的解法忘记了。。。

这是两个不同的问题

作者: yq_118 时间: 2009-5-26 02:26:27

原帖由 lulijie 于 2009-5-23 13:51 发表
用电脑编程计算了一下：
n个人分别去n个地方，其中有m个人被限制不能去某一个地方（被限制去的地方都不相同）。总共方案数为S。
结果如下：
n=7
   m=0    S=5040
   m=1    S=4320
   m=2    ...

通项公式还是靠理论分析，从一些数字很难找到规律。

附件: 1.JPG (2009-5-26 02:26:27, 8.76 KB) / 下载次数 45
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTE4OTR8YTFjYTc0ZDl8MTc0MDc3NDk5NHwwfDA%3D

作者: 貔貅 时间: 2009-5-26 02:31:17

第一题：我又没站在里面——不知

第二题：我没跟着去——还是不知

第三题：能找到通项——我前两个都不知

作者: pumpitup 时间: 2009-5-26 11:36:06

甲有两个位置,乙有五个位置,其余的,有p(5,5)种

所以是2*5*1*2*3*4*5=1200吧

2400,难道我错了?

作者: mlyfe0508 时间: 2009-5-26 14:23:03

呵呵，高中数学题.....不过现在忘的差不多了

作者: 九局下半 时间: 2009-5-26 21:32:26

好强大，算不来，只会前面的~~

作者: superacid 时间: 2009-5-27 08:19:48

数据小，他就是要你自己一个一个算出来的，可能没有通项公式。

作者: yq_118 时间: 2009-5-27 19:53:30

原帖由 superacid 于 2009-5-27 08:19 发表
数据小，他就是要你自己一个一个算出来的，可能没有通项公式。

晕，请看16楼，我都算都出来了。

作者: 录 时间: 2009-6-10 22:47:32

最近都沒去想..今天想了下..可以用容斥原理..

作者: 东莞的8 时间: 2009-6-10 22:53:36

路过的。怎么这个题目没有在猪群发出？

[ 本帖最后由东莞的8 于 2009-6-10 22:54 编辑 ]

作者: 录 时间: 2009-6-11 08:04:54

怕被人揍..討論魔方的干嘛發條數學過來

作者: 阿牛++ 时间: 2009-6-11 12:08:35 标题: 搞出通向公式的这个是牛人！！！

16# 大中小发表于 2009-5-26 02:26  只看该作者
引用:
原帖由 lulijie 于 2009-5-23 13:51 发表
用电脑编程计算了一下：
n个人分别去n个地方，其中有m个人被限制不能去某一个地方（被限制去的地方都不相同）。总共方案数为S。
结果如下：
n=7
   m=0    S=5040
   m=1    S=4320
   m=2    ...
通项公式还是靠理论分析，从一些数字很难找到规律。
附件
1.JPG (8.76 KB)
2009-5-26 02:26

[ 本帖最后由阿牛++ 于 2009-6-11 12:12 编辑 ]

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)