排列问题
1-9各n个排成一列，任意相邻两数字都不相同，共有多少种排列情况？最简单的计算方法是什么？ 初始的想法：
动态规划算法。
状态数：
$(n+1)^9$
转移次数：
$9n$
算法的时间复杂度：
$O(n^10)$
然后算一下$n=1$到$n=8$的答案，看看是否有规律。 是9*8^(n-1)么？ 是9*8^(n-1)么？
litaoye 发表于 2010-5-26 00:07 http://bbs.emath.ac.cn/images/common/back.gif
不对。n=1,p=9! S(n)=9n*8n! 本帖最后由 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)}$ 郁闷，这个公式编辑不成 不好意思，1-9各n个理解成了一共n个。这样的话还是比较复杂！
可以根据容斥原则一点一点算出来，感觉递推比较复杂。
可以看看这个帖子
http://topic.csdn.net/u/20100505/09/73065037-b246-458b-a2b4-9cbb48e3b31e.html 6 楼的递推式果然有误，考虑不周。 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}
这个已经就很大了
页:
[1]
2