Question

一道奥数题，请数学达人帮帮忙！

一张圆桌边坐了16个学生。课间休息时他们离开座位，上课后又重新坐回到桌边。可以确定的是，每个学生要么还坐在自己原来的座位上，要么坐在与原来座位相邻的两个座位的其中一个上。请问共有多少种不同的坐法？
回答请附上解题过程哦！好答案会有追加分的！
换位算法好像不能分成8组吧……

Answer 1

如果，16个人全在位置上，那么有一种。
而且，如果有一个人在他自己原来的位置上，那么它一侧的人如果不在位置上，
只能跟那一则的交换，而且，被交换的数字，必须填补回来，不然，这将中个空位。如图
---D---C----不动点X------A------B-----Y--
---C---D----不动点X------B------A-----Y--
后面的数字如果也有交换，只可能和它后面的数字进行了。
所以，能交换的数字组成若干个数字交换对，且每个只有一种交换方式。
故而可以得出
1，除非一个环全部运动，不然，不存在奇数个位置进行交换。
2，每组数字只有一种组合，及AB变成BA，所以，只有求组合对数就行了。
先核算其直线排列下基本公式。
16个人全在位置上，那么有1种即，C(16,0)
14个人在位置上，那么有C(16-2+2/2,2/2)
12个人在位置上，那么有C(16-4+4/2,4/2)
10个人在位置上，那么有C(16-6+6/2,6/2)
……
2个人在位置上，那么有C(16-14+14/2,14/2)
0个人在位置上，那么有C(16-16+16/2,16/2)=1
其在环路下，有，当第一组不占据(1,2),位置时，最后一组可以使用(16,1)
所以，其排列数为，使其按基数加来算，但要除去第一组在(1,2)位置上时，最后一组选(16,1)的情况，可由线性组合公式C(n-x,x)推导相应的环形组合数公式为。
C(n-x+1,x)-C(n-x+1-4/2,x-2)=C(n-x+1,x)-C(n-1-x,x-2)
所以有
16个人全在位置上，那么有1种即，C(16,0)
14个人在位置上，环路下为C(16-2+2/2+1,2/2)-0
12个人在位置上，环路下为C(16-4+4/2+1,4/2)-C(16-1-4+4/2,4/2-2)
10个人在位置上，环路下为C(16-6+6/2+1,4/2)-C(16-1-6+6/2,6/2-2)
……
2个人在位置上，环路下为C(16-14+14/2+1,14/2)-C(16-1-14+14/2,14/2-2)
0个人在位置上，环路下为C(16-16+16/2+1,16/2)-C(16-1-16+16/2,16/2-2)
又因为，当全不在位置上时，可以整个向单方向旋转，
且左右各一种，故另加大环位置交换2种。
所以，总共做法为。
C(16,0)+C(16,1)+C(15,2)-C(13,0)+C(14,3)-C(12,1)……+C(10,7)-C(8,5)+C(9,8)-C(7,6)+2
计算得
1+16+104+352+660+672+336+64+2+2=2209

Answer 2

16人每3人中1名有3种其余2人中1人有两种还有一人有一种
3*2*1*5+3

Answer 3

如果一人只能不动或顺时针移动，那他的顺时针方向的人可以与之换位或继续顺时针移动，后者即所有人必须全部顺时针移动一位(位置已经被坐了，不换过去，只能顺时针移动一位啦~~~~），这种情况下每个人都只能移动下去，否则大家自己想，就有空位别人坐不到啦，所以坐法=1。
前者(换位）算法为将16人分为8组，即（12,34,56,78，。。。1516）坐法为2的8次=256种（包括所有人顺序不动的一种）。
坐法共257种。
同理，若只能不动或逆时针移动，（分组为161,23,45,67,89.。。。1415）,坐法=256+1=257种。
故：总坐法为257*2-1（两种分组方法中都包含所有人顺序不动的坐法）=513种

Answer 4

第一个人有3种选择，而剩下的人中除了最后一个人，其余都可看成有2种选择，最后一个人只有一种选择，所以应该是3*2^14*1=49152种坐法（2^14是指14个2相乘，因为14次方打不出来）

Answer 5

答案是 2209 种
容易发现的是，如果连续两个人都往右挪动的话， 全部的人都必须朝右挪动了。同理，连续两个朝左挪动也是。
下面考虑没有连续两个人朝同一方向挪动的情况。
事实上这种情况正好是某些相邻的“对”交换座位的情况。总共是16对，但是对于对之间的交换是有约束的。比如12交换了23就不能再交换。所以这种交换的数目不是太好计算的。

下面考虑把环拆掉，拆成链来计算。
将座位排序为一列点，考虑其中有i对人互换了座位的情况。
这里通过选取这一对中位置靠前的人的种数来计算。
每次在16 - i 个位置中选取i的位置座位交换对中靠前的位置，然后再在其后插入一个点配成交换对。
这里的总数是 (16 - i) 选 i 种。
但是原题中的座位是环状的，也就是说有第16个位置与第一个交换，而前面的计数并没有考虑到。
于是在16与1交换的前提下，剩下的14个位置中仍有 i - 1对交换，并且不再具有环的性质。所以这里又有 (14 - (i-1)) 选 (i-1)种。
于是又i对人互换座位的种数一共是 {16 - i \choose i} + {15 - i \choose i -1}.
这里{m \choose n} 表示 m 选 n 的组合数。
i 可以从 0 取到 8
所以这样的总数是
\sum_{i=0}^{8}({16 - i \choose i} + {15 - i \choose i -1}) = 2207

其中如果组合数中选的数为负数或者超过总数时定义为0.
再加上前面的2种，一共是2209种

Answer 6

2152人
16组

Answer 7

分析：1、若有两个相邻的人同时向左或向右挪动了一位，则其余人必然朝同一个方向挪动一位。
2、排除1的情况后，若某人A向某一方向挪动了一位，则此座的原有人B必然坐在A的位置上，否则，会出现1的情况。我暂且将这种情况称作交叉
解答
一、所有人都坐在原来的位置上，则N=1
二、出现1的情况（向左或向右），则N=2
三、出现2的情况，这时，我将圆形从任意位置打开，变为直线型口口口口口口口口口口口口口口口口，并将对应的人分别编号为一号、二号、……、十六号(用捆绑法)
（1）出现一个交叉的情况
1、从十五个空间中选一个留个这队人N=15
2、恰好一头一尾的两个人进行交叉N=1
{具体操作是：选定一个空间后，选定的空间叫做双人间，其余的叫做单人间，然后按照一到十六的顺序入座，当遇到双人间时，两个人交换顺序后入座}
（2）出现两个交叉的情况
1、从十四个空间中选两个留个这队人N=91
2、一头一尾的两个人进行交叉，给另一组选空间，从13个空间选1个进行交叉N=13
以此类推
三个交叉N=286,N=66
四个交叉N=485,N=330
五个交叉N=462,N=210
六个交叉N=210,N=126
七个交叉N=36,N=28
八个交叉N=2
{用组合数算}
N=2164