2n个人站队排列问题
本帖最后由 xwfh2000 于 2015-1-23 12:01 编辑现在有2n个人站成一队，人的编号分别为1,2,3，……2n-1,2n。要求1和n+1不能站一起，2和n+2不能站一起，……以此类推，n-1和2n-1不能站一起，n与2n不能站一起（即每个人都不能和比自己编号大n或小n的人站一起）。
问，总共的合法站法。
变种1：追加一个条件：队列的第一个人和队列的最后一个人也看做是相邻。为此时的站法共有多少种？
变种2：现在有mn个人，编号为1到mn。其中每个人都不能同编号和自己差n的整数倍的人相邻，并且队列的第一个人和最后一个人的关系也看作是相邻。问，合法站法一共有多少种？ 容斥原理可以做，好像表达式挺复杂 本帖最后由 xwfh2000 于 2015-1-23 19:17 编辑
是的，用互斥原理可以做。主题和变种1都已经解决，因为写数学公式不方便，因此直接放c语言代码；
主题主要计算代码：
double sum = fac(2*n);
sum += Math.Pow(-1, k) * fac(n) / fac(n - k) / fac(k) * Math.Pow(2, k) * fac(2 * n - k); k从1到n
变种1主要计算代码：
double sum = fac(2*n);
sum += Math.Pow(-1, k) * fac(n) / fac(n - k) / fac(k) * Math.Pow(2, k) *( fac(2 * n - k)+k*fac(2*n-k-1)); k从1到n
其中，fac是自己写的阶乘函数。
以下是程序部分计算结果：
n 主题解 变种1解
2: 8 8
3: 240 192
4: 13824 11904
5: 1263360 1125120
6: 168422400 153262080
7: 30865121280 28507207680
8: 7445355724800 6951513784320
9: 2.28716800671744E+15 2.15315160367104E+15
10: 8.71804170613555E+17 8.26060810479206E+17
11: 4.03779880746418E+20 3.8460018899292E+20
变种2还正在考虑中……
完全表示看不懂。。。。:Q
页:
[1]