排列问题

northwolves · 发表于 2010-5-25 22:14:36

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

1-9各n个排成一列，任意相邻两数字都不相同，共有多少种排列情况？
最简单的计算方法是什么？

KeyTo9_Fans · 发表于 2010-5-25 22:53:09

初始的想法：

动态规划算法。

状态数：

$(n+1)^9$

转移次数：

$9n$

算法的时间复杂度：

$O(n^10)$

然后算一下$n=1$到$n=8$的答案，看看是否有规律。

litaoye · 发表于 2010-5-26 00:07:10

是9*8^(n-1)么？

northwolves · 发表于 2010-5-26 01:53:40

是9*8^(n-1)么？
litaoye 发表于 2010-5-26 00:07

不对。n=1,p=9!

qianyb · 发表于 2010-5-26 07:41:38

S(n)=9n*8n!

northwolves · 发表于 2010-5-26 08:26:32

本帖最后由 northwolves 于 2010-5-26 08:40 编辑

我的解法：
假设1-K 个n 的排列数为p(k)
$p(k)={(0,k=1),(2,k=2),(p(K-1)*(((k-1)*n+1),(n)),k>2)}$

northwolves · 发表于 2010-5-26 08:39:10

郁闷，这个公式编辑不成

litaoye · 发表于 2010-5-26 13:52:11

不好意思，1-9各n个理解成了一共n个。这样的话还是比较复杂！
可以根据容斥原则一点一点算出来，感觉递推比较复杂。
可以看看这个帖子
http://topic.csdn.net/u/20100505 ... 4-9cbb48e3b31e.html

northwolves · 发表于 2010-5-26 14:27:36

6 楼的递推式果然有误，考虑不周。

wayne · 发表于 2010-5-26 14:40:29

8# litaoye

根据CSDN上到帖子，可以得知
1--n被重复了两次的
排列数为：$\sum _{k=0}^n \frac{(-1)^{n-k} (k+n)! C_n^k}{2^k}$
{0, 2, 30, 864, 39480, 2631600, 241133760, 29083420800, 4467125013120}

这个已经就很大了

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 排列问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分