魔方吧·中文魔方俱乐部

标题: 2n个人站队排列问题 [打印本页]

作者: xwfh2000 时间: 2015-1-23 11:50:23 标题: 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的整数倍的人相邻，并且队列的第一个人和最后一个人的关系也看作是相邻。问，合法站法一共有多少种？

作者: a471791142 时间: 2015-1-23 18:13:11

容斥原理可以做，好像表达式挺复杂

作者: xwfh2000 时间: 2015-1-23 19:15:24

本帖最后由 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还正在考虑中……

作者: 大耗纸 时间: 2015-1-25 09:57:35

完全表示看不懂。。。。

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