魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 1231|回复: 3

2n个人站队排列问题 [复制链接]

Rank: 2

积分
268
帖子
570
精华
1
UID
112
性别

十四年元老 十年元老 十二年元老

发表于 2015-1-23 11:50:23 |显示全部楼层
本帖最后由 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的整数倍的人相邻,并且队列的第一个人和最后一个人的关系也看作是相邻。问,合法站法一共有多少种?

Rank: 1

积分
39
帖子
25
精华
0
UID
1307898
发表于 2015-1-23 18:13:11 |显示全部楼层
容斥原理可以做,好像表达式挺复杂

使用道具 举报

Rank: 2

积分
268
帖子
570
精华
1
UID
112
性别

十四年元老 十年元老 十二年元老

发表于 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还正在考虑中……

使用道具 举报

Rank: 1

积分
134
帖子
134
精华
0
UID
1334123
发表于 2015-1-25 09:57:35 |显示全部楼层
完全表示看不懂。。。。

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2022-6-29 20:40

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部